Pages that link to "Item:Q3189637"
From MaRDI portal
The following pages link to Nonuniform ACC Circuit Lower Bounds (Q3189637):
Displaying 44 items.
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability (Q722517) (← links)
- Solving sparse instances of Max SAT via width reduction and greedy restriction (Q905695) (← links)
- Local expanders (Q1653336) (← links)
- Gate elimination: circuit size lower bounds and \#SAT upper bounds (Q1704573) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- Average-case rigidity lower bounds (Q2117087) (← links)
- Upper bound for torus polynomials (Q2117095) (← links)
- A \#SAT algorithm for small constant-depth circuits with PTF gates (Q2118395) (← links)
- Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case (Q2151382) (← links)
- Skew circuits of small width (Q2173307) (← links)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs (Q2281256) (← links)
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression (Q2316930) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- Dual VP classes (Q2410687) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- Computing the best-case energy complexity of satisfying assignments in monotone circuits (Q2674710) (← links)
- Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms (Q2701071) (← links)
- Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074) (← links)
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (Q4568115) (← links)
- New algorithms and lower bounds for circuits with linear threshold gates (Q4612481) (← links)
- (Q4612482) (← links)
- (Q4638059) (← links)
- (Q5002674) (← links)
- (Q5005112) (← links)
- (Q5005182) (← links)
- From Circuit Complexity to Faster All-Pairs Shortest Paths (Q5009891) (← links)
- (Q5028364) (← links)
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization (Q5080481) (← links)
- (Q5090385) (← links)
- (Q5090396) (← links)
- Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle (Q5090435) (← links)
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity (Q5091770) (← links)
- Hardness magnification near state-of-the-art lower bounds (Q5091779) (← links)
- Algorithms and lower bounds for de morgan formulas of low-communication leaf gates (Q5092464) (← links)
- A super-quadratic lower bound for depth four arithmetic circuits (Q5092474) (← links)
- (Q5121894) (← links)
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)
- Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs (Q5136279) (← links)
- Efficient Construction of Rigid Matrices Using an NP Oracle (Q5863325) (← links)
- Algorithms and lower bounds for comparator circuits from shrinkage (Q6107895) (← links)
- Effective guessing has unlikely consequences (Q6109068) (← links)
- Improving \(3N\) circuit complexity lower bounds (Q6184294) (← links)
- Substitution Principle and semidirect products (Q6190406) (← links)
- Rigid matrices from rectangular PCPs (Q6491304) (← links)
