Relations between average case complexity and approximation complexity
From MaRDI portal
Publication:3579211
DOI10.1145/509907.509985zbMATH Open1192.68358DBLPconf/stoc/Feige02OpenAlexW2072802070WikidataQ57568021 ScholiaQ57568021MaRDI QIDQ3579211FDOQ3579211
Cited In (64)
- On the complexity of random satisfiability problems with planted solutions
- Finding connected \(k\)-subgraphs with high density
- Title not available (Why is no real title available?)
- 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
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- The hospitals/residents problem with lower quotas
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Bi-covering: covering edges with two small subsets of vertices
- Sherali-Adams integrality gaps matching the log-density threshold
- An efficient approach to solving random \(k\)-SAT problems
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- 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 no real title available?)
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Noisy tensor completion via the sum-of-squares hierarchy
- Optimal testing for planted satisfiability problems
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs
- The densest \(k\)-subhypergraph problem
- 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
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- Non-convex matrix completion and related problems via strong duality
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Matrix completion and related problems via strong duality
- Improper learning by refuting
- Finding Connected Dense $$k$$-Subgraphs
- Satisfiability thresholds for regular occupation problems
- Asymptotic behavior of the quadratic knapsack problem
- On fair price discrimination in multi-unit markets
- On super strong ETH
- Cryptographic hardness of random local functions. Survey
- On social envy-freeness in multi-unit markets
- On the complexity of fair house allocation
- Finding maximum edge bicliques in convex bipartite graphs
- Approximation of the quadratic knapsack problem
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- 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
- Spectral techniques applied to sparse random graphs
- Algebraic attacks against random local functions and their countermeasures
- Convex optimization for the densest subgraph and densest submatrix problems
- The vertex attack tolerance of complex networks
- Detecting almost symmetries of graphs
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- 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
- Nearly optimal NP-hardness of unique coverage
- 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
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)
