Relations between average case complexity and approximation complexity
From MaRDI portal
Publication:3579211
DOI10.1145/509907.509985zbMath1192.68358OpenAlexW2072802070WikidataQ57568021 ScholiaQ57568021MaRDI QIDQ3579211
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509985
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (61)
Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ On the Complexity of Random Satisfiability Problems with Planted Solutions ⋮ Detecting almost symmetries of graphs ⋮ Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes ⋮ Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes ⋮ The Densest $k$-Subhypergraph Problem ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Noisy tensor completion via the sum-of-squares hierarchy ⋮ Asymptotic behavior of the quadratic knapsack problem ⋮ Approximation of the Quadratic Knapsack Problem ⋮ Unnamed Item ⋮ Cryptographic hardness of random local functions. Survey ⋮ Information-theoretic thresholds from the cavity method ⋮ Spectral techniques applied to sparse random graphs ⋮ Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization ⋮ Finding connected \(k\)-subgraphs with high density ⋮ An efficient approach to solving random \(k\)-SAT problems ⋮ The vertex attack tolerance of complex networks ⋮ Partially ordered knapsack and applications to scheduling ⋮ On the approximability of the minimum rainbow subgraph problem and other related problems ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ Vertex downgrading to minimize connectivity ⋮ Max-3-Lin over non-abelian groups with universal factor graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Inapproximability of Maximum Weighted Edge Biclique and Its Applications ⋮ Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Algebraic Attacks against Random Local Functions and Their Countermeasures ⋮ Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ More on average case vs approximation complexity ⋮ Lower bounds for \(k\)-DNF resolution on random 3-CNFs ⋮ Unnamed Item ⋮ Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives ⋮ Unnamed Item ⋮ Maximum Edge Bicliques in Tree Convex Bipartite Graphs ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Solving the maximum edge biclique packing problem on unbalanced bipartite graphs ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Charting the replica symmetric phase ⋮ The envy-free pricing problem, unit-demand markets and connections with the network pricing problem ⋮ Approximating the 2-catalog segmentation problem using semidefinite programming relaxations ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Optimal testing for planted satisfiability problems ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The ordered covering problem ⋮ Convex optimization for the densest subgraph and densest submatrix problems ⋮ On fair price discrimination in multi-unit markets ⋮ On the complexity of fair house allocation ⋮ On social envy-freeness in multi-unit markets ⋮ The replica symmetric phase of random constraint satisfaction problems ⋮ Nearly Optimal NP-Hardness of Unique Coverage ⋮ On Super Strong ETH ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Recognizing more random unsatisfiable 3-SAT instances efficiently ⋮ The hospitals/residents problem with lower quotas
Uses Software
This page was built for publication: Relations between average case complexity and approximation complexity
