Pages that link to "Item:Q3579211"
From MaRDI portal
The following pages link to Relations between average case complexity and approximation complexity (Q3579211):
Displaying 50 items.
- Convex optimization for the densest subgraph and densest submatrix problems (Q142862) (← links)
- The hospitals/residents problem with lower quotas (Q261379) (← links)
- Asymptotic behavior of the quadratic knapsack problem (Q323537) (← links)
- Cryptographic hardness of random local functions. Survey (Q332271) (← links)
- More on average case vs approximation complexity (Q430823) (← links)
- Lower bounds for \(k\)-DNF resolution on random 3-CNFs (Q430840) (← links)
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs (Q496657) (← links)
- Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT (Q706614) (← links)
- The ordered covering problem (Q722532) (← links)
- An efficient approach to solving random \(k\)-SAT problems (Q877837) (← links)
- Partially ordered knapsack and applications to scheduling (Q881568) (← links)
- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation (Q896191) (← links)
- Detecting almost symmetries of graphs (Q1621684) (← links)
- Information-theoretic thresholds from the cavity method (Q1649349) (← links)
- On the approximability of the minimum rainbow subgraph problem and other related problems (Q1679237) (← links)
- Charting the replica symmetric phase (Q1749356) (← links)
- The envy-free pricing problem, unit-demand markets and connections with the network pricing problem (Q1751179) (← links)
- Finding maximum edge bicliques in convex bipartite graphs (Q1759663) (← links)
- On fair price discrimination in multi-unit markets (Q2046039) (← links)
- On the complexity of fair house allocation (Q2060606) (← links)
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes (Q2129008) (← links)
- Noisy tensor completion via the sum-of-squares hierarchy (Q2144539) (← links)
- Optimal testing for planted satisfiability problems (Q2259537) (← links)
- On social envy-freeness in multi-unit markets (Q2321269) (← links)
- Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix (Q2358291) (← links)
- Finding connected \(k\)-subgraphs with high density (Q2407097) (← links)
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis (Q2633244) (← links)
- Finding Connected Dense $$k$$-Subgraphs (Q2948471) (← links)
- Interdicting Structured Combinatorial Optimization Problems with {0, 1}-Objectives (Q2976146) (← links)
- The Densest $k$-Subhypergraph Problem (Q3174693) (← links)
- Approximation of the Quadratic Knapsack Problem (Q3186661) (← links)
- Recognizing more random unsatisfiable 3-SAT instances efficiently (Q3439113) (← links)
- Inapproximability of Maximum Weighted Edge Biclique and Its Applications (Q3502654) (← links)
- Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization (Q4575825) (← links)
- On the Complexity of Random Satisfiability Problems with Planted Solutions (Q4577186) (← links)
- The vertex attack tolerance of complex networks (Q4578160) (← links)
- Bi-Covering: Covering Edges with Two Small Subsets of Vertices (Q4596825) (← links)
- Algebraic Attacks against Random Local Functions and Their Countermeasures (Q4600698) (← links)
- Maximum Edge Bicliques in Tree Convex Bipartite Graphs (Q4632202) (← links)
- Approximating the 2-catalog segmentation problem using semidefinite programming relaxations (Q4650629) (← links)
- The replica symmetric phase of random constraint satisfaction problems (Q4993097) (← links)
- (Q4993268) (← links)
- (Q4993325) (← links)
- (Q5009502) (← links)
- Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut (Q5009512) (← links)
- (Q5090427) (← links)
- (Q5091251) (← links)
- From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More (Q5115701) (← links)
- Constructing concrete hard instances of the maximum independent set problem (Q5149679) (← links)
- (Q5214187) (← links)
