Semialgebraic Proofs and Efficient Algorithm Design
From MaRDI portal
Publication:5215904
Complexity of proofs (03F20) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01) Linear programming (90C05) Semidefinite programming (90C22)
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
(33)- Logical semirings and their usage for construction of quick algorithms
- scientific article; zbMATH DE number 1304339 (Why is no real title available?)
- Sum-of-squares proofs and the quest toward optimal algorithms
- scientific article; zbMATH DE number 2086404 (Why is no real title available?)
- Superlinear Integrality Gaps for the Minimum Majority Problem
- Reflections on Proof Complexity and Counting Principles
- MaxSAT Resolution and Subcube Sums
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Sum-of-squares lower bounds for densest k-subgraph
- Algorithms approaching the threshold for semi-random planted clique
- Semialgebraic proofs, IPS lower bounds, and the -conjecture: can a natural number be negative?
- Independent set in \(k\)-claw-free graphs: conditional \(\chi \)-boundedness and the power of LP/SDP relaxations
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- First-order reasoning and efficient semi-algebraic proofs
- Book review of: T. Theobald, Real algebraic geometry and optimization
- On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
- First-order reasoning and efficient semi-algebraic proofs
- Certifying Euclidean sections and finding planted sparse vectors beyond the \(\sqrt{n}\) dimension threshold
- Approximation algorithms for _p-shortest path and _p-group Steiner tree
- Computational complexity of sum-of-squares bounds for copositive programs
- Intersection classes in TFNP and proof complexity
- NLTS Hamiltonians and strongly-explicit SoS lower bounds from low-rate quantum LDPC codes
- Proving unsatisfiability with hitting formulas
- Separations in proof complexity and TFNP
- Polynomial-time sum-of-squares can robustly estimate mean and covariance of Gaussians optimally
- Strength and limitations of Sherali-Adams and nullstellensatz proof systems
- Explicit SoS lower bounds from high-dimensional expanders
- Refuting perfect matchings in spectral expanders is hard
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- On the degree automatability of sum-of-squares proofs
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)
