The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover

We suggest the research agenda of establishing new hardness of approximation results based on the “projection games conjecture”, i.e., an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games.

• Publication year

  2012

• Venue

  Theory of Computing

• Publication date

  2012-08-15

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4086/toc.2015.v011a007
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation resistance from pairwise independent subgroups

  2013cited by this paper
• Improved Approximation Algorithms for Label Cover Problems

  2011cited by this paper
• On the Complexity of Lattice Problems with Polynomial Approximation Factors

  2010cited by this paper
• Inapproximability Results for Computational Problems on Lattices

  2010cited by this paper
• Exponential-time approximation of weighted set cover

  2009cited by this paper
• Two Query PCP with Sub-Constant Error

  2008cited by this paper
• Optimal algorithms and inapproximability results for every CSP?

  2008cited by this paper
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors

  2007cited by this paper
• Algorithmic construction of sets for k-restrictions

  2006cited by this paper
• Sub-constant error low degree test of almost-linear size

  2006cited by this paper
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

  2006cited by this paper
• Lattice problems in NP ∩ coNP

  2005cited by this paper
• On lattices, learning with errors, random linear codes, and cryptography

  2005cited by this paper
• Worst-case to average-case reductions based on Gaussian measures

  2004cited by this paper
• Hardness of approximating the shortest vector problem in lattices

  2004cited by this paper
• Approximating CVP to Within Almost-Polynomial Factors is NP-Hard

  2003cited by this paper
• Complexity of lattice problems - a cryptographic perspective

  2002cited by this paper
• On the power of unique 2-prover 1-round games

  2002cited by this paper
• Some optimal inapproximability results

  2001cited by this paper
• Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring

  2001cited by this paper
• Approximation algorithms for the Label-CoverMAX and Red-Blue Set Cover problems

  2000cited by this paper
• On bounded occurrence constraint satisfaction

  2000cited by this paper
• Improved Approximation Guarantees for Packing and Covering Integer Programs

  1999cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• Complexity of k-SAT

  1999cited by this paper
• PCP characterizations of NP: towards a polynomially-small error-probability

  1999cited by this paper
• Approximating SVPinfinity to within almost-polynomial factors is NP-hard

  1998cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  1997cited by this paper
• Improved Low-Degree Testing and its Applications

  1997cited by this paper
• A tight analysis of the greedy algorithm for set cover

  1996cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• A parallel repetition theorem

  1995cited by this paper
• Splitters and near-optimal derandomization

  1995cited by this paper
• On the hardness of approximating minimization problems

  1994cited by this paper
• The hardness of approximate optima in lattices, codes, and systems of linear equations

  1993cited by this paper
• Efficient probabilistically checkable proofs and applications to approximations

  1993cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• A Greedy Heuristic for the Set-Covering Problem

  1979cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Two Combinatorial Covering Theorems

  1974cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper

• Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria

  2026influential citation
• Multiway cuts with a choice of representatives

  2026cites this paper
• On Small Pair Decompositions for Point Sets

  2026cites this paper
• Shortcuts and Transitive-Closure Spanners Approximation

  2025cites this paper
• Time-Optimal k-Server

  2025cites this paper
• On the (In)Approximability of the Monitoring Edge Geodetic Set Problem

  2025cites this paper
• Inventory placement on a network

  2025cites this paper
• SVPp is NP-Hard for all p > 2, Even to Approximate Within a Factor of 2{log1-ϵ n

  2025cites this paper
• SVPp is Deterministically NP-Hard for all p > 2, Even to Approximate Within a Factor of 2log1-ε n

  2025cites this paper
• On the complexity of temporal arborescence reconfiguration

  2025cites this paper
• Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization

  2024cites this paper
• Sensitivity Lower Bounds for Approximaiton Algorithms

  2024cites this paper
• Parameterized Approximation for Capacitated d-Hitting Set with Hard Capacities

  2024cites this paper
• Optimization by decoded quantum interferometry

  2024cites this paper
• Quasi-Linear Size PCPs with Small Soundness from HDX

  2024cites this paper
• Multiway Cuts with a Choice of Representatives

  2024cites this paper
• Fault-Tolerant Bounded Flow Preservers

  2024cites this paper
• Open Problems Column

  2023influential citation
• The Complexity of the Shortest Vector Problem

  2023cites this paper
• Observation Routes and External Watchman Routes

  2023cites this paper
• The Price of Explainability for Clustering

  2023cites this paper
• Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms

  2023cites this paper
• Finding Smallest Witnesses for Conjunctive Queries

  2023cites this paper
• Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold

  2023cites this paper
• Algorithms for Intersection Graphs of 𝑡 -Intervals and 𝑡 -Pseudodisks

  2022cites this paper
• Differentially Private Partial Set Cover with Applications to Facility Location

  2022cites this paper
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing

  2022cites this paper
• Polynomial Integrality Gap of Flow LP for Directed Steiner Tree

  2021cites this paper
• CS 583: Approximation Algorithms

  2021cites this paper
• Inapproximability of a Pair of Forms Defining a Partial Boolean Function

  2021cites this paper
• Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics

  2021cites this paper
• A Chronology of Set Cover Inapproximability Results

  2021influential citation
• Algorithms, hardness and graph products on a pursuit-evasion game

  2021cites this paper
• Generalizable synthesis through unification

  2021cites this paper
• Justifying Groups in Multiwinner Approval Voting

  2021cites this paper
• Occam Learning Meets Synthesis Through Unification

  2021cites this paper
• Designing viral diagnostics with model-based optimization

  2021cites this paper
• Strong Parallel Repetition for Unique Games on Small Set Expanders

  2021cites this paper
• Diagnostic design with machine learning model-based optimization

  2021cites this paper
• The Complexity of Flow Expansion and Electrical Flow Expansion

  2021cites this paper
• Cost-optimal Planning, Delete Relaxation, Approximability, and Heuristics

  2021cites this paper
• Almost Optimal Inapproximability of Multidimensional Packing Problems

  2021cites this paper
• The Optimal Design of Low-Latency Virtual Backbones

  2020cites this paper
• On Hop-Constrained Steiner Trees in Tree-Like Metrics

  2020influential citation
• Domination chain: Characterisation, classical complexity, parameterised complexity and approximability

  2020cites this paper
• Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

  2020cites this paper
• A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

  2020cites this paper
• New Directions in Streaming Algorithms

  2020cites this paper
• Combinatorial Optimization of Graphical User Interface Designs

  2020cites this paper
• Efficient design of maximally active and specific nucleic acid diagnostics for thousands of viruses

  2020cites this paper
• From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More

  2020cites this paper
• Easy Capacitated Facility Location Problems, with Connections to Lot-Sizing

  2020cites this paper
• Covert Networks: How Hard is It to Hide?

  2019cites this paper
• Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

  2019cites this paper
• The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems

  2019cites this paper
• Improved Local Computation Algorithm for Set Cover via Sparsification

  2019cites this paper
• Fast approximations for combinatorial optimization via multiplicative weight updates

  2019cites this paper
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)

  2019cites this paper
