Adventures in monotone complexity and TFNP
From MaRDI portal
(Redirected from Adventures in monotone complexity and TFNP)
Recommendations
- Complete problems for monotone NP
- Monotonicity and the Expressibility of NP Operators
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- The journey from NP to TFNP hardness
- scientific article; zbMATH DE number 176869
- Mathematical Foundations of Computer Science 2005
- scientific article; zbMATH DE number 4045141
- The complexity of monotone computations of polynomials
- On the mean complexity of monotone functions
- scientific article; zbMATH DE number 1342209
Cites work
- A characterization of span program size and improved lower bounds for monotone span programs
- A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
- Boolean function complexity. Advances and frontiers.
- Bounds on Monotone Switching Networks for Directed Connectivity
- Communication Complexity
- Communication complexity of correlated equilibrium with small support
- Communication lower bounds via critical block sensitivity
- Complexity theory, game theory, and economics: the Barbados lectures
- Cumulative space in black-white pebbling and resolution
- Dag-like communication and its applications
- Deterministic communication vs. partition number
- Hard examples for resolution
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- How easy is local search?
- scientific article; zbMATH DE number 6680986 (Why is no real title available?)
- scientific article; zbMATH DE number 3698383 (Why is no real title available?)
- scientific article; zbMATH DE number 176869 (Why is no real title available?)
- scientific article; zbMATH DE number 1114015 (Why is no real title available?)
- scientific article; zbMATH DE number 1114028 (Why is no real title available?)
- scientific article; zbMATH DE number 6783433 (Why is no real title available?)
- Lifting Nullstellensatz to monotone span programs over any field
- Linear gaps between degrees for the polynomial calculus modulo distinct primes
- Lower Bounds for Lovász–Schrijver Systems and Beyond Follow from Multiparty Communication Complexity
- Lower bounds on monotone complexity of the logical permanent
- Monotone circuit lower bounds from resolution
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- On extracting computations from propositional proofs (a survey)
- On the complexity of the parity argument and other inefficient proofs of existence
- On the polynomial parity argument complexity of the combinatorial Nullstellensatz
- On the virtue of succinct proofs
- On total functions, existence theorems and computational complexity
- Pseudorandom Generators in Propositional Proof Complexity
- Relations between communication complexity classes
- Separation of the monotone NC hierarchy
- Short proofs are narrow—resolution made simple
- Strongly exponential lower bounds for monotone computation
- Superpolynomial lower bounds for monotone span programs
- The communication complexity of local search
- The complexity of circuit value and network stability
- The complexity of satisfiability problems
- The complexity of the comparator circuit value problem
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The gap between monotone and non-monotone circuit complexity is exponential
- The landscape of communication complexity classes
- The relative complexity of NP search problems
- Tight bounds for monotone switching networks via Fourier analysis
- Unique end of potential line
- Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
Cited in
(18)- Nullstellensatz size-degree trade-offs from reversible pebbling
- A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
- scientific article; zbMATH DE number 7561747 (Why is no real title available?)
- Algorithms and lower bounds for comparator circuits from shrinkage
- Further collapses in \(\mathsf{TFNP}\)
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- Complete problems for monotone NP
- Algorithms and complexity for computing Nash equilibria in adversarial team games
- Total NP search problems with abundant solutions
- Intersection classes in TFNP and proof complexity
- TFNP intersections through the Lens of feasible disjunction
- Separations in proof complexity and TFNP
- On protocols for monotone feasible interpolation
- Some recent advancements in monotone circuit complexity (invited talk)
- Settling the complexity of Nash equilibrium in congestion games
- Iterated lower bound formulas: a diagonalization-based approach to proof complexity
- Searching for falsified clause in random ( n)-CNFs is hard for randomized communication
This page was built for publication: Adventures in monotone complexity and TFNP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090415)
