Algebraic methods in the theory of lower bounds for Boolean circuit complexity

No abstract is available for this paper.

• Publication year

  1987

• Venue

  Symposium on the Theory of Computing

• Publication date

  1987-01-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/28395.28404
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹

  1989cited by this paper
• Almost optimal lower bounds for small depth circuits

  1986cited by this paper
• Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

  1986cited by this paper
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

  1986cited by this paper
• Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions

  1985cited by this paper
• Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version)

  1985cited by this paper
• ∑11-Formulae on finite structures

  1983cited by this paper
• Parity, circuits, and the polynomial-time hierarchy

  1981cited by this paper

• QAC0 Contains TC0 (with Many Copies of the Input)

  2026cites this paper
• Rational Transductors

  2026cites this paper
• Convergent Gate Elimination and Constructive Circuit Lower Bounds

  2026cites this paper
• Lifting to Bounded-Depth and Regular Resolutions over Parities via Games

  2025cites this paper
• Sparsity Lower Bounds for Probabilistic Polynomials

  2025cites this paper
• Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals

  2025cites this paper
• Strong Pseudorandom Functions in AC0[2] in the Bounded-Query Setting

  2025cites this paper
• #SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

  2025cites this paper
• New Bounds for the Ideal Proof System in Positive Characteristic

  2025cites this paper
• Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations

  2025cites this paper
• Complexity of Minimal Faithful Permutation Degree for Fitting-free Groups

  2025cites this paper
• Linear-Size QAC0 Channels: Learning, Testing and Hardness

  2025cites this paper
• SoK: On Shallow Weak PRFs A Common Symmetric Building Block for MPC Protocols

  2025cites this paper
• Doubly-polylog-time-overhead fault-tolerant quantum computation by a polylog-time parallel minimum-weight perfect matching decoder

  2025cites this paper
• Leakage-Resilient Circuits against NC1, Revisited

  2025cites this paper
• Generative Artificial Intelligence: Evolving Technology, Growing Societal Impact, and Opportunities for Information Systems Research

  2025cites this paper
• Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification

  2025cites this paper
• Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?)

  2025cites this paper
• Languages of Words of Low Automatic Complexity Are Hard to Compute

  2025cites this paper
• Quantum circuit lower bounds in the magic hierarchy

  2025cites this paper
• Generative Artificial Intelligence: Evolving Technology, Growing Societal Impact, and Opportunities for Information Systems Research

  2025cites this paper
• Amortized Closure and Its Applications in Lifting for Resolution over Parities

  2025cites this paper
• Improved Lower Bounds for QAC0

  2025cites this paper
• The regular multivariate quadratic problem

  2025cites this paper
• Total Search Problems in ZPP

  2025cites this paper
• Supercritical Tradeoff Between Size and Depth for Resolution over Parities

  2025cites this paper
• Lower Bounds Beyond DNF of Parities

  2025cites this paper
• AC0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard

  2025cites this paper
• Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

  2024cites this paper
• On the Power of Interactive Proofs for Learning

  2024cites this paper
• Monomial Boolean functions with large high-order nonlinearities

  2024cites this paper
• Improved Alternating Moduli PRFs and Post-Quantum Signatures

  2024cites this paper
• Quantum Threshold is Powerful

  2024cites this paper
• Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)

  2024cites this paper
• Mastering NIM and Impartial Games with Weak Neural Networks: An AlphaZero-inspired Multi-Frame Approach

  2024cites this paper
• Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits

  2024cites this paper
• Fine-Grained Non-interactive Key-Exchange Without Idealized Assumptions

  2024cites this paper
• On the Computational Power of QAC0 with Barely Superlinear Ancillae

  2024cites this paper
• Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

  2024cites this paper
• How Numerical Precision Affects Arithmetical Reasoning Capabilities of LLMs

  2024cites this paper
• Formula Size-Depth Tradeoffs for Iterated Sub-permutation Matrix Multiplication

  2024cites this paper
• Lifting to regular resolution over parities via games

  2024cites this paper
• Fine-grained polynomial functional encryption

  2024cites this paper
• Towards ACC Lower Bounds using Torus Polynomials

  2024cites this paper
