Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
DOI10.1137/15M1018319zbMath1359.68103OpenAlexW2588984325MaRDI QIDQ2968148
Avi Wigderson, Dmitry Gavinsky, Omri Weinstein, Or Meir
Publication date: 10 March 2017
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1018319
lower boundsinformation complexitycommunication complexityKarchmer-Wigderson relationsKRW conjecture
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
- Size-depth tradeoffs for Boolean formulae
- Communication complexity towards lower bounds on circuit depth
- Graph products, Fourier analysis and spectral techniques
- Top-down lower bounds for depth-three circuits
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Applications of matrix methods to the theory of lower bounds in computational complexity
- How to Compress Interactive Communication
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Applications of product colouring
- Monotone circuits for matching require linear depth
- The Shrinkage Exponent of de Morgan Formulas is 2
- The Parallel Evaluation of General Arithmetic Expressions
- The effect of random restrictions on formula size
- Shrinkage of de Morgan formulae under restriction
- Fractional Covers and Communication Complexity
- Toward better formula lower bounds
- Natural proofs
- The Erdős-Ko-Rado theorem for integer sequences
This page was built for publication: Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
