Semialgebraic Proofs and Efficient Algorithm Design

DOI10.1561/0400000086zbMath1430.68428OpenAlexW4205196152WikidataQ113740131 ScholiaQ113740131MaRDI QIDQ5215904

Pravesh K. Kothari, Toniann Pitassi, Noah Fleming

Publication date: 13 February 2020

Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1561/0400000086

Mathematics Subject Classification ID

Semidefinite programming (90C22) Linear programming (90C05) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) General topics in the theory of algorithms (68W01)

Related Items (4)

The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem ⋮ Reflections on Proof Complexity and Counting Principles ⋮ MaxSAT Resolution and Subcube Sums

This page was built for publication: Semialgebraic Proofs and Efficient Algorithm Design