Adventures in monotone complexity and TFNP
From MaRDI portal
Publication:5090415
DOI10.4230/LIPIcs.ITCS.2019.38OpenAlexW2914732100MaRDI QIDQ5090415
No author found.
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2019.38
Related Items (3)
Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- Relations between communication complexity classes
- On total functions, existence theorems and computational complexity
- Lower bounds on monotone complexity of the logical permanent
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- How easy is local search?
- The complexity of circuit value and network stability
- The relative complexity of NP search problems
- On the complexity of the parity argument and other inefficient proofs of existence
- A characterization of span program size and improved lower bounds for monotone span programs
- The gap between monotone and non-monotone circuit complexity is exponential
- Superpolynomial lower bounds for monotone span programs
- Separation of the monotone NC hierarchy
- Communication complexity of approximate Nash equilibria
- Unique end of potential line
- Dag-like communication and its applications
- The complexity of the comparator circuit value problem
- On extracting computations from propositional proofs (a survey).
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Hard examples for resolution
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Short proofs are narrow—resolution made simple
- Deterministic Communication vs. Partition Number
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
- The Landscape of Communication Complexity Classes.
- Cumulative Space in Black-White Pebbling and Resolution
- Bounds on Monotone Switching Networks for Directed Connectivity
- Pseudorandom Generators in Propositional Proof Complexity
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
- Communication Complexity
- Strongly exponential lower bounds for monotone computation
- The communication complexity of local search
- Monotone circuit lower bounds from resolution
- Lifting Nullstellensatz to monotone span programs over any field
- Communication lower bounds via critical block sensitivity
- The complexity of satisfiability problems
- On the virtue of succinct proofs
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
This page was built for publication: Adventures in monotone complexity and TFNP
