Relations between average case complexity and approximation complexity
From MaRDI portal
(Redirected from Publication:3579211)
Cited in
(80)- Convex optimization for the densest subgraph and densest submatrix problems
- Detecting almost symmetries of graphs
- On the approximability of the minimum rainbow subgraph problem and other related problems
- Charting the replica symmetric phase
- The envy-free pricing problem, unit-demand markets and connections with the network pricing problem
- Finding maximum edge bicliques in convex bipartite graphs
- On fair price discrimination in multi-unit markets
- On the complexity of fair house allocation
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- Noisy tensor completion via the sum-of-squares hierarchy
- Optimal testing for planted satisfiability problems
- On social envy-freeness in multi-unit markets
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
- Finding connected \(k\)-subgraphs with high density
- The hospitals/residents problem with lower quotas
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Finding Connected Dense k-Subgraphs
- Interdicting structured combinatorial optimization problems with {0,1}-objectives
- The densest k-subhypergraph problem
- Approximation of the quadratic knapsack problem
- Asymptotic behavior of the quadratic knapsack problem
- Cryptographic hardness of random local functions. Survey
- Recognizing more random unsatisfiable 3-SAT instances efficiently
- Inapproximability of Maximum Weighted Edge Biclique and Its Applications
- More on average case vs approximation complexity
- Lower bounds for k-DNF resolution on random 3-CNFs
- On the complexity of random satisfiability problems with planted solutions
- The vertex attack tolerance of complex networks
- Bi-covering: covering edges with two small subsets of vertices
- Algebraic attacks against random local functions and their countermeasures
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- The replica symmetric phase of random constraint satisfaction problems
- Matrix completion and related problems via strong duality
- Improper learning by refuting
- Sherali-Adams integrality gaps matching the log-density threshold
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
- SOS lower bounds with hard constraints: think global, act local
- Satisfiability thresholds for regular occupation 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
- Non-convex matrix completion and related problems via strong duality
- Nearly optimal NP-hardness of unique coverage
- Spectral techniques applied to sparse random graphs
- Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph
- Approximation algorithms and hardness of the \(k\)-route cut problem
- On super strong ETH
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Vertex downgrading to minimize connectivity
- Max-3-Lin over non-abelian groups with universal factor graphs
- scientific article; zbMATH DE number 7758323 (Why is no real title available?)
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN
- Sum-of-squares lower bounds for densest k-subgraph
- Reception capacity: definitions, game theory and hardness
- Reasoning with propositional logic: from SAT solvers to knowledge compilation
- Lossy cryptography from code-based assumptions
- A systematic study of sparse LWE
- Smoothed analysis of deterministic discounted and Mean-payoff games
- Satisfiability thresholds for regular occupation problems
- Somewhat homomorphic encryption from linear homomorphism and sparse LPN
- Distributional PAC-learning from Nisan's natural proofs
- Optirefine: densest subgraphs and maximum cuts with k refinements
- Lossy cryptography from code-based assumptions dense-sparse LPN: a new subexponentially hard LPN variant in SZK
- Indistinguishability obfuscation from bilinear maps and LPN variants
- Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT
- The ordered covering problem
- The strongish planted clique hypothesis and its consequences
- Finding maximum edge bicliques in tree convex graphs
- Improved hardness results for learning intersections of halfspaces
- Improved search-to-decision reduction for random local functions
- On the MCMC performance in Bernoulli group testing and the random max-set cover problem
- On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
- Spectral refutations of semirandom k-LIN over larger fields
- Structured-seed local pseudorandom generators and their applications
- An efficient approach to solving random \(k\)-SAT problems
- Partially ordered knapsack and applications to scheduling
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
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)
