Limits on the Rate of Locally Testable Affine-Invariant Codes

No abstract is available for this paper.

• Publication year

  2011

• Venue

  International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

• Publication date

  2011-08-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-22935-0_35
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Locally Decodable Codes

  2012cited by this paper
• Symmetric LDPC Codes are not Necessarily Locally Testable

  2011cited by this paper
• Succinct Representation of Codes with Applications to Testing

  2009cited by this paper
• Optimal Testing of Reed-Muller Codes

  2009cited by this paper
• Locally Testable Codes Require Redundant Testers

  2009cited by this paper
• Towards 3-query locally decodable codes of subexponential length

  2008cited by this paper
• Algebraic property testing: the role of invariance

  2008cited by this paper
• 2-Transitivity is Insufficient for Local Testability

  2008cited by this paper
• New Lower Bounds for General Locally Decodable Codes

  2007cited by this paper
• The PCP theorem by gap amplification

  2006cited by this paper
• A combinatorial characterization of the testable graph properties: it's all about regularity

  2006influential reference
• Graph limits and parameter testing

  2006influential reference
• Low-degree tests at large distances

  2006cited by this paper
• Testing Reed-Muller codes

  2005influential reference
• Simple PCPs with poly-log rate and query complexity

  2005cited by this paper
• Improved Lower Bounds for Locally Decodable Codes and Private Information Retrieval

  2004cited by this paper
• Testing polynomials over general fields

  2004cited by this paper
• Testing low-degree polynomials over prime fields

  2004cited by this paper
• Some 3CNF properties are hard to test

  2003cited by this paper
• The complexity of homomorphism and constraint satisfaction problems seen from the other side

  2003cited by this paper
• Locally testable codes and PCPs of almost-linear length

  2002cited by this paper
• CNF Properties are Hard to Test

  2002cited by this paper
• Lower bounds for linear locally decodable codes and private information retrieval

  2002cited by this paper
• On the efficiency of local decoding procedures for error-correcting codes

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

  1998influential reference
• Property testing and its connection to learning and approximation

  1996cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• Efficient Checking of Polynomials and Proofs and the Hardness of Appoximation Problems

  1995cited by this paper
• Private information retrieval

  1995cited by this paper
• Nearly-linear size holographic proofs

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

  1992cited by this paper
• Checking computations in polylogarithmic time

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

  1990cited by this paper
• Some Results on Cyclic Codes which Are Invariant under the Affine Group and Their Application

  1966cited by this paper

• Codes with locality: Constructions and applications to cryptographic protocols. (Codes à propriétés locales: constructions et applications à des protocoles cryptographiques)

  2018cites this paper
• Locality in coding theory

  2018cites this paper
• Locality via Partially Lifted Codes

  2017cites this paper
• Multi-variate Abstractions of Algebraic Geometry Codes, With Applications

  2016cites this paper
• Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs

  2015cites this paper
• New Directions in Coding Theory : Capacity and Limitations

  2015cites this paper
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

  2015cites this paper
• Additive combinatorics methods in computational complexity

  2014cites this paper
• Absolutely Sound Testing of Lifted Codes

  2013cites this paper
• Strong LTCs with Inverse Poly-Log Rate and Constant Soundness

  2013cites this paper
• Tight Lower Bounds for Testing Linear Isomorphism

  2013influential citation
• A new family of locally correctable codes based on degree-lifted algebraic geometry codes

  2013cites this paper
• New affine-invariant codes from lifting

  2012cites this paper
• Some closure features of locally testable affine-invariant properties

  2012cites this paper
• A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes

  2012cites this paper
• Towards lower bounds on locally testable codes

  2012influential citation
• Sparse affine-invariant linear codes are locally testable

  2012cites this paper
• Algebraic Property Testing

  2011cites this paper
• Reseach of security risk identification based on rough set theory for highway subgrade stability in the slope of reservoir

  2011cites this paper
• Towards lower bounds on locally testable codes via density arguments

  2011cites this paper
• On Sums of Locally Testable Affine Invariant Properties

  2011cites this paper
• Guest column: testing linear properties: some general theme

  2011influential citation
• Noisy Interpolating Sets for Low-Degree Polynomials Zeev Dvir

  2011cites this paper
• Symmetric LDPC Codes are not Necessarily Locally Testable

  2011cites this paper
• Testing Linear Properties: Some general themes

  2011cites this paper
• Limitation on the Rate of Families of Locally Testable Codes

  2010influential citation
• Invariance in Property Testing

  2010cites this paper
• A Unified Framework for Testing Linear-Invariant Properties

  2010cites this paper
• Local computation in codes

  2010cites this paper
• Testing of exponentially large codes, by a new extension to Weil bound for character sums

  2010cites this paper
• Noisy Interpolating Sets for Low Degree Polynomials

  2008cites this paper
• A Unified Framework for Testing Linear-Invariant Properties

  year unknowncites this paper