The Shrinkage Exponent of de Morgan Formulas is 2
From MaRDI portal
Publication:4388862
DOI10.1137/S0097539794261556zbMath0907.68107OpenAlexW2005223599MaRDI QIDQ4388862
Publication date: 10 May 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794261556
Related Items (46)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ On the limits of gate elimination ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Sufficient conditions for the local repetition-freeness of minimal π-schemes realizing linear Boolean functions ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Complexity of the Realization of a Linear Boolean Function in the Class of π-Schemes ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ On the perfectness of minimal regular partitions of the edge set of the $n$-dimensional cube ⋮ Uniform derandomization from pathetic lower bounds ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Smallest Formulas for Parity of 2 k Variables Are Essentially Unique ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Unnamed Item ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ A stronger LP bound for formula size lower bounds via clique constraints ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ Unnamed Item ⋮ On uniformity and circuit lower bounds ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ On convex complexity measures ⋮ Fourier concentration from shrinkage ⋮ Smallest formulas for the parity of \(2^k\) variables are essentially unique ⋮ Natural proofs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Negation-limited formulas ⋮ Unnamed Item ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ On covering graphs by complete bipartite subgraphs ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Toward better depth lower bounds: two results on the multiplexor relation ⋮ Pseudorandom Functions: Three Decades Later ⋮ Mining circuit lower bound proofs for meta-algorithms
This page was built for publication: The Shrinkage Exponent of de Morgan Formulas is 2
