Simple analysis of graph tests for linearity and PCP

No abstract is available for this paper.

• Publication year

  2001

• Venue

  Proceedings 16th Annual IEEE Conference on Computational Complexity

• Publication date

  2001-06-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/CCC.2001.933891
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Non-approximability of Non-Boolean Predicates

  2001cited by this paper
• Some optimal inapproximability results

  2001influential reference
• The Probablistic Method

  2000cited by this paper
• A PCP characterization of NP with optimal amortized query complexity

  2000influential reference
• Linear Consistency Testing

  1999cited by this paper
• Probabilistic checking of proofs: a new characterization of NP

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Probabilistically checkable proofs and the testing of hadamard-like codes

  1996cited by this paper
• A threshold of ln n for approximating set cover (preliminary version)

  1996cited by this paper
• Interactive proofs and the hardness of approximating cliques

  1996cited by this paper
• Free bits, PCPs and non-approximability-towards tight results

  1995cited by this paper
• Linearity testing in characteristic two

  1995cited by this paper
• A parallel repetition theorem

  1995cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper
• Hardness vs. randomness

  1988cited by this paper
• The Construction of Graphs.

  1953cited by this paper

• A General Framework for Low Soundness Homomorphism Testing

  2025cites this paper
• Finding Large Sets Without Arithmetic Progressions of Length Three: An Empirical View and Survey II

  2025cites this paper
• Homomorphism Testing with Resilience to Online Manipulations

  2025cites this paper
• On Optimal Testing of Linearity

  2024cites this paper
• Catalytic Communication

  2024cites this paper
• Property Testing with Online Adversaries

  2023cites this paper
• Bridge Girth: A Unifying Notion in Network Design

  2022influential citation
• On Regularity Lemma and Barriers in Streaming and Dynamic Matching

  2022cites this paper
• Sublinear-Time Computation in the Presence of Online Erasures

  2021cites this paper
• Beating Two-Thirds For Random-Order Streaming Matching

  2021cites this paper
• Sublinear-Time Computation in the Presence of An Online Adversary

  2021cites this paper
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

  2021cites this paper
• Equivalences between Non-trivial Variants of 3LDT and Conv3LDT

  2020cites this paper
• All non-trivial variants of 3-LDT are equivalent

  2020cites this paper
• Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

  2020cites this paper
• Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling

  2019cites this paper
• Colorings with only rainbow arithmetic progressions

  2019cites this paper
• Sparse Hypergraphs with Applications to Coding Theory

  2019cites this paper
• Limitation of the BLR testing in estimating nonlinearity ( Extended Abstract )

  2019cites this paper
• Universally Sparse Hypergraphs with Applications to Coding Theory

  2019cites this paper
• Mathematics and Computation

  2019cites this paper
• On non-optimally expanding sets in Grassmann graphs

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• N ov 2 01 8 On The Communication Complexity of High-Dimensional Permutations Nati Linial

  2018cites this paper
• SETH-based Lower Bounds for Subset Sum and Bicriteria Path

  2017cites this paper
• On The Communication Complexity of High-Dimensional Permutations

  2017cites this paper
• An Improved Dictatorship Test with Perfect Completeness

  2017cites this paper
• On Estimating Maximum Matching Size in Graph Streams

  2017cites this paper
• Approximation Resistance from Pairwise-Independent Subgroups

  2016cites this paper
• Linearity and Group Homomorphism Testing / Testing Hadamard Codes

  2015cites this paper
• On graphs decomposable into induced matchings of linear sizes

  2015cites this paper
• On the power of the congested clique model

  2014cites this paper
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

  2014cites this paper
• A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

  2014cites this paper
• Hardness of Maximum Constraint Satisfaction

  2013cites this paper
• Towards an optimal query efficient PCP?

  2013cites this paper
• Approximation resistance from pairwise independent subgroups

  2013cites this paper
• On the communication and streaming complexity of maximum bipartite matching

  2012cites this paper
• On the Usefulness of Predicates

  2012cites this paper
• Black-Box Reductions in Mechanism Design

  2011cites this paper
