Derandomized graph products
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1003268 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256635 (Why is no real title available?)
- scientific article; zbMATH DE number 1256636 (Why is no real title available?)
- scientific article; zbMATH DE number 3204642 (Why is no real title available?)
- Eigenvalues and expanders
- Explicit construction of linear sized tolerant networks
- Explicit constructions of linear-sized superconcentrators
- Greed is good: approximating independent sets in sparse and bounded-degree graphs
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Ramanujan graphs
- Randomness in interactive proofs
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- The hardness of approximate optima in lattices, codes, and systems of linear equations
Cited in
(37)- Deterministic tensor completion with hypergraph expanders
- Online admission control and embedding of service chains
- Designing menus of contracts efficiently: the power of randomization
- On the hardness of approximating max-satisfy
- Bi-covering: covering edges with two small subsets of vertices
- Directed Random Dot Product Graphs
- On approximating four covering and packing problems
- Approximate graph products
- Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
- 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
- Traveling salesman problems in temporal graphs
- Differential approximation of MIN SAT, MAX SAT and related problems
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- On Lagrangian Relaxation and Subset Selection Problems
- Derandomized graph product results using the low degree long code
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Scalable secure storage when half the system is faulty
- Local correctability of expander codes
- On codes from hypergraphs.
- Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE
- Randomness buys depth for approximate counting
- On the advantage over a random assignment
- Zero knowledge and the chromatic number
- The complexity and approximability of finding maximum feasible subsystems of linear relations
- Improved non-approximability results for minimum vertex cover with density constraints
- Expander graphs and their applications
- ALMOST EUCLIDEAN SECTIONS OF THE N-DIMENSIONAL CROSS-POLYTOPE USING O(N) RANDOM BITS
- Optimal explicit small-depth formulas for the coin problem
- Improved (In-)Approximability Bounds for d-Scattered Set
- Inequalities for the number of walks in graphs
- Bounded queries, approximations, and the Boolean hierarchy
- Greed is good for deterministic scale-free networks
- Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
- Completeness in approximation classes beyond APX
- How much randomness is needed to convert MA protocols to AM protocols?
- Deterministic document exchange protocols and almost optimal binary codes for edit errors
This page was built for publication: Derandomized graph products
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1842777)
