Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Direct Product Test:
TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

TR17-089 | 11th May 2017
Irit Dinur, Tali Kaufman

High dimensional expanders imply agreement expanders

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree ... more >>>

TR17-181 | 26th November 2017
Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests on graphs and hypergraphs

Revisions: 1

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

TR19-112 | 1st September 2019
Yotam Dikstein, Irit Dinur

Agreement testing theorems on layered set systems

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test.

Previous work has shown that high dimensional expansion ... more >>>

TR23-054 | 20th April 2023
Amey Bhangale, Subhash Khot, Dor Minzer

On Approximability of Satisfiable $k$-CSPs: III

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property ... more >>>

ISSN 1433-8092 | Imprint