Skip header Section
Skip Bibliometrics Section
Computational limitations of small-depth circuitsJanuary 1987
- Author:
- Johan Håstad
Abstract
No abstract available.
Cited By
- Creiner A and Jackson S (2023). Borel complexity and Ramsey largeness of sets of oracles separating complexity classes, Mathematical Logic Quarterly, 69:3, (267-286), Online publication date: 28-Aug-2023.
- Viola E New Sampling Lower Bounds via the Separator Proceedings of the conference on Proceedings of the 38th Computational Complexity Conference, (1-23)
- Hirahara S and Nanashima M Finding errorless pessiland in error-prone heuristica Proceedings of the 37th Computational Complexity Conference, (1-28)
- Aaronson S, Ingram D and Kretschmer W The acrobatics of BQP Proceedings of the 37th Computational Complexity Conference, (1-17)
- Lecomte V, Ramakrishnan P and Tan L The composition complexity of majority Proceedings of the 37th Computational Complexity Conference, (1-26)
- Aceto L, Achilleos A, Anastasiadi E and Francalanza A Monitoring Hyperproperties with Circuits Formal Techniques for Distributed Objects, Components, and Systems, (1-10)
- Oliveira I, Santhanam R and Tell R (2022). Expander-Based Cryptography Meets Natural Proofs, Computational Complexity, 31:1, Online publication date: 1-Jun-2022.
- Hitchcock J, Sekoni A and Shafei H (2021). Polynomial-Time Random Oracles and Separating Complexity Classes, ACM Transactions on Computation Theory, 13:1, (11-16), Online publication date: 1-Mar-2021.
- Nachum I and Yehudayoff A On Symmetry and Initialization for Neural Networks LATIN 2020: Theoretical Informatics, (401-412)
- Chen M, Bai Y, Lee J, Zhao T, Wang H, Xiong C and Socher R Towards understanding hierarchical learning Proceedings of the 34th International Conference on Neural Information Processing Systems, (22134-22145)
- Abbe E and Sandon C On the universality of deep learning Proceedings of the 34th International Conference on Neural Information Processing Systems, (20061-20072)
- Beyersdorff O, Chew L and Janota M (2019). New Resolution-Based QBF Calculi and Their Proof Complexity, ACM Transactions on Computation Theory, 11:4, (1-42), Online publication date: 17-Sep-2019.
- Allender E and Hirahara S (2019). New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems, ACM Transactions on Computation Theory, 11:4, (1-27), Online publication date: 17-Sep-2019.
- Beyersdorff O, Chew L and Sreenivasaiah K (2019). A game characterisation of tree-like Q-Resolution size, Journal of Computer and System Sciences, 104:C, (82-101), Online publication date: 1-Sep-2019.
- Chen L and Tell R Bootstrapping results for threshold circuits “just beyond” known lower bounds Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, (34-41)
- Lovett S and Zhang J DNF sparsification beyond sunflowers Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, (454-460)
- Poggio T, Mhaskar H, Rosasco L, Miranda B and Liao Q (2017). Why and when can deep-but not shallow-networks avoid the curse of dimensionality, International Journal of Automation and Computing, 14:5, (503-519), Online publication date: 1-Oct-2017.
- Haramaty E, Lee C and Viola E Bounded independence plus noise fools products Proceedings of the 32nd Computational Complexity Conference, (1-30)
- Tell R Improved bounds for quantified derandomization of constant-depth circuits and polynomials Proceedings of the 32nd Computational Complexity Conference, (1-48)
- Chattopadhyay E and Li X Non-malleable codes and extractors for small-depth circuits, and affine functions Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (1171-1184)
- Gasarch W (2017). Open Problems Column, ACM SIGACT News, 48:2, (34-39), Online publication date: 12-Jun-2017.
- Viola E (2017). Selected challenges in computational lower bounds, ACM SIGACT News, 48:1, (39-45), Online publication date: 10-Mar-2017.
- Rudolph S (2017). Succinctness and tractability of closure operator representations, Theoretical Computer Science, 658:PB, (327-345), Online publication date: 7-Jan-2017.
- Kane D and Watanabe O (2016). A Short Implicant of a CNF Formula with Many Satisfying Assignments, Algorithmica, 76:4, (1203-1223), Online publication date: 1-Dec-2016.
- Gopalan P, Servedio R and Wigderson A Degree and sensitivity Proceedings of the 31st Conference on Computational Complexity, (1-23)
- Srivastava R, Greff K and Schmidhuber J Training very deep networks Proceedings of the 29th International Conference on Neural Information Processing Systems - Volume 2, (2377-2385)
- Rossman B, Servedio R and Tan L (2015). Complexity Theory Column 89, ACM SIGACT News, 46:4, (50-68), Online publication date: 1-Dec-2015.
- Viola E (2015). The communication complexity of addition, Combinatorica, 35:6, (703-747), Online publication date: 1-Dec-2015.
- Filmus Y, Pitassi T and Santhanam R (2015). Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, ACM Transactions on Computation Theory, 7:2, (1-16), Online publication date: 11-May-2015.
- Hemaspaandra L (2014). Beautiful structures, ACM SIGACT News, 45:3, (54-70), Online publication date: 17-Sep-2014.
- Rossman B Formulas vs. circuits for small distance connectivity Proceedings of the forty-sixth annual ACM symposium on Theory of computing, (203-212)
- Fournier H, Limaye N, Malod G and Srinivasan S Lower bounds for depth 4 formulas computing iterated matrix multiplication Proceedings of the forty-sixth annual ACM symposium on Theory of computing, (128-135)
- Akavia A, Bogdanov A, Guo S, Kamath A and Rosen A Candidate weak pseudorandom functions in AC0 ○ MOD2 Proceedings of the 5th conference on Innovations in theoretical computer science, (251-260)
- Chattopadhyay A, Torán J and Wagner F (2013). Graph Isomorphism is Not AC0-Reducible to Group Isomorphism, ACM Transactions on Computation Theory, 5:4, (1-13), Online publication date: 1-Nov-2013.
- Viola E The communication complexity of addition Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, (632-651)
- Impagliazzo R, Matthews W and Paturi R A satisfiability algorithm for AC0 Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms, (961-972)
- Fefferman B, Shaltiel R, Umans C and Viola E On beating the hybrid argument Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, (468-483)
- Aaronson S and Arkhipov A The computational complexity of linear optics Proceedings of the forty-third annual ACM symposium on Theory of computing, (333-342)
- Gopalan P and Servedio R Learning and lower bounds for AC0 with threshold gates Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques, (588-601)
- Aaronson S BQP and the polynomial hierarchy Proceedings of the forty-second ACM symposium on Theory of computing, (141-150)
- Allender E and Koucký M (2010). Amplifying lower bounds by means of self-reducibility, Journal of the ACM, 57:3, (1-36), Online publication date: 1-Mar-2010.
- Kinne J, Melkebeek D and Shaltiel R Pseudorandom Generators and Typically-Correct Derandomization Proceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (574-587)
- Viola E (2009). Guest Column, ACM SIGACT News, 40:1, (27-44), Online publication date: 28-Feb-2009.
- Ré C and Suciu D (2008). Approximate lineage for probabilistic databases, Proceedings of the VLDB Endowment, 1:1, (797-808), Online publication date: 1-Aug-2008.
- Allender E Cracks in the defenses Proceedings of the 3rd international conference on Computer science: theory and applications, (3-10)
- Shaltiel R and Viola E Hardness amplification proofs require majority Proceedings of the fortieth annual ACM symposium on Theory of computing, (589-598)
- Hansen K Computing symmetric boolean functions by circuits with few exact threshold gates Proceedings of the 13th annual international conference on Computing and Combinatorics, (448-458)
- O'Donnell R and Wimmer K Approximation by DNF Proceedings of the 34th international conference on Automata, Languages and Programming, (195-206)
- Kołodziejczyk L and Thapen N The Polynomial and Linear Hierarchies in V0 Proceedings of the 3rd conference on Computability in Europe: Computation and Logic in the Real World, (408-415)
- Tarui J Finding a duplicate and a missing item in a stream Proceedings of the 4th international conference on Theory and applications of models of computation, (128-135)
- Bengio Y, Lamblin P, Popovici D and Larochelle H Greedy layer-wise training of deep networks Proceedings of the 20th International Conference on Neural Information Processing Systems, (153-160)
- Atıcı A and Servedio R Learning unions of ω(1)-dimensional rectangles Proceedings of the 17th international conference on Algorithmic Learning Theory, (32-47)
- Spakowski H and Tripathi R Hierarchical unambiguity Proceedings of the 31st international conference on Mathematical Foundations of Computer Science, (777-788)
- Gál A and Trifonov V On the correlation between parity and modular polynomials Proceedings of the 31st international conference on Mathematical Foundations of Computer Science, (387-398)
- Dubrov B and Ishai Y On the randomness complexity of efficient sampling Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing, (711-720)
- Hitchcock J (2006). Hausdorff dimension and oracle constructions, Theoretical Computer Science, 355:3, (382-388), Online publication date: 14-Apr-2006.
- Healy A and Viola E Constant-Depth circuits for arithmetic in finite fields of characteristic two Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer Science, (672-683)
- Spakowski H and Tripathi R On the power of unambiguity in alternating machines Proceedings of the 15th international conference on Fundamentals of Computation Theory, (125-136)
- Chattopadhyay A and Hansen K Lower bounds for circuits with few modular and symmetric gates Proceedings of the 32nd international conference on Automata, Languages and Programming, (994-1005)
- Miltersen P The computational complexity of one-dimensional sandpiles Proceedings of the First international conference on Computability in Europe: new Computational Paradigms, (342-348)
- Jackson J, Klivans A and Servedio R Learnability beyond AC0 Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, (776-784)
- Beigel R and Maciel A Upper and Lower Bounds for Some Depth-3 Circuit Classes Proceedings of the 12th Annual IEEE Conference on Computational Complexity
- Berg C and Ulfberg S A Lower Bound For Perceptrons And An Oracle Separation Of The PP/sup PH/ Hierarchy Proceedings of the 12th Annual IEEE Conference on Computational Complexity
- Cai L, Chen J and Hastad J Circuit Bottom Fan-in and Computational Power Proceedings of the 12th Annual IEEE Conference on Computational Complexity
- Hemaspaandra L, Ramachandran A and Zimand M (1995). Worlds to die for, ACM SIGACT News, 26:4, (5-15), Online publication date: 1-Dec-1995.
- Mansour Y (1995). An O(nlog log n) Learning Algorithm for DNF under the Uniform Distribution, Journal of Computer and System Sciences, 50:3, (543-550), Online publication date: 1-Jun-1995.
- Teng S (1994). Functional inversion and communication complexity, Journal of Cryptology, 7:3, (153-170), Online publication date: 1-Sep-1994.
- Goldberg L, Jerrum M and MacKenzie P An Ω(√ log log n) lower bound for routing in optical networks Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, (147-156)
- Hemaspaandra L (1994). Complexity theory column 5, ACM SIGACT News, 25:2, (5-10), Online publication date: 1-Jun-1994.
- Mansour Y An O(n) learning algorithm for DNF under the uniform distribution Proceedings of the fifth annual workshop on Computational learning theory, (53-61)
- Kharitonov M Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution Proceedings of the fifth annual workshop on Computational learning theory, (29-36)
- Sipser M The history and status of the P versus NP question Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing, (603-618)
- Beame P, Impagliazzo R, Krajíček J, Pitassi T, Pudlák P and Woods A Exponential lower bounds for the pigeonhole principle Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing, (200-220)
- Ko K Relativized polynomial time hierarchies having exactly K levels Proceedings of the twentieth annual ACM symposium on Theory of computing, (245-253)
Index Terms
- Computational limitations of small-depth circuits
Please enable JavaScript to view thecomments powered by Disqus.
Recommendations
The Complexity of Computational Circuits Versus Radix
The complexity of computational circuits versus radix is analyzed. Necessary and sufficient conditions are given that ensure that the complexity of certain computational circuits will be a monotonically decreasing function of radix. Mechanizations of a ...
Matroids with many small circuits and cocircuits
AbstractTutte proved that a non-empty 3-connected matroid with every element in a 3-element circuit and a 3-element cocircuit is either a whirl or the cycle matroid of a wheel. This result led to the Splitter Theorem. More recently, Miller ...
Lower Bounds for Depth-Three Arithmetic Circuits with small bottom fanin
Shpilka & Wigderson (IEEE conference on computational complexity, vol 87, 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth-three arithmetic circuits with bounded bottom fanin over a field $${{\mathbb{F}}}$$F of ...