Gowers uniformity, influence of variables, and PCPs
- 21 May 2006
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
Abstract
No abstract availableKeywords
This publication has 24 references indexed in Scilit:
- On the hardness of approximating vertex coverAnnals of Mathematics, 2005
- Nonconventional ergodic averages and nilmanifoldsAnnals of Mathematics, 2005
- Simple analysis of graph tests for linearity and PCPRandom Structures & Algorithms, 2003
- Some optimal inapproximability resultsJournal of the ACM, 2001
- Linear-Consistency TestingJournal of Computer and System Sciences, 2001
- Free Bits, PCPs, and Nonapproximability---Towards Tight ResultsSIAM Journal on Computing, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- Linearity testing in characteristic twoIEEE Transactions on Information Theory, 1996
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993