• Hilbert Functions and Low-Degree Randomness Extractors

  2024influential citation
• Improved Circuit Lower Bounds and Quantum-Classical Separations

  2024influential citation
• Low-Depth Algebraic Circuit Lower Bounds over Any Field

  2024cites this paper
• Solving Polynomial Equations Over Finite Fields

  2024influential citation
• The power of shallow-depth Toffoli and qudit quantum circuits

  2024cites this paper
• Low-degree approximation of QAC0 circuits

  2024influential citation
• On the Constant-Depth Circuit Complexity of Generating Quasigroups

  2024cites this paper
• From Proof Complexity to Circuit Complexity via Interactive Protocols

  2024cites this paper
• Lower Bounds for Regular Resolution over Parities

  2024cites this paper
• Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank Under NSETH and Beyond

  2024cites this paper
• Learning Circuit Complexity of Boolean Functions

  2024cites this paper
• Constant Depth Circuit Complexity for Generating Quasigroups

  2024cites this paper
• Dot-Product Proofs and Their Applications

  2024cites this paper
• Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

  2024cites this paper
• Generation of small complexity classes using logical formulas, schemes and operations of bounded concatenation

  2023cites this paper
• SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle

  2023cites this paper
• Noisy decoding by shallow circuits with parities: classical and quantum

  2023cites this paper
• Dynamic Complexity of Regular Languages: Big Changes, Small Work

  2023influential citation
• Violating Constant Degree Hypothesis Requires Breaking Symmetry

  2023cites this paper
• Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques

  2023cites this paper
• Unconditional Quantum Advantage for Sampling with Shallow Circuits

  2023cites this paper
• A Technique for Hardness Amplification Against $\mathrm{AC}^0$

  2023cites this paper
• Depth-3 Circuit Lower Bounds for k-OV

  2023cites this paper
• Extended Nullstellensatz proof systems

  2023cites this paper
• Parity vs. AC0 with simple quantum preprocessing

  2023cites this paper
• On Representation Complexity of Model-based and Model-free Reinforcement Learning

  2023cites this paper
• Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates

  2023cites this paper
• MidBit+, Torus Polynomials and Non-classical Polynomials: Equivalences for ACC Lower Bounds

  2023cites this paper
• Near-Optimal Set-Multilinear Formula Lower Bounds

  2023cites this paper
• Fine-Grained Secure Attribute-Based Encryption

  2023cites this paper
• Distributional PAC-Learning from Nisan's Natural Proofs

  2023cites this paper
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

  2023cites this paper
• On teaching the approximation method for circuit lower bounds

  2023cites this paper
• Lower Bounds for Constant Depth Algebraic Circuits

  2023cites this paper
• Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler-Leman

  2023cites this paper
• NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach

  2023cites this paper
• Efficient Interactive Proofs for Non-Deterministic Bounded Space

  2023influential citation
• Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle?

  2023cites this paper
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs

  2023cites this paper
• An Algorithmic Approach to Uniform Lower Bounds

  2023cites this paper
• On correlation bounds against polynomials

  2023cites this paper
• Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system

  2023cites this paper
• Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms

  2023cites this paper
• Depth-𝑑 Threshold Circuits vs. Depth-(𝑑+1) AND-OR Trees

  2023cites this paper
• Optimal Explicit Small-Depth Formulas for the Coin Problem

  2023cites this paper
• Average-Case PAC-Learning from Nisan's Natural Proofs

  2023cites this paper
• A Study of Sparse Representation of Boolean Functions

  2023cites this paper
• Sampling and Certifying Symmetric Functions

  2023cites this paper
• Fourier Growth of Communication Protocols for XOR Functions

  2023cites this paper
• Tight Correlation Bounds for Circuits Between AC0 and TC0

  2023cites this paper
• Top-Down Lower Bounds for Depth-Four Circuits

  2023cites this paper
• Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic

  2023cites this paper
• New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method

  2022cites this paper
• Correlation bounds against polynomials

  2022cites this paper
• Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

  2022cites this paper
• Count-Free Weisfeiler-Leman and Group Isomorphism

  2022cites this paper