Pages that link to "Item:Q3177811"

The following pages link to Approximate Constraint Satisfaction Requires Large LP Relaxations (Q3177811):

Displaying 50 items.

• Integrality gaps for strengthened linear relaxations of capacitated facility location (Q304227) (← links)
• Common information and unique disjointness (Q343843) (← links)
• Average case polyhedral complexity of the maximum stable set problem (Q344955) (← links)
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy (Q430828) (← links)
• Extension complexity of formal languages (Q778518) (← links)
• Extended formulation for CSP that is compact for instances of bounded treewidth (Q907218) (← links)
• Sum-of-squares rank upper bounds for matching problems (Q1631641) (← links)
• The matching problem has no small symmetric SDP (Q1675264) (← links)
• Affine reductions for LPs and SDPs (Q1717229) (← links)
• Simple approximation algorithms for balanced MAX~2SAT (Q1742374) (← links)
• Approximating graph-constrained max-cut (Q1800989) (← links)
• Semidefinite and linear programming integrality gaps for scheduling identical machines (Q1800998) (← links)
• Strong reductions for extended formulations (Q1801022) (← links)
• Information-theoretic approximations of the nonnegative rank (Q2012181) (← links)
• Balas formulation for the union of polytopes is optimal (Q2297650) (← links)
• Parameterized extension complexity of independent set and related problems (Q2413967) (← links)
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) (Q2422767) (← links)
• A comprehensive analysis of polyhedral lift-and-project methods (Q2790405) (← links)
• Exponential lower bounds for polytopes in combinatorial optimization (Q2796404) (← links)
• Sum-of-Squares Rank Upper Bounds for Matching Problems (Q2835696) (← links)
• Separation between Estimation and Approximation (Q2989040) (← links)
• Query Complexity in Expectation (Q3448835) (← links)
• Approximation Limits of Linear Programs (Beyond Hierarchies) (Q3449458) (← links)
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies (Q3451762) (← links)
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy (Q3581430) (← links)
• Communication Lower Bounds via Critical Block Sensitivity (Q4554052) (← links)
• Deterministic Communication vs. Partition Number (Q4562279) (← links)
• From weak to strong linear programming gaps for all constraint satisfaction problems (Q4568111) (← links)
• Extension Complexity of Independent Set Polytopes (Q4606697) (← links)
• Small extended formulation for knapsack cover inequalities from monotone circuits (Q4612478) (← links)
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs (Q4978005) (← links)
• Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs (Q4994984) (← links)
• Reflections on Proof Complexity and Counting Principles (Q5027248) (← links)
• Lifting for Simplicity: Concise Descriptions of Convex Sets (Q5044992) (← links)
• Extension complexity of low-dimensional polytopes (Q5082401) (← links)
• (Q5088887) (← links)
• (Q5089260) (← links)
• Sherali-adams strikes back (Q5091758) (← links)
• Query-to-Communication Lifting for BPP (Q5117373) (← links)
• (Q5121903) (← links)
• (Q5158503) (← links)
• Constant-Query Testability of Assignments to Constraint Satisfaction Problems (Q5232319) (← links)
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds (Q5269825) (← links)
• The Complexity of General-Valued CSPs (Q5283238) (← links)
• The Power of Sherali--Adams Relaxations for General-Valued CSPs (Q5348454) (← links)
• An Almost Optimal Algorithm for Computing Nonnegative Rank (Q5743610) (← links)
• Rectangles are nonnegative juntas (Q5890971) (← links)
• Principles and Practice of Constraint Programming – CP 2004 (Q5900306) (← links)
• Extended formulations from communication protocols in output-efficient time (Q5918910) (← links)
• A tight approximation algorithm for the cluster vertex deletion problem (Q5925651) (← links)