Mining circuit lower bound proofs for meta-algorithms
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3133387 (Why is no real title available?)
- scientific article; zbMATH DE number 3162894 (Why is no real title available?)
- scientific article; zbMATH DE number 4012495 (Why is no real title available?)
- scientific article; zbMATH DE number 4031582 (Why is no real title available?)
- scientific article; zbMATH DE number 3730059 (Why is no real title available?)
- scientific article; zbMATH DE number 3759547 (Why is no real title available?)
- scientific article; zbMATH DE number 1142303 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 806753 (Why is no real title available?)
- scientific article; zbMATH DE number 1405644 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- A Greedy Heuristic for the Set-Covering Problem
- A Pseudorandom Generator from any One-way Function
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Approximation algorithms for combinatorial problems
- Average-case lower bounds for formula size
- Boolean function complexity. Advances and frontiers.
- Circuit minimization problem
- Circuit-size lower bounds and non-reducibility to sparse sets
- Computational Complexity
- Constant depth circuits, Fourier transform, and learnability
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Easiness assumptions and hardness tests: Trading time for zero error
- Efficient Learning Algorithms Yield Circuit Lower Bounds
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Hardness vs randomness
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Improving exhaustive search implies superpolynomial lower bounds
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Invertible zero-error dispersers and defective memory with stuck-at errors
- Learning and lower bounds for AC\(^{0}\) with threshold gates
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
- Natural proofs
- On derandomization and average-case complexity of monotone functions
- On the ratio of optimal integral and fractional covers
- Parity, circuits, and the polynomial-time hierarchy
- Polylogarithmic independence can fool DNF formulas
- Polylogarithmic independence fools \(\mathrm{AC}^{0}\) circuits
- Pseudorandom generators without the XOR lemma
- Pseudorandomness from shrinkage
- Quadratic Goldreich-Levin theorems
- Shrinkage of de Morgan formulae under restriction
- Simple Constructions of Almost k-wise Independent Random Variables
- The Shrinkage Exponent of de Morgan Formulas is 2
- The complexity of monotone boolean functions
- The complexity of satisfiability of small depth circuits
- The complexity of theorem-proving procedures
Cited in
(34)- Fourier concentration from shrinkage
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Tighter connections between Formula-SAT and shaving logs
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- Strong ETH and resolution via games and the multiplicity of strategies
- Algorithms and lower bounds for comparator circuits from shrinkage
- Agnostic Learning from Tolerant Natural Proofs
- A moderately exponential time algorithm for k-IBDD satisfiability
- Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
- Agnostic membership query learning with nontrivial savings: new results and techniques
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Negation-limited formulas
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- On the complexity of compressing obfuscation
- Improving \(3N\) circuit complexity lower bounds
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Zero-fixing extractors for sub-logarithmic entropy
- Cubic Formula Size Lower Bounds Based on Compositions with Majority
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Proofs of Work from worst-case assumptions
- Local enumeration and majority lower bounds
- Circuit lower bounds from learning-theoretic approaches
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability
- What circuit classes can be learned with non-trivial savings?
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Towards stronger depth lower bounds
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- Improved algorithms for sparse MAX-SAT and MAX-k-CSP
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Satisfiability algorithms and lower bounds for Boolean formulas over finite bases
- Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
- Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression
- Improved exact algorithms for mildly sparse instances of MAX SAT
This page was built for publication: Mining circuit lower bound proofs for meta-algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2351392)
