NDLI: From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits

Content Provider	ACM Digital Library
Author	Saxena, Nitin Seshadhri, C.
Copyright Year	2013
Abstract	We study the problem of identity testing for depth-3 circuits of top fanin $\textit{k}$ and degree $\textit{d}.$ We give a new structure theorem for such identities that improves the known deterministic $d^{k}^{O(k)}-time$ blackbox identity test over rationals [Kayal and Saraf, 2009] to one that takes $d^{O(k^{2})}-time.$ Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir and Shpilka [2006]. We devise various algebraic tools to study depth-3 identities, and use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the “complexity” of the main identity. The special properties of this nucleus allow us to get near optimal rank bounds for depth-3 identities. The most important aspect of this work is relating a field-dependent quantity, the Sylvester-Gallai rank bound, to the rank of depth-3 identities. We also prove a high-dimensional Sylvester-Gallai theorem for all fields, and get a general depth-3 identity rank bound (slightly improving previous bounds).
Starting Page	1
Ending Page	33
Page Count	33
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2528403
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-10-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Chinese remaindering Sylvester-Gallai Combinatorial design Depth-3 circuit Ideal theory Identities Incidence geometry
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits

From Sylvester-Gallai Configurations to Rank Bounds: Improved Blackbox Identity Test for Depth-3 Circuits

From sylvester-gallai configurations to rank bounds: improved blackbox identity test for depth-3 circuits.

From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits (2010)

From sylvester-gallai configurations to rank bounds: improved black-box identity test for depth-3 circuits.

From sylvester-gallai configurations to rank bounds: improved black-box identity test for depth-3 circuits (2010).

From sylvester-gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits

Similar Documents

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits

From Sylvester-Gallai Configurations to Rank Bounds: Improved Blackbox Identity Test for Depth-3 Circuits

From sylvester-gallai configurations to rank bounds: improved blackbox identity test for depth-3 circuits.

From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits (2010)

From sylvester-gallai configurations to rank bounds: improved black-box identity test for depth-3 circuits.

From sylvester-gallai configurations to rank bounds: improved black-box identity test for depth-3 circuits (2010).

From sylvester-gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits