Mean-payoff games and propositional proofs
From MaRDI portal
Publication:716324
DOI10.1016/j.ic.2011.01.003zbMath1237.91043OpenAlexW1978132353MaRDI QIDQ716324
Albert Atserias, Elitza Maneva
Publication date: 28 April 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.01.003
Related Items (4)
Tropically convex constraint satisfaction ⋮ Parity Games and Propositional Proofs ⋮ The canonical pairs of bounded depth Frege systems ⋮ Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Combinatorial structure and randomized subexponential algorithms for infinite games
- Matching theory
- Positional strategies for mean payoff games
- A characterization of the minimum cycle mean in a digraph
- The complexity of mean payoff games on graphs
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- On reducibility and symmetry of disjoint NP pairs.
- Non-automatizability of bounded-depth Frege proofs
- Lower bounds for the weak pigeonhole principle and random formulas beyond resolution
- On the automatizability of resolution and related propositional proof systems
- Parity, circuits, and the polynomial-time hierarchy
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Mean-Payoff Games and Propositional Proofs
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Lower bounds for cutting planes proofs with small coefficients
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Short proofs are narrow—resolution made simple
- On Interpolation and Automatization for Frege Systems
- Scheduling with AND/OR Precedence Constraints
- The Max-Atom Problem and Its Relevance
This page was built for publication: Mean-payoff games and propositional proofs
