Semialgebraic Proofs and Efficient Algorithm Design
DOI10.1561/0400000086zbMATH Open1430.68428OpenAlexW4205196152WikidataQ113740131 ScholiaQ113740131MaRDI QIDQ5215904FDOQ5215904
Authors: Noah Fleming, Pravesh Kothari, Toniann Pitassi 
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
Recommendations
- A semi-algorithm for algebraic implementation proofs
- scientific article; zbMATH DE number 2086404
- scientific article; zbMATH DE number 1916823
- On the width of semialgebraic proofs and algorithms
- scientific article; zbMATH DE number 1304339
- Algorithmic problems in varieties of semigroups
- scientific article; zbMATH DE number 4051899
- scientific article; zbMATH DE number 515726
- scientific article; zbMATH DE number 1745035
- Algebraic algorithmics: Theory and applications
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Linear programming (90C05) Semidefinite programming (90C22) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity of proofs (03F20) General topics in the theory of algorithms (68W01)
Cited In (16)
- Title not available (Why is that?)
- Reflections on Proof Complexity and Counting Principles
- Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
- Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
- Logical semirings and their usage for construction of quick algorithms
- MaxSAT Resolution and Subcube Sums
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- First-order reasoning and efficient semi-algebraic proofs
- Superlinear Integrality Gaps for the Minimum Majority Problem
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Book review of: T. Theobald, Real algebraic geometry and optimization
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- Title not available (Why is that?)
- Algorithms approaching the threshold for semi-random planted clique
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Sum-of-squares proofs and the quest toward optimal algorithms
This page was built for publication: Semialgebraic Proofs and Efficient Algorithm Design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5215904)
