Optimal Long Code Test with One Free Bit

DOI10.1109/FOCS.2009.23zbMath1292.68081MaRDI QIDQ5171195

Subhash A. Khot, Nikhil Bansal

Publication date: 25 July 2014

Published in: 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/focs.2009.23

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Bi-Covering: Covering Edges with Two Small Subsets of Vertices, A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies, The Quest for Strong Inapproximability Results with Perfect Completeness, On Submodular Search and Machine Scheduling, Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations, Quasi-PTAS for scheduling with precedences using LP hierarchies, Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, An improved approximation algorithm for scheduling under arborescence precedence constraints, Unnamed Item, Scheduling results applicable to decision-theoretic troubleshooting, The feedback arc set problem with triangle inequality is a vertex cover problem, A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Strong reductions for extended formulations, Makespan minimization with OR-precedence constraints, Tight inapproximability of minimum maximal matching on bipartite graphs and related problems, Preemptive and non-preemptive generalized min sum set cover, Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates, A \((2 + \epsilon)\)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Vertex Cover in Graphs with Locally Few Colors, Approximating Weighted Completion Time for Order Scheduling with Setup Times, Towards Tight Lower Bounds for Scheduling Problems