Nonuniform ACC Circuit Lower Bounds
From MaRDI portal
Publication:3189637
DOI10.1145/2559903zbMath1295.68117OpenAlexW2083820240MaRDI QIDQ3189637
Publication date: 12 September 2014
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2559903
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Circuit lower bounds from learning-theoretic approaches ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Local expanders ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Skew circuits of small width ⋮ Dual VP classes ⋮ Computing the best-case energy complexity of satisfying assignments in monotone circuits ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Effective guessing has unlikely consequences ⋮ Unnamed Item ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Substitution Principle and semidirect products ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Unnamed Item ⋮ New algorithms and lower bounds for circuits with linear threshold gates ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Unnamed Item ⋮ Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Unifying known lower bounds via geometric complexity theory ⋮ Average-case rigidity lower bounds ⋮ Upper bound for torus polynomials ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A lower bound for depth-3 circuits with MOD \(m\) gates
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- On uniformity and circuit lower bounds
- On O(Tlog T) reduction from RAM computations to satisfiability
- How to multiply matrices faster
- Non-uniform automata over groups
- NP is as easy as detecting unique solutions
- The monotone circuit complexity of Boolean functions
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Short propositional formulas represent nondeterministic computations
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- On the computational power of depth-2 circuits with threshold and modulo gates
- Fast rectangular matrix multiplication and applications
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Exponential size lower bounds for some depth three circuits
- Hardness vs randomness
- On ACC
- A note on a theorem of Barrington, Straubing and Thérien
- Rectangular matrix multiplication revisited
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Superlinear lower bounds for bounded-width branching programs
- A circuit-based proof of Toda's theorem
- Constant width planar computation characterizes ACC\(^{0}\)
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Algebrization
- NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Parity, circuits, and the polynomial-time hierarchy
- Circuit-size lower bounds and non-reducibility to sparse sets
- PP is as Hard as the Polynomial-Time Hierarchy
- Time-space lower bounds for satisfiability
- Set Partitioning via Inclusion-Exclusion
- The Complexity of Satisfiability of Small Depth Circuits
- Rapid Multiplication of Rectangular Matrices
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Satisfiability Is Quasilinear Complete in NQL
- Separating Nondeterministic Time Complexity Classes
- An algorithm for the satisfiability problem of formulas in conjunctive normal form
- A note on succinct representations of graphs
- Lower Bounds for (MODp - MODm) Circuits
- Linear Systems over Composite Moduli
- Explicit lower bound of 4.5n - o(n) for boolena circuits
- Computational Complexity
- Natural proofs
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Time-space tradeoffs for SAT on nonuniform machines
