Search results for "depth-3"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
37	Zohar Shay Karnin, Amir Shpilka	Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In.	CCC	2008	DBLP DOI BibTeX RDF	PIT, depth-3, arithmetic circuit, deterministic, polynomial identity testing
33	Zeev Dvir, Amir Shpilka	Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.	STOC	2005	DBLP DOI BibTeX RDF	depth 3 circuits, locally decodable codes, polynomial identity testing
32	Dmitriy Yu. Cherukhin	Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates.	CSR	2008	DBLP DOI BibTeX RDF	complexity, lower bound, Boolean function, circuit, depth, cyclic convolution
29	Dima Grigoriev, Alexander A. Razborov	Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.	Appl. Algebra Eng. Commun. Comput.	2000	DBLP DOI BibTeX RDF	Exponential lower bounds, Depth 3 arithmetic circuits, Finite fields
29	Dima Grigoriev, Alexander A. Razborov	Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.	FOCS	1998	DBLP DOI BibTeX RDF	depth 3 arithmetic circuits, exponential lower bounds, approximating by sparse polynomials
28	Johan Håstad, Stasys Jukna, Pavel Pudlák	Top-Down Lower Bounds for Depth 3 Circuits	FOCS	1993	DBLP DOI BibTeX RDF	nonmonotone circuits, top-down lower bounds, depth 3 circuits, depth 3 AND-OR-NOT circuits, strong lower bound, top-down argument
23	Ran Raz, Iddo Tzameret	The Strength of Multilinear Proofs.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17, 13P10
23	Amir Shpilka, Ilya Volkovich	Read-once polynomial identity testing.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, identity testing, read-once formulas, reconstruction, arithmetic circuits
19	Amir Shpilka	Affine Projections of Symmetric Polynomials.	CCC	2001	DBLP DOI BibTeX RDF
19	Sorin Cotofana, Stamatis Vassiliadis	Signed Digit Addition and Related Operations with Threshold Logic.	IEEE Trans. Computers	2000	DBLP DOI BibTeX RDF	signed-digit arithmetic, redundant adders, redundant multipliers, neural networks, Computer arithmetic, threshold logic, carry-free addition, signed-digit number representation
19	Nitin Saxena 0001	Diagonal Circuit Identity Testing and Lower Bounds.	ICALP (1)	2008	DBLP DOI BibTeX RDF	identity testing, depth 3, depth 4, lower bounds, determinant, arithmetic circuit, permanent
18	Christian Glaßer, Heinz Schmitz	Languages of Dot-Depth 3/2.	STACS	2000	DBLP DOI BibTeX RDF
18	Amir Shpilka, Avi Wigderson	Depth-3 Arithmetic Formulae over Fields of Characteristic Zero.	CCC	1999	DBLP DOI BibTeX RDF
17	Amir Shpilka	Interpolation of depth-3 arithmetic circuits with two multiplication gates.	STOC	2007	DBLP DOI BibTeX RDF	depth-3, interpolation, arithmetic circuits, exact learning
15	David Buchfuhrer, Christopher Umans	The Complexity of Boolean Formula Minimization.	ICALP (1)	2008	DBLP DOI BibTeX RDF
15	Sorin Dan Cotofana, Casper Lageweg, Stamatis Vassiliadis	Addition Related Arithmetic Operations via Controlled Transport of Charge.	IEEE Trans. Computers	2005	DBLP DOI BibTeX RDF	single electron technology, electron counting, multiplication, SET, addition
15	Satyanarayana V. Lokam	Graph Complexity and Slice Functions.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
15	Sorin Cotofana, Casper Lageweg, Stamatis Vassiliadis	On Computing Addition Related Arithmetic Operations via Controlled Transport of Charge.	IEEE Symposium on Computer Arithmetic	2003	DBLP DOI BibTeX RDF
15	José Fernández Ramos, Alfonso Gago Bohórquez	Two Operand Binary Adders with Threshold Logic.	IEEE Trans. Computers	1999	DBLP DOI BibTeX RDF	neural networks, logic design, computer arithmetic, Threshold logic, threshold gate, binary adders
15	Claudia Bertram-Kretzberg, Thomas Hofmeister	Multiple Product Modulo Arbitrary Numbers.	MFCS	1995	DBLP DOI BibTeX RDF
13	Suryajith Chillara, Partha Mukhopadhyay	On the limits of depth reduction at depth 3 over small finite fields.	Inf. Comput.	2017	DBLP DOI BibTeX RDF
13	Manindra Agrawal, Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
13	Sébastien Tavenas	Improved bounds for reduction to depth 4 and depth 3.	Inf. Comput.	2015	DBLP DOI BibTeX RDF
13	Suryajith Chillara, Partha Mukhopadhyay	On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields.	CoRR	2014	DBLP BibTeX RDF
13	Suryajith Chillara, Partha Mukhopadhyay	On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields.	MFCS (2)	2014	DBLP DOI BibTeX RDF
13	Sébastien Tavenas	Improved bounds for reduction to depth 4 and depth 3	CoRR	2013	DBLP BibTeX RDF
13	Sébastien Tavenas	Improved Bounds for Reduction to Depth 4 and Depth 3.	MFCS	2013	DBLP DOI BibTeX RDF
13	Manindra Agrawal, Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.	STOC	2012	DBLP DOI BibTeX RDF
13	Manindra Agrawal, Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
13	Manindra Agrawal, Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits	CoRR	2011	DBLP BibTeX RDF
12	Ran Raz	Tensor-rank and lower bounds for arithmetic formulas.	STOC	2010	DBLP DOI BibTeX RDF	homogenous circuits, multilinear circuits, tensor rank, lower bounds, arithmetic circuits
12	Emanuele Viola	On Approximate Majority and Probabilistic Time.	CCC	2007	DBLP DOI BibTeX RDF
12	Alexis Maciel, Denis Thérien	Threshold Circuits for Iterated Multiplication: Using AC0 for Free.	STACS	1993	DBLP DOI BibTeX RDF
12	Sorin Istrail, Dejan Zivkovic	A Non-Probabilistic Switching Lemma for the Sipser Function.	STACS	1993	DBLP DOI BibTeX RDF
11	Kai-Yeung Siu, Vwani P. Roychowdhury, Thomas Kailath	Depth-Size Tradeoffs for Neural Computation.	IEEE Trans. Computers	1991	DBLP DOI BibTeX RDF	arithmetic functions, depth-3, parallel computation, Boolean functions, neural nets, size, threshold logic, neural computation, threshold gates, symmetric Boolean functions
11	Andrew Chi-Chih Yao	On ACC and Threshold Circuits	FOCS	1990	DBLP DOI BibTeX RDF	ACC, two-level circuits, symmetric-function gate, depth-3 threshold circuits, language, computing power, threshold circuits, AND gates
10	Neeraj Kayal, Nitin Saxena 0001	Polynomial Identity Testing for Depth 3 Circuits.	Comput. Complex.	2007	DBLP DOI BibTeX RDF	13P99, Subject classification. 68Q15
10	Neeraj Kayal, Nitin Saxena 0001	Polynomial Identity Testing for Depth 3 Circuits.	CCC	2006	DBLP DOI BibTeX RDF
10	Richard Beigel, Alexis Maciel	Upper and Lower Bounds for Some Depth-3 Circuit Classes.	CCC	1997	DBLP DOI BibTeX RDF	constant depth, majority gate, MOD gate, inner product mod 2, threshold circuit
8	Alexander A. Sherstov	Separating AC0 from depth-2 majority circuits.	STOC	2007	DBLP DOI BibTeX RDF	AC0, communication complexity, discrepancy, threshold circuits
8	Adam R. Klivans, Alexander A. Sherstov	Cryptographic Hardness for Learning Intersections of Halfspaces.	FOCS	2006	DBLP DOI BibTeX RDF
8	Kei Uchizawa, Rodney J. Douglas, Wolfgang Maass 0001	Energy Complexity and Entropy of Threshold Circuits.	ICALP (1)	2006	DBLP DOI BibTeX RDF
8	Ran Raz, Amir Shpilka	Deterministic polynomial identity testing in non-commutative models.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q25, Subject classification
8	Ran Raz, Amir Shpilka	Deterministic Polynomial Identity Testing in Non-Commutative Models.	CCC	2004	DBLP DOI BibTeX RDF
8	Matthias Krause 0001	On Realizing Iterated Multiplication by Small Depth Threshold Circuits.	STACS	1995	DBLP DOI BibTeX RDF
8	Nader H. Bshouty, Richard Cleve, Sampath Kannan, Christino Tamon	Oracles and Queries that are Sufficient for Exact Learning (Extended Abstract).	COLT	1994	DBLP DOI BibTeX RDF
8	Dima Grigoriev, Marek Karpinski	A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals.	AAECC	1993	DBLP DOI BibTeX RDF
6	Tameem Choudhury, Karteek Sreenivasaiah	Depth-3 Circuit Lower Bounds for k-OV.	STACS	2024	DBLP DOI BibTeX RDF
6	Mika Göös, Ziyi Guan, Tiberiu Mosnoi	Depth-3 Circuits for Inner Product.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
6	Tameem Choudhury, Karteek Sreenivasaiah	Depth-3 Circuit Lower Bounds for k-OV.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
6	Mika Göös, Ziyi Guan, Tiberiu Mosnoi	Depth-3 Circuits for Inner Product.	MFCS	2023	DBLP DOI BibTeX RDF
6	Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye	On depth-3 circuits and covering number: an explicit counter-example.	CoRR	2022	DBLP DOI BibTeX RDF
6	Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard	A Variant of the VC-Dimension with Applications to Depth-3 Circuits.	ITCS	2022	DBLP DOI BibTeX RDF
6	Pranjal Dutta, Nitin Saxena 0001	Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits.	FOCS	2022	DBLP DOI BibTeX RDF
6	Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich	Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
6	Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich	Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits.	CoRR	2021	DBLP BibTeX RDF
6	Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard	A Variant of the VC-dimension with Applications to Depth-3 Circuits.	CoRR	2021	DBLP BibTeX RDF
6	Pranjal Dutta, Prateek Dwivedi 0001, Nitin Saxena 0001	Demystifying the border of depth-3 algebraic circuits.	FOCS	2021	DBLP DOI BibTeX RDF
6	Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich	Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits.	STOC	2021	DBLP DOI BibTeX RDF
6	Mrinal Kumar 0001	On the Power of Border of Depth-3 Arithmetic Circuits.	ACM Trans. Comput. Theory	2020	DBLP DOI BibTeX RDF
6	Vikraman Arvind, Abhranil Chatterjee 0001, Rajit Datta, Partha Mukhopadhyay	Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
6	Mrinal Kumar 0001	On top fan-in vs formal degree for depth-3 arithmetic circuits.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
6	Mrinal Kumar 0001	On top fan-in vs formal degree for depth-3 arithmetic circuits.	CoRR	2018	DBLP BibTeX RDF
6	Vikraman Arvind, Abhranil Chatterjee 0001, Rajit Datta, Partha Mukhopadhyay	A Note on Polynomial Identity Testing for Depth-3 Circuits.	CoRR	2018	DBLP BibTeX RDF
6	Ning Ding 0001, Yanli Ren, Dawu Gu	PAC Learning Depth-3 $\textrm{AC}^0$ Circuits of Bounded Top Fanin.	ALT	2017	DBLP BibTeX RDF
6	Ankit Gupta 0001, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi	Arithmetic Circuits: A Chasm at Depth 3.	SIAM J. Comput.	2016	DBLP DOI BibTeX RDF
6	Gaurav Sinha	Reconstruction of Real Depth-3 Circuits with Top Fan-In 2.	CCC	2016	DBLP DOI BibTeX RDF
6	Gaurav Sinha	Reconstruction of Real depth-3 Circuits with top fan-in 2.	CoRR	2015	DBLP BibTeX RDF
6	Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.	Comput. Complex.	2013	DBLP DOI BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits.	J. ACM	2013	DBLP DOI BibTeX RDF
6	Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena 0001	Hitting-sets for low-distance multilinear depth-3.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
6	Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena 0001	Hitting-sets for low-distance multilinear depth-3.	CoRR	2013	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn't Matter.	SIAM J. Comput.	2012	DBLP DOI BibTeX RDF
6	Khalid Mohamed Alajel, Wei Xiang 0001	Color plus depth 3-D video transmission with hierarchical 16-QAM.	3DTV-Conference	2012	DBLP DOI BibTeX RDF
6	Zohar Shay Karnin, Amir Shpilka	Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in.	Comb.	2011	DBLP DOI BibTeX RDF
6	Chandan Saha 0001, Ramprasad Saptharishi, Nitin Saxena 0001	A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
6	Craig Gentry, Shai Halevi	Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits.	IACR Cryptol. ePrint Arch.	2011	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	An Almost Optimal Rank Bound for Depth-3 Identities.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
6	Craig Gentry, Shai Halevi	Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits.	FOCS	2011	DBLP DOI BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter.	STOC	2011	DBLP DOI BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits	CoRR	2010	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter	CoRR	2010	DBLP BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits.	FOCS	2010	DBLP DOI BibTeX RDF
6	Jeffrey Tsang	The structure of a depth-3 lookup table representation for Prisoner's Dilemma.	CIG	2010	DBLP DOI BibTeX RDF
6	Neeraj Kayal, Shubhangi Saraf	Blackbox Polynomial Identity Testing for Depth 3 Circuits.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
6	Amir Shpilka	Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates.	SIAM J. Comput.	2009	DBLP DOI BibTeX RDF
6	Neeraj Kayal, Shubhangi Saraf	Blackbox Polynomial Identity Testing for Depth 3 Circuits.	FOCS	2009	DBLP DOI BibTeX RDF	Sylvester, Derandomization, Arithmetic circuits
6	Nitin Saxena 0001, C. Seshadhri 0001	An Almost Optimal Rank Bound for Depth-3 Identities.	CCC	2009	DBLP DOI BibTeX RDF
6	Zohar Shay Karnin, Amir Shpilka	Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in.	CCC	2009	DBLP DOI BibTeX RDF
6	Nitin Saxena 0001, C. Seshadhri 0001	An Almost Optimal Rank Bound for Depth-3 Identities.	Electron. Colloquium Comput. Complex.	2008	DBLP BibTeX RDF
6	Christian Glaßer, Heinz Schmitz	Languages of Dot-Depth 3/2.	Theory Comput. Syst.	2008	DBLP DOI BibTeX RDF	Starfree regular languages, Concatenation hierarchies, Dot-depth hierarchy, Decidability
6	Nitin Saxena 0001, C. Seshadhri 0001	An Almost Optimal Rank Bound for Depth-3 Identities	CoRR	2008	DBLP BibTeX RDF
6	Alexander A. Sherstov	Powering requires threshold depth 3.	Inf. Process. Lett.	2007	DBLP DOI BibTeX RDF
6	Zohar Shay Karnin, Amir Shpilka	Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in.	Electron. Colloquium Comput. Complex.	2007	DBLP BibTeX RDF
6	Zeev Dvir, Amir Shpilka	Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits.	SIAM J. Comput.	2007	DBLP DOI BibTeX RDF
6	Tahsin Oner, Dick de Jongh	The Structure of Rigid Frames of Depth 3 Only.	TbiLLC	2007	DBLP DOI BibTeX RDF
6	Guy Wolfovitz	The complexity of depth-3 circuits computing symmetric Boolean functions.	Inf. Process. Lett.	2006	DBLP DOI BibTeX RDF
6	Guy Wolfovitz	The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions.	Electron. Colloquium Comput. Complex.	2006	DBLP BibTeX RDF