On the complexity of the parity argument and other inefficient proofs of existence
From MaRDI portal
Publication:1329155
DOI10.1016/S0022-0000(05)80063-7zbMath0806.68048WikidataQ56138406 ScholiaQ56138406MaRDI QIDQ1329155
Publication date: 13 February 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (only showing first 100 items - show all)
The NP Search Problems of Frege and Extended Frege Proofs ⋮ Inapproximability of Nash Equilibrium ⋮ On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ TFNP: An Update ⋮ When the Players Are Not Expectation Maximizers ⋮ A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria ⋮ Settling Some Open Problems on 2-Player Symmetric Nash Equilibria ⋮ The Journey from NP to TFNP Hardness ⋮ On Solving Systems of Diagonal Polynomial Equations Over Finite Fields ⋮ Approximate counting and NP search problems ⋮ A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ A survey of mass partitions ⋮ The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form ⋮ Computation of Dynamic Equilibria in Series-Parallel Networks ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ NP-completeness: A retrospective ⋮ The Exact Computational Complexity of Evolutionarily Stable Strategies ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ The complexity of searching implicit graphs ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Public goods games in directed networks ⋮ Faster algorithms for \(k\)-\textsc{Subset Sum} and variations ⋮ A CSP-Based Approach for Solving Parity Game ⋮ On finding constrained independent sets in cycles ⋮ Total functions in QMA ⋮ Non-interactive universal arguments ⋮ Multilinear Games ⋮ Fixed-Parameter Algorithms for the Kneser and Schrijver Problems ⋮ $$\mathcal {NP}$$-Hardness of Equilibria in Case of Risk-Averse Players ⋮ Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Euler Complexes ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Many-one reductions and the category of multivalued functions ⋮ Unnamed Item ⋮ Approximating Tverberg points in linear time for any fixed dimension ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ ARRIVAL: Next Stop in CLS ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ Some Tractable Win-Lose Games ⋮ The complexity of searching succinctly represented graphs ⋮ The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Complexity of equilibria in first-price auctions under general tie-breaking rules ⋮ New and simple algorithms for stable flow problems ⋮ Unnamed Item ⋮ Decomposable obfuscation: a framework for building applications of obfuscation from polynomial hardness ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ Approximating subset sum ratio via partition computations ⋮ Further collapses in \(\mathsf{TFNP}\) ⋮ Minimal and Hyper-Minimal Biautomata ⋮ The complexity of iterated reversible computation ⋮ The complexity of gradient descent: CLS = PPAD \(\cap\) pls ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 ⋮ Approximate Equilibria for Strategic Two Person Games ⋮ The parameterized complexity of welfare guarantees in Schelling segregation ⋮ Approximate and randomized algorithms for computing a second Hamiltonian cycle ⋮ Strategic Characterization of the Index of an Equilibrium ⋮ Note on constrained long choice with multiple beginning elements ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ Inapproximability of NP-Complete Variants of Nash Equilibrium ⋮ Adventures in monotone complexity and TFNP ⋮ On the complexity of stable fractional hypergraph matching ⋮ The Hairy Ball Problem is PPAD-Complete. ⋮ Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem ⋮ Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium ⋮ Computational complexity of some intelligent computing systems ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ Fully Polynomial-Time Approximation Schemes for Fair Rent Division ⋮ On Random Symmetric Bimatrix Games ⋮ Unnamed Item ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Consensus Halving for Sets of Items ⋮ A smooth path-following algorithm for market equilibrium under a class of piecewise-smooth concave utilities ⋮ The complexity of equilibria for risk-modeling valuations ⋮ Congestion games with malicious players ⋮ On the complexity of price equilibria ⋮ Computing approximate Nash equilibria in general network revenue management games ⋮ On the complexity of constrained Nash equilibria in graphical games ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ On the black-box complexity of Sperner's Lemma ⋮ Computational complexity of computing a quasi-proper equilibrium ⋮ On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Regular subgraphs of almost regular graphs
- Exponential lower bounds for finding Brouwer fixed points
- How easy is local search?
- A constructive proof of Tucker's combinatorial lemma
- Complementary pivot theory of mathematical programming
- The Jacobian matrix and global univalence of mappings
- Variable Dimension Complexes Part I: Basic Theory
- Orientation in Complementary Pivot Algorithms
- Every Prime Has a Succinct Certificate
- Hamiltonian Cycles and Uniquely Edge Colourable Graphs
- Equilibrium Points of Bimatrix Games
- Bimatrix Equilibrium Points and Mathematical Programming
- Existence of an Equilibrium for a Competitive Economy
This page was built for publication: On the complexity of the parity argument and other inefficient proofs of existence
