首页    期刊浏览 2024年10月05日 星期六
登录注册

文章基本信息

  • 标题:Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties
  • 本地全文:下载
  • 作者:Ankit Gupta
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we present an algorithm that, given blackboxes to P 1 P d , Q 11 Q 1 d 1 , , Q k 1 Q k d k where k and the degrees of P i 's and Q i j 's are bounded, determines the membership of P 1 P d in the radical of the ideal generated by Q 11 Q 1 d 1 , , Q k 1 Q k d k in deterministic poly( n d max i ( d i ) )-time.

    We also give a Dvir-Shpilka (STOC 2005)-like approach to resolve the degenerate case and, in the process, initiate a new direction in incidence geometry for non-linear varieties . This approach consists of a series of Sylvester-Gallai type conjectures for bounded-degree varieties and, if true, imply a complete derandomization in the bounded bottom fanin case. To the best of our knowledge, these problems have not been posed before.

  • 关键词:arithmetic circuits ; depth-4 ; identity testing ; radical membership ; Sylvester-Gallai type problems
国家哲学社会科学文献中心版权所有