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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (43)
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
This page was built for publication: Nonuniform ACC Circuit Lower Bounds