Relations between average case complexity and approximation complexity
From MaRDI portal
Publication:3579211
DOI10.1145/509907.509985zbMATH Open1192.68358DBLPconf/stoc/Feige02OpenAlexW2072802070WikidataQ57568021 ScholiaQ57568021MaRDI QIDQ3579211FDOQ3579211
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)
Cited In (66)
- Nearly Optimal NP-Hardness of Unique Coverage
- Title not available (Why is that?)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- On Super Strong ETH
- Vertex downgrading to minimize connectivity
- Reasoning with propositional logic: from SAT solvers to knowledge compilation
- Max-3-Lin over non-abelian groups with universal factor graphs
- Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN
- A systematic study of sparse LWE
- Lossy cryptography from code-based assumptions
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Reception capacity: definitions, game theory and hardness
- Title not available (Why is that?)
- Finding connected \(k\)-subgraphs with high density
- Title not available (Why is that?)
- On the approximability of the minimum rainbow subgraph problem and other related problems
- The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- The hospitals/residents problem with lower quotas
- Approximation of the Quadratic Knapsack Problem
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- An efficient approach to solving random \(k\)-SAT problems
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Title not available (Why is that?)
- Information-theoretic thresholds from the cavity method
- Noisy tensor completion via the sum-of-squares hierarchy
- Optimal testing for planted satisfiability problems
- On the Complexity of Random Satisfiability Problems with Planted Solutions
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs
- Charting the replica symmetric phase
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- More on average case vs approximation complexity
- Constructing concrete hard instances of the maximum independent set problem
- The ordered covering problem
- Inapproximability of Maximum Weighted Edge Biclique and Its Applications
- The replica symmetric phase of random constraint satisfaction problems
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Finding Connected Dense $$k$$-Subgraphs
- Asymptotic behavior of the quadratic knapsack problem
- On fair price discrimination in multi-unit markets
- Title not available (Why is that?)
- The Densest $k$-Subhypergraph Problem
- Cryptographic hardness of random local functions. Survey
- Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices
- On social envy-freeness in multi-unit markets
- On the complexity of fair house allocation
- Algebraic Attacks against Random Local Functions and Their Countermeasures
- Finding maximum edge bicliques in convex bipartite graphs
- Title not available (Why is that?)
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More
- Partially ordered knapsack and applications to scheduling
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- Title not available (Why is that?)
- Spectral techniques applied to sparse random graphs
- Convex optimization for the densest subgraph and densest submatrix problems
- The vertex attack tolerance of complex networks
- Detecting almost symmetries of graphs
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Title not available (Why is that?)
- Title not available (Why is that?)
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
Uses Software
This page was built for publication: Relations between average case complexity and approximation complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3579211)
