Search results for "constant-depth"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
72	Jin-yi Cai, D. Sivakumar, Martin Strauss 0001	Constant Depth Circuits and the Lutz Hypothesis.	FOCS	1997	DBLP DOI BibTeX RDF	Lutz hypothesis, Exponential Time, constant-depth, nearly exponential-size circuits, circuit complexity theory, computational complexity, pseudorandom generators, complexity classes, NP, constant depth circuits
68	Benjamin Rossman	On the constant-depth complexity of k-clique.	STOC	2008	DBLP DOI BibTeX RDF	ac0, bounded variable hierarchy, k-clique, first-order logic, circuit complexity, constant-depth circuits
63	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	CCC	2008	DBLP DOI BibTeX RDF	Constant Depth, Lower Bounds, Separations, Arithmetic Circuits
62	Jin-yi Cai	Lower Bounds for Constant Depth Circuits in the Presence of Help Bits	FOCS	1989	DBLP DOI BibTeX RDF	help bit, arbitrary Boolean function, exponential lower bound, parity functions, random oracle separation, constant depth circuits, constant depth circuit, PSPACE, PH
61	Manindra Agrawal, Eric Allender, Samir Datta	On TC0, AC0, and Arithmetic Circuits.	CCC	1997	DBLP DOI BibTeX RDF	TC/sup 0/, AC/sup 0/, function classes, constant-depth polynomial-size arithmetic circuits, unbounded fanin addition, multiplication gates, constant-depth arithmetic circuits, computational complexity, normal forms, arithmetic circuits, closure properties
54	Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum	Verifying and decoding in constant depth.	STOC	2007	DBLP DOI BibTeX RDF	error-correcting codes, interactive proofs, constant-depth circuits
52	Dan Gutfreund, Guy N. Rothblum	The Complexity of Local List Decoding.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF	list-decodable codes, constant-depth circuits, locally-decodable codes
48	Ran Raz, Amir Shpilka	Lower bounds for matrix product, in bounded depth circuits with arbitrary gates.	STOC	2001	DBLP DOI BibTeX RDF
47	Emanuele Viola	On Constructing Parallel Pseudorandom Generators from One-Way Functions.	CCC	2005	DBLP DOI BibTeX RDF	Pseudorandom generator construction, one-way function, black-box, restriction, constant-depth circuit, noise sensitivity, hardness amplification
46	Emanuele Viola	Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates.	CCC	2005	DBLP DOI BibTeX RDF
46	Miklos Santha, Christopher B. Wilson	Polynomial Size Constant Depth Circuits with a Limited Number of Negations.	STACS	1991	DBLP DOI BibTeX RDF
43	Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang 0053	Bounds on the Power of Constant-Depth Quantum Circuits.	FCT	2005	DBLP DOI BibTeX RDF
41	Ronen Shaltiel, Emanuele Viola	Hardness amplification proofs require majority.	STOC	2008	DBLP DOI BibTeX RDF	amplification, natural proofs, black-box, hardness, average-case complexity, constant-depth circuits, majority
40	Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu	Learning a circuit by injecting values.	STOC	2006	DBLP DOI BibTeX RDF	learning, circuit, gene regulatory network
40	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	68Q17, Subject classification
39	Alexis Maciel, Toniann Pitassi	Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives.	LICS	2006	DBLP DOI BibTeX RDF
39	Adam R. Klivans	On the Derandomization of Constant Depth Circuits.	RANDOM-APPROX	2001	DBLP DOI BibTeX RDF
39	Ashok K. Chandra, Steven Fortune, Richard J. Lipton	Lower Bounds for Constant Depth Circuits for Prefix Problems.	ICALP	1983	DBLP DOI BibTeX RDF
38	Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff, Rolf Wanka	Fast and Feasible Periodic Sorting Networks of Constant Depth	FOCS	1994	DBLP DOI BibTeX RDF	d-dimensional mesh, periodic sorting networks, constant depth, compare-exchange operations, AKS network, Batcher's networks, comparator network, layout area
37	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	Cryptography with Constant Input Locality.	CRYPTO	2007	DBLP DOI BibTeX RDF
36	Emanuele Viola	The complexity of constructing pseudorandom generators from hard functions.	Comput. Complex.	2005	DBLP DOI BibTeX RDF	68Q01, Subject classification
32	Zhouchen Lin, Heung-Yeung Shum	On the Number of Samples Needed in Light Field Rendering with Constant-Depth Assumption.	CVPR	2000	DBLP DOI BibTeX RDF
30	Scott Aaronson	BQP and the polynomial hierarchy.	STOC	2010	DBLP DOI BibTeX RDF	linial-nisan conjecture, quantum complexity classes, fourier analysis, constant-depth circuits
30	Michal Koucký 0001, Pavel Pudlák, Denis Thérien	Bounded-depth circuits: separating wires from gates.	STOC	2005	DBLP DOI BibTeX RDF	communication, complexity, lower bounds, regular languages, wires, constant-depth circuits, gates
30	Moni Naor, Omer Reingold	Number-theoretic constructions of efficient pseudo-random functions.	J. ACM	2004	DBLP DOI BibTeX RDF	constant-depth threshold circuits, decision Diffie-Hellman, natural proofs, factoring, learning theory, Pseudo-random functions
30	Moni Naor, Omer Reingold	Number-theoretic Constructions of Efficient Pseudo-random Functions.	FOCS	1997	DBLP DOI BibTeX RDF	number-theoretic constructions, cryptography, cryptographic primitives, constant depth circuits, pseudo-random functions, threshold gates
29	Marcin Kik, Miroslaw Kutylowski, Grzegorz Stachowiak	Periodic Constant Depth Sorting Networks.	STACS	1994	DBLP DOI BibTeX RDF
29	Mrinal Kumar 0001, Varun Ramanathan 0002, Ramprasad Saptharishi, Ben Lee Volk	Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits.	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
29	Mrinal Kumar 0001, Varun Ramanathan 0002, Ramprasad Saptharishi, Ben Lee Volk	Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits.	CoRR	2024	DBLP DOI BibTeX RDF
28	Russell Impagliazzo, Nathan Segerlind	Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations.	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	Modular counting axioms, Nullstellensatz refutations, propositional proof complexity
28	Omer Barkol, Yuval Ishai	Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems.	CRYPTO	2005	DBLP DOI BibTeX RDF
28	Hubie Chen	Arithmetic Constant-Depth Circuit Complexity Classes.	MFCS	2003	DBLP DOI BibTeX RDF
28	Manindra Agrawal	Hard Sets and Pseudo-random Generators for Constant Depth Circuits.	FSTTCS	2001	DBLP DOI BibTeX RDF
28	H. K. Dai 0001	The Size Complexity of Strictly Non-blocking Fixed Ratio Concentrators with Constant Depth.	Euro-Par, Vol. I	1996	DBLP DOI BibTeX RDF
28	Ingo Wegener, Norbert Wurm, Sang-Zin Yi	Symmetric Functions in AC0A Can Be Computed in Constant Depth With Very Small Size.	MFCS	1990	DBLP DOI BibTeX RDF
25	Kei Uchizawa, Eiji Takimoto	An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity.	CCC	2007	DBLP DOI BibTeX RDF
24	Arkadev Chattopadhyay, Avi Wigderson	Linear Systems over Composite Moduli.	FOCS	2009	DBLP DOI BibTeX RDF	Boolean circuit complexity, modular gates, matrix rigidity, exponential sums, constant-depth circuits
24	Paul Beame, Dang-Trinh Huynh-Ngoc	Multiparty Communication Complexity and Threshold Circuit Size of AC^0.	FOCS	2009	DBLP DOI BibTeX RDF	lower bounds, communication complexity, constant-depth circuits
24	Maurice J. Jansen, Kenneth W. Regan	"Resistant" Polynomials and Stronger Lower Bounds for Depth-Three Arithmetical Formulas.	COCOON	2007	DBLP DOI BibTeX RDF	constant depth formulas, Computational complexity, lower bounds, arithmetical circuits, partial derivatives
24	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
24	Wolfgang Maass 0001, Georg Schnitger, Eduardo D. Sontag	On the Computational Power of Sigmoid versus Boolean Threshold Circuits	FOCS	1991	DBLP DOI BibTeX RDF	polynomially bounded weights, sigmoid threshold gates, smooth threshold gates, depth 2 circuits, Boolean threshold circuits, constant size circuits, Boolean threshold gates, polynomial size sigmoid threshold circuits, Boolean functions, computational power, constant depth circuits
24	Ran Raz	Elusive functions and lower bounds for arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, lower bounds, arithmetic circuits, circuit complexity
21	Kazuyuki Amano, Akira Maruoka	Some Properties of MODm Circuits Computing Simple Functions.	CIAC	2003	DBLP DOI BibTeX RDF	modular circuits, composite modulus, lower bounds, Fourier analysis, symmetric functions
21	Peter Høyer, Robert Spalek	Quantum Circuits with Unbounded Fan-out.	STACS	2003	DBLP DOI BibTeX RDF
21	Michael Schmitt 0001	Product Unit Neural Networks with Constant Depth and Superlinear VC Dimension.	ICANN	2001	DBLP DOI BibTeX RDF
21	Jan Krajícek	Lower Bounds for a Proof System with an Expentential Speed-up over Constant-Depth Frege Systems and over Polynomial Calculus.	MFCS	1997	DBLP DOI BibTeX RDF
21	Purnata Ghosal, Om Prakash 0002, B. V. Raghavendra Rao	On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction.	COCOON	2017	DBLP DOI BibTeX RDF
21	Eric Allender, Michal Koucký 0001	Amplifying Lower Bounds by Means of Self-Reducibility.	CCC	2008	DBLP DOI BibTeX RDF	self-reducibility, lower bounds, circuit complexity
21	Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui	Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate.	STACS	1993	DBLP DOI BibTeX RDF
18	Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano	Randomized path coloring on binary trees.	APPROX	2000	DBLP DOI BibTeX RDF
18	Phuong Nguyen, Stephen A. Cook	VTC circ: A Second-Order Theory for TCcirc.	LICS	2004	DBLP DOI BibTeX RDF
18	Andreas Jakoby, Rüdiger Reischuk	Average Case Complexity of Unbounded Fanin Circuits.	CCC	2000	DBLP DOI BibTeX RDF
17	Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien	Lower bounds for circuits with MOD_m gates.	FOCS	2006	DBLP DOI BibTeX RDF
17	Dan Gutfreund, Emanuele Viola	Fooling Parity Tests with Parity Gates.	APPROX-RANDOM	2004	DBLP DOI BibTeX RDF
15	Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum	A (de)constructive approach to program checking.	STOC	2008	DBLP DOI BibTeX RDF	program testing, program correcting, program checking
15	Peter Høyer, Mehdi Mhalla, Simon Perdrix	Resources Required for Preparing Graph States.	ISAAC	2006	DBLP DOI BibTeX RDF	Foundations of computing, Algorithms, Quantum Computing
15	Gang Li, Steven W. Zucker	Surface Geometric Constraints for Stereo in Belief Propagation.	CVPR (2)	2006	DBLP DOI BibTeX RDF
15	Zhigang Zhu, Allen R. Hanson, Edward M. Riseman	Generalized Parallel-Perspective Stereo Mosaics from Airborne Video.	IEEE Trans. Pattern Anal. Mach. Intell.	2004	DBLP DOI BibTeX RDF	airborne video analysis, image registration, stereo vision, epipolar geometry, Mosaicing, visual representation, view interpolation
15	Zhouchen Lin, Heung-Yeung Shum	A Geometric Analysis of Light Field Rendering.	Int. J. Comput. Vis.	2004	DBLP DOI BibTeX RDF	double image, sampling, light field, image-based modeling and rendering, view interpolation, lumigraph
15	Jinxiang Chai, Shing-Chow Chan, Heung-Yeung Shum, Xin Tong 0001	Plenoptic sampling.	SIGGRAPH	2000	DBLP DOI BibTeX RDF	plenoptic sampling, sampling, image-based rendering, spectral analysis, plenoptic functions
15	Mikael Goldmann, Mats Näslund	The Complexity of Computing Hard Core Predicates.	CRYPTO	1997	DBLP DOI BibTeX RDF	small-depth circuit, one-way function, Pseudo-randomness
14	Joel Rajakumar, James D. Watson, Yi-Kai Liu 0001	Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth.	CoRR	2024	DBLP DOI BibTeX RDF
14	Levente Bodnar	CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits.	CoRR	2024	DBLP DOI BibTeX RDF
14	Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß	On the Constant-Depth Circuit Complexity of Generating Quasigroups.	CoRR	2024	DBLP DOI BibTeX RDF
14	Mrinal Kumar 0001, Varun Ramanathan 0002, Ramprasad Saptharishi	Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.	SODA	2024	DBLP DOI BibTeX RDF
14	Mrinal Kumar 0001, Varun Ramanathan 0002, Ramprasad Saptharishi	Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
14	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
14	Bruno Pasqualotto Cavalar, Igor Carboni Oliveira	Constant-depth circuits vs. monotone circuits.	Electron. Colloquium Comput. Complex.	2023	DBLP BibTeX RDF
14	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
14	Lena Strobl	Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits.	CoRR	2023	DBLP DOI BibTeX RDF
14	Mrinal Kumar 0001, Varun Ramanathan 0002, Ramprasad Saptharishi	Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.	CoRR	2023	DBLP DOI BibTeX RDF
14	Jonathan Allcock, Jinge Bao, João F. Doriguello, Alessandro Luongo, Miklos Santha	Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits.	CoRR	2023	DBLP DOI BibTeX RDF
14	Bruno Pasqualotto Cavalar, Igor C. Oliveira	Constant-depth circuits vs. monotone circuits.	CoRR	2023	DBLP DOI BibTeX RDF
14	Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii	Constant-Depth Sorting Networks.	ITCS	2023	DBLP DOI BibTeX RDF
14	Anette Messinger, Michael Fellner, Wolfgang Lechner	Constant Depth Code Deformations in the Parity Architecture.	QCE	2023	DBLP DOI BibTeX RDF
14	Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi	Range Avoidance for Constant Depth Circuits: Hardness and Algorithms.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
14	Bruno Pasqualotto Cavalar, Igor C. Oliveira	Constant-Depth Circuits vs. Monotone Circuits.	CCC	2023	DBLP DOI BibTeX RDF
14	Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan 0001	A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.	Algorithmica	2022	DBLP DOI BibTeX RDF
14	Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii	Constant-Depth Sorting Networks.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
14	William Merrill, Ashish Sabharwal, Noah A. Smith	Saturated Transformers are Constant-Depth Threshold Circuits.	Trans. Assoc. Comput. Linguistics	2022	DBLP BibTeX RDF
14	William Merrill, Ashish Sabharwal	Log-Precision Transformers are Constant-Depth Uniform Threshold Circuits.	CoRR	2022	DBLP DOI BibTeX RDF
14	Jonathan H. A. de Carvalho, Fernando M. de Paula Neto	Parametrized constant-depth quantum neuron.	CoRR	2022	DBLP BibTeX RDF
14	Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii	Constant-Depth Sorting Networks.	CoRR	2022	DBLP DOI BibTeX RDF
14	Nutan Limaye, Srikanth Srinivasan 0001, Sébastien Tavenas	Guest Column: Lower Bounds Against Constant-Depth Algebraic Circuits.	SIGACT News	2022	DBLP DOI BibTeX RDF
14	C. S. Bhargav, Sagnik Dutta, Nitin Saxena 0001	Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits.	MFCS	2022	DBLP DOI BibTeX RDF
14	Pooya Hatami, William Hoza, Avishay Tal, Roei Tell	Fooling Constant-Depth Threshold Circuits.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
14	Vincent Guigues, Anatoli B. Juditsky, Arkadi Nemirovski	Constant Depth Decision Rules for multistage optimization under uncertainty.	Eur. J. Oper. Res.	2021	DBLP DOI BibTeX RDF
14	Timon Barlag, Heribert Vollmer	A Logical Characterization of Constant-Depth Circuits over the Reals.	WoLLIC	2021	DBLP DOI BibTeX RDF
14	Pooya Hatami, William M. Hoza, Avishay Tal, Roei Tell	Fooling Constant-Depth Threshold Circuits (Extended Abstract).	FOCS	2021	DBLP DOI BibTeX RDF
14	Marco Carmosino, Kenneth Hoover, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova	Lifting for Constant-Depth Circuits and Applications to MCSP.	ICALP	2021	DBLP DOI BibTeX RDF
14	Rahul Ilango	Constant Depth Formula and Partial Function Versions of MCSP are Hard.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
14	Timon Barlag, Heribert Vollmer	A Logical Characterization of Constant-Depth Circuits over the Reals.	CoRR	2020	DBLP BibTeX RDF
14	Nolan J. Coble, Matthew Coudron	Quasi-polynomial Time Approximation of Output Probabilities of Constant-depth, Geometrically-local Quantum Circuits.	CoRR	2020	DBLP BibTeX RDF
14	Alexandru Paler, Oumarou Oumarou, Robert Basmadjian	Constant Depth Bucket Brigade Quantum RAM Circuits Without Introducing Ancillae.	CoRR	2020	DBLP BibTeX RDF
14	Ojas Parekh, Cynthia A. Phillips, Conrad D. James, James B. Aimone	Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication.	CoRR	2020	DBLP BibTeX RDF
14	Oded Goldreich 0001, Avishay Tal	On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.	Computational Complexity and Property Testing	2020	DBLP DOI BibTeX RDF
14	Russell Impagliazzo, Sasank Mouli, Toniann Pitassi	The Surprising Power of Constant Depth Algebraic Proofs.	LICS	2020	DBLP DOI BibTeX RDF
14	Rahul Ilango	Constant Depth Formula and Partial Function Versions of MCSP are Hard.	FOCS	2020	DBLP DOI BibTeX RDF
14	Roei Tell	Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials.	Comput. Complex.	2019	DBLP DOI BibTeX RDF
14	Russell Impagliazzo, Sasank Mouli, Toniann Pitassi	The Surprising Power of Constant Depth Algebraic Proofs.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF