Applications of random algebraic constructions to hardness of approximation
From MaRDI portal
Cites work
- A birthday repetition theorem and complexity of approximating dense CSPs
- A characterization of span program size and improved lower bounds for monotone span programs
- A note on a maximum \(k\)-subset intersection problem
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- A simplified NP-complete satisfiability problem
- Color-coding
- Communication Complexity
- Complexity of Linear Boolean Operators
- Computational complexity of graphs
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Equations over finite fields. An elementary approach
- Explicit two-source extractors and resilient functions
- Exponential separation of information and communication for Boolean functions
- Extremal combinatorics. With applications in computer science
- Extremal graphs without exponentially small bicliques
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Fundamentals of parameterized complexity
- Hardness of approximate nearest neighbor search
- scientific article; zbMATH DE number 3859276 (Why is no real title available?)
- scientific article; zbMATH DE number 3563286 (Why is no real title available?)
- scientific article; zbMATH DE number 1256780 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1142309 (Why is no real title available?)
- scientific article; zbMATH DE number 2120513 (Why is no real title available?)
- scientific article; zbMATH DE number 3305097 (Why is no real title available?)
- Linear codes with exponentially many light vectors
- Linear-time encodable and decodable error-correcting codes
- Matrix rigidity of random Toeplitz matrices
- Maximum subset intersection
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Norm-graphs and bipartite Turán numbers
- Number of Points of Varieties in Finite Fields
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- On discrepancy bounds via dual shatter function
- On hardness of approximation of parameterized set cover and label cover: threshold graphs from error correcting codes
- On the complexity of k-SAT
- On the complexity of closest pair via polar-pair of point-sets
- On the Parameterized Complexity of Approximating Dominating Set
- Parameterized algorithms
- Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
- Parameterized Intractability of Even Set and Shortest Vector Problem
- Paths, Trees, and Flowers
- Probabilistic polynomials and Hamming nearest neighbors
- Problems and results in extremal combinatorics. I.
- Problems and results in extremal combinatorics. II
- Problems and results in extremal combinatorics. III.
- Random algebraic construction of extremal graphs
- Rational exponents in extremal graph theory
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Simple Constructions of Almost k-wise Independent Random Variables
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Some remarks on the Zarankiewicz problem
- Subcubic equivalences between path, matrix, and triangle problems
- Sum-product estimates for rational functions
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The constant inapproximability of the parameterized dominating set problem
- The hardness of embedding grids and walls
- The parameterized complexity of the k-biclique problem
- Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs
- Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
- Which problems have strongly exponential complexity?
This page was built for publication: Applications of random algebraic constructions to hardness of approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6891640)
