Pages that link to "Item:Q5441360"
From MaRDI portal
The following pages link to Some optimal inapproximability results (Q5441360):
Displaying 50 items.
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz (Q2632506) (← links)
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis (Q2633244) (← links)
- Satisfiability with index dependency (Q2637283) (← links)
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach (Q2637641) (← links)
- Column subset selection problem is UG-hard (Q2637653) (← links)
- Go-MOCE: greedy order method of conditional expectations for Max Sat (Q2691199) (← links)
- Three-player entangled XOR games are NP-hard to approximate (Q2816299) (← links)
- Robustly solvable constraint satisfaction problems (Q2817797) (← links)
- From Graph Orientation to the Unweighted Maximum Cut (Q2817879) (← links)
- Quantum XOR games (Q2828211) (← links)
- Learning hurdles for sleeping experts (Q2828218) (← links)
- Limitations of Deterministic Auction Design for Correlated Bidders (Q2849317) (← links)
- Moderately exponential time and fixed parameter approximation algorithms (Q2868915) (← links)
- Improved Parameterized Algorithms for above Average Constraint Satisfaction (Q2891342) (← links)
- Grothendieck-type inequalities in combinatorial optimization (Q2892967) (← links)
- Satisfiability Thresholds beyond k −XORSAT (Q2907497) (← links)
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey (Q2908541) (← links)
- New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover (Q2943894) (← links)
- Block Sorting Is APX-Hard (Q2947036) (← links)
- Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies (Q2947865) (← links)
- Super-polynomial approximation branching algorithms (Q2954364) (← links)
- Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors (Q2968154) (← links)
- A priori TSP in the Scenario Model (Q2971168) (← links)
- Approximation Algorithms for Orienting Mixed Graphs (Q3011872) (← links)
- Inapproximability of b-Matching in k-Uniform Hypergraphs (Q3078381) (← links)
- Satisfying Degree-d Equations over GF[2] n (Q3088098) (← links)
- Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs (Q3088105) (← links)
- Short Locally Testable Codes and Proofs (Q3088191) (← links)
- On Khot’s unique games conjecture (Q3109809) (← links)
- Minimum Cell Connection in Line Segment Arrangements (Q3132917) (← links)
- Nonnegative Weighted #CSP: An Effective Complexity Dichotomy (Q3179267) (← links)
- A query efficient non-adaptive long code test with perfect completeness (Q3192387) (← links)
- Approximation hardness of graphic TSP on cubic graphs (Q3194690) (← links)
- On the Complexity of the Minimum Independent Set Partition Problem (Q3196378) (← links)
- Approximate Kernel Clustering (Q3400770) (← links)
- On Dinur’s proof of the PCP theorem (Q3430210) (← links)
- ON THE APPROXIMABILITY OF MAXIMUM AND MINIMUM EDGE CLIQUE PARTITION PROBLEMS (Q3434272) (← links)
- Covering Graphs by Colored Stable Sets (Q3439145) (← links)
- Simultaneous Approximation of Constraint Satisfaction Problems (Q3448785) (← links)
- Quantum Locally Testable Codes (Q3449558) (← links)
- A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization (Q3449564) (← links)
- Judicious partitions of directed graphs (Q3467583) (← links)
- Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation (Q3467859) (← links)
- How to Encrypt with the LPN Problem (Q3519542) (← links)
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies (Q3541786) (← links)
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2) (Q3541815) (← links)
- On the Random Satisfiable Process (Q3552504) (← links)
- Finding an Unknown Acyclic Orientation of a Given Graph (Q3557528) (← links)
- Parallel and Concurrent Security of the HB and HB + Protocols (Q3593090) (← links)
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP (Q3608306) (← links)