• Approximation and Hardness: Beyond P and NP

  2019cites this paper
• Tight approximation bounds for maximum multi-coverage

  2019influential citation
• A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree

  2019influential citation
• On the Parameterized Complexity of Approximating Dominating Set

  2019cites this paper
• A Low Overhead Mapping Scheme for Exploration and Representation in the Unknown Area

  2019cites this paper
• Sliding Scale Conjectures in PCP

  2019influential citation
• Faster provable sieving algorithms for the Shortest Vector Problem and the Closest Vector Problem on lattices in 𝓁p norm

  2019cites this paper
• Improved 3LIN Hardness via Linear Label Cover

  2019cites this paper
• The Projection Games Conjecture and the Hardness of Approximation of SSAT and related problems

  2019cites this paper
• New Results on Directed Edge Dominating Set

  2019cites this paper
• Parameterized Inapproximability of Exact Cover and Nearest Codeword

  2019cites this paper
• Ju n 20 19 Approximation algorithms for stochastic clustering ∗

  2019cites this paper
• The synthesis problem of decentralized energy systems is strongly NP-hard

  2019cites this paper
• Becoming Gatekeepers Together with Allies: Collaborative Brokerage over Social Networks

  2019cites this paper
• The Inapproximability of k-DominatingSet for Parameterized \mathsf AC^0 AC 0 Circuits

  2019cites this paper
• The Inapproximability of k-DominatingSet for Parameterized AC 0 Circuits †

  2019cites this paper
• On subexponential running times for approximating directed Steiner tree and related problems

  2018influential citation
• Parameterized Orientable Deletion ∗

  2018cites this paper
• Towards Fast Computation of Certified Robustness for ReLU Networks

  2018influential citation
• Complexity of minimum irreducible infeasible subsystem covers for flow networks

  2018cites this paper
• Set Cover in Sub-linear Time

  2018cites this paper
• The Kessler Run: On the Design of the GTOC9 Challenge

  2018cites this paper
• Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class

  2018cites this paper
• A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems

  2018cites this paper
• Tracking Mobile Intruders in an Art Gallery: Guard Deployment Strategies, Fundamental Limitations, and Performance Guarantees

  2018cites this paper
• On Approximating (Sparse) Covering Integer Programs

  2018cites this paper
• Approximation algorithms for stochastic clustering

  2018cites this paper
• Distributed Set Cover Approximation: Primal-Dual with Optimal Locality

  2018cites this paper
• Stochastic Submodular Cover with Limited Adaptivity

  2018cites this paper
• O(log2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

  2018cites this paper
• When polynomial approximation meets exact computation

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• 2 Our Results 2 . 1 Better Approximation in Polynomial Time

  2018cites this paper
• Deleting edges to restrict the size of an epidemic in temporal networks

  2018cites this paper
• Resource allocation and decision making for groups

  2018cites this paper
• Parameterized Orientable Deletion

  2018cites this paper
• D S ] 3 1 O ct 2 01 8 Stochastic Submodular Cover with Limited Adaptivity Arpit

  2018cites this paper
• Optimal Matroid Partitioning Problems

  2017cites this paper
• On the parameterized complexity of approximating dominating set

  2017cites this paper
• Using the PCP to prove fixed parameter hardness

  2017influential citation
• Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis

  2017cites this paper
• A pr 2 01 7 Partial resampling to approximate covering integer programs ∗

  2017cites this paper