Random sampling and approximation of MAX-CSPs
From MaRDI portal
Cites work
- .878-approximation algorithms for MAX CUT and MAX 2SAT
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1263204 (Why is no real title available?)
- scientific article; zbMATH DE number 1301970 (Why is no real title available?)
- scientific article; zbMATH DE number 1754615 (Why is no real title available?)
- scientific article; zbMATH DE number 2119722 (Why is no real title available?)
- MAX-CUT has a randomized approximation scheme in dense graphs
- On the best constants in the Khinchin inequality
- On the discrepancy of combinatorial rectangles
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Probability Inequalities for Sums of Bounded Random Variables
- Property testers for dense constraint satisfaction programs on finite domains
- Property testing and its connection to learning and approximation
- Quick approximation to matrices and applications
- Random sampling and approximation of MAX-CSP problems
Cited in
(26)- Bounds for graph regularity and removal lemmas
- Optimal graphon estimation in cut distance
- Moments of two-variable functions and the uniqueness of graph limits
- A dichotomy for minimum cost graph homomorphisms
- Co-clustering separately exchangeable network data
- Numerical multilinear algebra and its applications
- Grothendieck-type inequalities in combinatorial optimization
- Testing Odd-Cycle-Freeness in Boolean Functions
- Optimal cuts and partitions in tree metrics in polynomial time
- Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
- Sublinear-time Algorithms
- Approximating sparse binary matrices in the cut-norm
- The cut metric for probability distributions
- Sublinear algorithms for MAXCUT and correlation clustering
- Amplification and Derandomization without Slowdown
- Testing odd-cycle-freeness in Boolean functions
- Hypergraph regularity and random sampling
- Local and global expansion in random geometric graphs
- Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
- Random unconditional convergence of Rademacher chaos in L_ and sharp estimates for discrepancy of weighted graphs and hypergraphs
- Pliability and approximating Max-CSPs
- Exploiting dense structures in parameterized complexity
- Why is it easier to predict the epidemic curve than to reconstruct the underlying contact network?
- Interlacing polynomial method for matrix approximation via generalized column and row selection
- Min-CSPs on complete instances. II: Polylogarithmic approximation for Min-NAE-3-SAT
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
This page was built for publication: Random sampling and approximation of MAX-CSPs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1886453)
