Parallel approximation of min-max problems
Publication:354658
DOI10.1007/S00037-013-0065-9zbMath1286.68133arXiv1011.2787OpenAlexW2083633130MaRDI QIDQ354658
Publication date: 19 July 2013
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1011.2787
semidefinite programmingzero-sum gamesparallel approximation algorithmquantum interactive proofs with competing provers
Semidefinite programming (90C22) Minimax problems in mathematical programming (90C47) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel approximation of min-max problems
- Approximating linear programming is log-space complete for P
- Quantum Arthur-Merlin games
- On the complexity of succinct zero-sum games
- The complexity of two-person zero-sum games in extensive form
- A note on approximate linear programming
- Fast algorithms for finding randomized strategies in game trees
- Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
- Parallel Algorithms for Algebraic Problems
- On Relating Time and Space to Size and Depth
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Cryptographic distinguishability measures for quantum-mechanical states
- Two-Message Quantum Interactive Proofs Are in PSPACE
- A parallel approximation algorithm for positive linear programming
- Online Variance Minimization
- QIP = PSPACE
- A Parallel Approximation Algorithm for Positive Semidefinite Programming
- STACS 2005
- Minimax Theorems
This page was built for publication: Parallel approximation of min-max problems
