Semialgebraic Proofs and Efficient Algorithm Design

DOI10.1561/0400000086MaRDI QIDQ5215904zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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)

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

Cited in

(17)

• Sum-of-squares proofs and the quest toward optimal algorithms
• Reflections on Proof Complexity and Counting Principles
• scientific article; zbMATH DE number 1304339 (Why is no real title available?)
• MaxSAT Resolution and Subcube Sums
• Algorithms approaching the threshold for semi-random planted clique
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Book review of: T. Theobald, Real algebraic geometry and optimization
• On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• First-order reasoning and efficient semi-algebraic proofs
• Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
• scientific article; zbMATH DE number 2086404 (Why is no real title available?)
• Semialgebraic proofs, IPS lower bounds, and the \(\tau\)-conjecture: can a natural number be negative?
• First-order reasoning and efficient semi-algebraic proofs
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• Logical semirings and their usage for construction of quick algorithms
• Superlinear Integrality Gaps for the Minimum Majority Problem

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)