The Shrinkage Exponent of de Morgan Formulas is 2
From MaRDI portal
Recommendations
Cited in
(60)- On covering graphs by complete bipartite subgraphs
- On the shrinkage exponent for read-once formulae
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- On the limits of gate elimination
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Fourier concentration from shrinkage
- Satisfiability algorithm for syntactic read-\(k\)-times branching programs
- Mining circuit lower bound proofs for meta-algorithms
- Circuit lower bounds from learning-theoretic approaches
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Uniform derandomization from pathetic lower bounds
- 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
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Sufficient conditions for the local repetition-freeness of minimal -schemes realizing linear Boolean functions
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- Correlation bounds and \#SAT algorithms for small linear-size circuits
- Smallest Formulas for Parity of 2 k Variables Are Essentially Unique
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- A stronger LP bound for formula size lower bounds via clique constraints
- Formulas versus Circuits for Small Distance Connectivity
- Complexity of the realization of a linear Boolean function in the class of -schemes
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- On uniformity and circuit lower bounds
- Tighter connections between Formula-SAT and shaving logs
- Small bias requires large formulas
- Pseudorandom functions: three decades later
- Hardness magnification near state-of-the-art lower bounds
- Quantified Derandomization: How to Find Water in the Ocean
- On the perfectness of minimal regular partitions of the edge set of the n-dimensional cube
- Torus polynomials: an algebraic approach to ACC lower bounds
- Cubic Formula Size Lower Bounds Based on Compositions with Majority
- Circuit lower bounds for MCSP from local pseudorandom generators
- Hardness magnification near state-of-the-art lower bounds
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- A super-quadratic lower bound for depth four arithmetic circuits
- scientific article; zbMATH DE number 7250155 (Why is no real title available?)
- Exploring the limits of subadditive approaches: parallels between optimization and complexity theory
- On the meaning of works by V. M. Khrapchenko
- Breaking the rectangle bound barrier against formula size lower bounds
- Representations of normalized formulas
- Natural proofs
- Improving \(3N\) circuit complexity lower bounds
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
- Capturing one-way functions via NP-hardness of meta-complexity
- Constructive separations and their consequences
- A nearly-4 n depth lower bound for formulas with restriction on top
- Towards stronger depth lower bounds
- Circuit depth reductions
- Shrinkage of decision lists and DNF formulas
- Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
- Toward better depth lower bounds: strong composition of XOR and a random function
- Negation-limited formulas
- On the complexity of hazard-free formulas
- Toward better depth lower bounds: two results on the multiplexor relation
- Solving sparse instances of Max SAT via width reduction and greedy restriction
- On convex complexity measures
- Smallest formulas for the parity of \(2^k\) variables are essentially unique
This page was built for publication: The Shrinkage Exponent of de Morgan Formulas is 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388862)
