Relations between average case complexity and approximation complexity
From MaRDI portal
Publication:3579211
Cited in
(64)- 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
- Reasoning with propositional logic: from SAT solvers to knowledge compilation
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Max-3-Lin over non-abelian groups with universal factor graphs
- Reception capacity: definitions, game theory and hardness
- Vertex downgrading to minimize connectivity
- Nearly optimal NP-hardness of unique coverage
- On the complexity of fair house allocation
- On the complexity of random satisfiability problems with planted solutions
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- Algebraic attacks against random local functions and their countermeasures
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- On fair price discrimination in multi-unit markets
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs
- More on average case vs approximation complexity
- On super strong ETH
- An efficient approach to solving random \(k\)-SAT problems
- Improper learning by refuting
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- Noisy tensor completion via the sum-of-squares hierarchy
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Convex optimization for the densest subgraph and densest submatrix problems
- Bi-covering: covering edges with two small subsets of vertices
- On the approximability of the minimum rainbow subgraph problem and other related problems
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Constructing concrete hard instances of the maximum independent set problem
- Finding Connected Dense $$k$$-Subgraphs
- Spectral techniques applied to sparse random graphs
- The replica symmetric phase of random constraint satisfaction problems
- The vertex attack tolerance of complex networks
- Approximation of the quadratic knapsack problem
- Optimal testing for planted satisfiability problems
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Finding connected \(k\)-subgraphs with high density
- On social envy-freeness in multi-unit markets
- The densest \(k\)-subhypergraph problem
- Partially ordered knapsack and applications to scheduling
- Satisfiability thresholds for regular occupation problems
- Detecting almost symmetries of graphs
- The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
- Non-convex matrix completion and related problems via strong duality
- The ordered covering problem
- Charting the replica symmetric phase
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- scientific article; zbMATH DE number 7559092 (Why is no real title available?)
- Asymptotic behavior of the quadratic knapsack problem
- Matrix completion and related problems via strong duality
- Sherali-Adams integrality gaps matching the log-density threshold
- Finding maximum edge bicliques in convex bipartite graphs
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- Cryptographic hardness of random local functions. Survey
- Inapproximability of Maximum Weighted Edge Biclique and Its Applications
- The hospitals/residents problem with lower quotas
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- scientific article; zbMATH DE number 7758323 (Why is no real title available?)
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- Recognizing more random unsatisfiable 3-SAT instances efficiently
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)
