Pages that link to "Item:Q5957725"
From MaRDI portal
The following pages link to Complexity of Positivstellensatz proofs for the knapsack (Q5957725):
Displayed 30 items.
- Algebraic proof systems over formulas. (Q1401356) (← links)
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem (Q1683679) (← links)
- Tight size-degree bounds for sums-of-squares proofs (Q1686838) (← links)
- Symmetric sums of squares over \(k\)-subset hypercubes (Q1702778) (← links)
- Fair colorful \(k\)-center clustering (Q2118132) (← links)
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials (Q2143214) (← links)
- Sum-of-squares hierarchy lower bounds for symmetric formulations (Q2191774) (← links)
- Breaking symmetries to rescue sum of squares in the case of makespan scheduling (Q2196315) (← links)
- On the complexity of Hilbert refutations for partition (Q2252121) (← links)
- An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs (Q2643148) (← links)
- On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy (Q2976145) (← links)
- Query Complexity in Expectation (Q3448835) (← links)
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy (Q3448844) (← links)
- A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem (Q3452846) (← links)
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem (Q4634034) (← links)
- SOS Is Not Obviously Automatizable, Even Approximately (Q4638114) (← links)
- Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs (Q4994984) (← links)
- (Q5005186) (← links)
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut (Q5009512) (← links)
- Fair Colorful k-Center Clustering (Q5041747) (← links)
- Disordered systems insights on computational hardness (Q5055432) (← links)
- (Q5090427) (← links)
- (Q5090440) (← links)
- (Q5091238) (← links)
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs (Q5091776) (← links)
- Complexity of Null- and Positivstellensatz proofs (Q5957910) (← links)
- Generalization of the subset sum problem and cubic forms (Q6039136) (← links)
- Sum of Squares Bounds for the Empty Integral Hull Problem (Q6081967) (← links)
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares (Q6184293) (← links)
- The Spectrum of the Grigoriev–Laurent Pseudomoments (Q6187076) (← links)