A query efficient non-adaptive long code test with perfect completeness
From MaRDI portal
Publication:3192387
DOI10.1002/rsa.20549zbMath1341.68066OpenAlexW2080994410MaRDI QIDQ3192387
Publication date: 12 October 2015
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/202504
Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Approximation resistant predicates from pairwise independence
- On the approximation resistance of a random predicate
- Noise stability of functions with low influences: invariance and optimality
- Self-testing/correcting with applications to numerical problems
- Gaussian bounds for noise correlation of functions
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Randomly Supported Independence and Resistance
- Linearity testing in characteristic two
- Proof verification and the hardness of approximation problems
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
- Probabilistic checking of proofs
- Logarithmic Sobolev Inequalities
- A Parallel Repetition Theorem
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Testing Basic Boolean Formulae
- Simple analysis of graph tests for linearity and PCP
- Gowers Uniformity, Influence of Variables, and PCPs
- Some optimal inapproximability results
- Some 3CNF Properties Are Hard to Test
- Linear-consistency testing.
