Derandomized graph products
From MaRDI portal
Publication:1842777
DOI10.1007/BF01277956zbMath0816.60070OpenAlexW2055656009MaRDI QIDQ1842777
Uriel Feige, David Zuckerman, Noga Alon, Avi Wigderson
Publication date: 16 July 1995
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01277956
Sums of independent random variables; random walks (60G50) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Traveling salesman problems in temporal graphs, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, On the longest common rigid subsequence problem, Online Admission Control and Embedding of Service Chains, The complexity and approximability of finding maximum feasible subsystems of linear relations, Differential approximation of MIN SAT, MAX SAT and related problems, On Lagrangian relaxation for constrained maximization and reoptimization problems, Inequalities for the number of walks in graphs, Improved (In-)Approximability Bounds for d-Scattered Set, Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Designing menus of contracts efficiently: the power of randomization, Expander graphs and their applications, Greed is good for deterministic scale-free networks, ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS, Improved non-approximability results for minimum vertex cover with density constraints, On codes from hypergraphs., Randomness buys depth for approximate counting, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality, Deterministic Tensor Completion with Hypergraph Expanders, Logarithmic reduction of the level of randomness in some probabilistic geometric constructions, Completeness in approximation classes beyond APX, On Lagrangian Relaxation and Subset Selection Problems, On the advantage over a random assignment, On approximating four covering and packing problems, Zero knowledge and the chromatic number, On the hardness of approximating max-satisfy, How much randomness is needed to convert MA protocols to AM protocols?, Bounded queries, approximations, and the Boolean hierarchy, Scalable secure storage when half the system is faulty, Local correctability of expander codes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Explicit construction of linear sized tolerant networks
- Ramanujan graphs
- Eigenvalues and expanders
- Explicit constructions of linear-sized superconcentrators
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Randomness in interactive proofs
- The hardness of approximate optima in lattices, codes, and systems of linear equations
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Greed is good
