Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOW-DEGREE TESTING:
Reports tagged with low-degree testing:
TR97-010 | 2nd April 1997
Marcos Kiwi

Testing and Weight Distributions of Dual Codes


We study the testing problem, that is, the problem of determining (maybe
probabilistically) if a function to which we have oracle access
satisfies a given property.

We propose a framework in which to formulate and carry out the analyzes
of several known tests. This framework establishes a connection between
more >>>


TR11-059 | 15th April 2011
Elad Haramaty, Amir Shpilka, Madhu Sudan

Optimal testing of multivariate polynomials over small prime fields

We consider the problem of testing if a given function f : \F_q^n \rightarrow \F_q is close to a n-variate degree d polynomial over the finite field \F_q of q elements. The natural, low-query, test for this property would be to pick the smallest dimension t = t_{q,d}\approx d/q such ... more >>>


TR12-045 | 22nd April 2012
Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>


TR14-004 | 30th November 2013
Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

On r-Simple k-Path

An r-simple k-path is a {path} in the graph of length k that
passes through each vertex at most r times. The \simpath{r}{k}
problem, given a graph G as input, asks whether there exists an
r-simple k-path in G. We first show that this problem is
NP-Complete. We then show ... more >>>


TR15-043 | 2nd April 2015
Alan Guo, Elad Haramaty, Madhu Sudan

Robust testing of lifted codes with applications to low-degree testing

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be ``robust'' ... more >>>


TR17-110 | 22nd June 2017
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Axis-Parallel Tests for Tensor Product Codes

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>


TR19-070 | 14th May 2019
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Local Testability in the Non-Signaling Setting

Revisions: 1

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>




ISSN 1433-8092 | Imprint