Dag-like communication and its applications
From MaRDI portal
Publication:2399382
DOI10.1007/978-3-319-58747-9_26zbMath1489.68099OpenAlexW2583114560MaRDI QIDQ2399382
Publication date: 22 August 2017
Full work available at URL: https://doi.org/10.1007/978-3-319-58747-9_26
Applications of game theory (91A80) Complexity of proofs (03F20) Communication complexity, information complexity (68Q11)
Related Items (7)
Dag-like communication and its applications ⋮ A note on monotone real circuits ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ Adventures in monotone complexity and TFNP ⋮ Unnamed Item ⋮ Reflections on Proof Complexity and Counting Principles
Cites Work
- The monotone circuit complexity of Boolean functions
- An exponential lower bound for the size of monotone real circuits
- Separation of the monotone NC hierarchy
- Dag-like communication and its applications
- On extracting computations from propositional proofs (a survey).
- FRAGMENTS OF APPROXIMATE COUNTING
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Interpolation by a Game
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Strongly exponential lower bounds for monotone computation
- Communication lower bounds via critical block sensitivity
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
- On the virtue of succinct proofs
This page was built for publication: Dag-like communication and its applications