• Nearly complete graphs decomposable into large induced matchings and their applications

  2011cites this paper
• Sparse instances of hard problems

  2011cites this paper
• Characterizations of locally testable linear- and affine-invariant families

  2011cites this paper
• Sublinear Time Algorithms

  2011cites this paper
• On the derandomization of the graph test for homomorphism over groups

  2011influential citation
• Algebraic Property Testing

  2011cites this paper
• A query efficient non‐adaptive long code test with perfect completeness

  2010cites this paper
• Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphs

  2010cites this paper
• Hardness of Finding Independent Sets in Almost q-Colorable Graphs

  2010cites this paper
• Randomness-efficient Low Degree Tests and Short PCPs via Epsilon-Biased Sets

  2010influential citation
• Breaking the Epsilon-Soundness Bound of the Linearity Test over GF(2)

  2010cites this paper
• Breaking the epsilon-Soundness Bound of the Linearity Test over Gf(2)

  2010cites this paper
• Query-Efficient Dictatorship Testing with Perfect Completeness

  2010cites this paper
• A Fourier-Analytic Approach to Reed–Muller Decoding

  2010cites this paper
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

  2010influential citation
• Lec . 6 : Linearity Testing over GF ( 2 ) via Fourier Analysis

  2010cites this paper
• Approximating np-hard problems efficient algorithms and their limits

  2009cites this paper
• Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma

  2009cites this paper
• The Gowers norm in the testing of Boolean functions

  2009cites this paper
• Course 236610 : Research Laboratory in Theoretical Computer Science

  2009cites this paper
• Breaking the epsilon-Soundness Bound of the Linearity Test over GF(2)

  2008cites this paper
• Two Query PCP with Sub-Constant Error

  2008cites this paper
• Finding large 3-free sets I: The small n case

  2008cites this paper
• Distribution of subgraphs of random regular graphs

  2008cites this paper
• A Hypergraph Dictatorship Test with Perfect Completeness

  2008influential citation
• Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

  2008cites this paper
• Testing Linear-Invariant Non-Linear Properties

  2008cites this paper
• Linearity Testing/Testing Hadamard Codes

  2008cites this paper
• Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness

  2008cites this paper
• Derandomizing Graph Tests for Homomorphism

  2008cites this paper
• Intractability Results for some Computational Problems

  2008cites this paper
• Eigenvalues of Euclidean random matrices

  2008cites this paper
• 2 KEY RESULTS

  2007cites this paper
• On An Extremal Hypergraph Problem Of Brown, Erdős And Sós

  2006cites this paper
• Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion

  2006cites this paper
• New Hardness Results for Undirected Edge Disjoint Paths

  2005cites this paper
• Beating a Random Assignment

  2005cites this paper
• Guest column: inapproximability results via Long Code based PCPs

  2005cites this paper
• Testing Periodicity

  2005cites this paper
• Gowers uniformity, influence of variables, and PCPs

  2005cites this paper
• More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP

  2005cites this paper
• Hardness of the undirected edge-disjoint paths problem with congestion

  2005cites this paper
• Efficient testing of groups

  2005cites this paper
• Beating a Random Assignment : Approximating Constraint Satisfaction Problems

  2005cites this paper
• Inapproximability of Combinatorial Optimization Problems

  2004cites this paper
• Derandomizing homomorphism testing in general groups

  2004cites this paper
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets

  2003influential citation
• Property testing: theory and applications

  2003cites this paper
• On probabilistic proof systems and hardness of approximation

  2002cites this paper
• Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs

  2002cites this paper
• Monotonicity testing over general poset domains

  2002influential citation
• Query efficient PCPs with perfect completeness

  2001influential citation
• A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

  year unknowncites this paper
• Cse 533: the Pcp Theorem and Hardness of Approximation Lecture 1: Introduction 1 Proof, and the Pcp Theorem

  year unknowncites this paper
• Lecture 25: Hardness of Max-kcsps and Max-independent-set

  year unknowncites this paper
• Testing Periodicity Extended

  year unknowncites this paper