ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
From MaRDI portal
Publication:4993301
DOI10.4230/LIPIcs.ITCS.2018.36zbMath1462.68068arXiv1805.03867OpenAlexW2964171575MaRDI QIDQ4993301
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1805.03867
constraint satisfaction problemshardness of approximationparameterized complexitydirected Steiner network
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (7)
An ETH-tight algorithm for bidirected Steiner connectivity ⋮ Unnamed Item ⋮ A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Imperfect gaps in Gap-ETH and PCPs ⋮ Complexity of the Steiner Network Problem with Respect to the Number of Terminals ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for directed Steiner forest
- Sub-constant error probabilistically checkable proof of almost-linear size
- Improved approximation algorithms for label cover problems
- PCP characterizations of NP: toward a polynomially-small error-probability
- Which problems have strongly exponential complexity?
- Approximation algorithms for spanner problems and directed Steiner forest
- On subexponential and FPT-time inapproximability
- Low-degree test with polynomially small error
- Design networks with bounded pairwise distance
- Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition
- Proof verification and the hardness of approximation problems
- Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
- Set connectivity problems in undirected graphs and the directed steiner network problem
- Short PCPs with Polylog Query Complexity
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds
- Reachability Preservers: New Extremal Bounds and Approximation Algorithms
- Robust Characterizations of Polynomials with Applications to Program Testing
- New Direct-Product Testers and 2-Query PCPs
- Approximation Algorithms for Directed Steiner Problems
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Efficient probabilistically checkable proofs and applications to approximations
- Analytical approach to parallel repetition
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Approximation resistance from pairwise independent subgroups
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- On a problem of K. Zarankiewicz
- The PCP theorem by gap amplification
- On the complexity of \(k\)-SAT
This page was built for publication: ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
