Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with agreement:
TR04-061 | 30th June 2004
Scott Aaronson

The Complexity of Agreement

A celebrated 1976 theorem of Aumann asserts that honest, rational
Bayesian agents with common priors will never "agree to disagree": if
their opinions about any topic are common knowledge, then those
opinions must be equal. Economists have written numerous papers
examining the assumptions behind this theorem. But two key questions
more >>>

TR15-064 | 19th April 2015
Ilan Komargodski, Pravesh Kothari, Madhu Sudan

Communication with Contextual Uncertainty

Revisions: 1

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... 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-096 | 30th May 2017
Irit Dinur, Inbal Livni Navon

Exponentially Small Soundness for the Direct Product Z-test

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ... 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-126 | 19th September 2019
Irit Dinur, Roy Meshulam

Near Coverings and Cosystolic Expansion -- an example of topological property testing

We study the stability of covers of simplicial complexes. Given a map f:Y?X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called cover-stable. We show that this is equivalent ... more >>>

TR23-119 | 18th August 2023
Yotam Dikstein, Irit Dinur

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Revisions: 1

Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses ... more >>>

TR24-019 | 2nd February 2024
Yotam Dikstein, Irit Dinur, Alexander Lubotzky

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

Revisions: 1

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work.

Derandomized direct product ... more >>>

ISSN 1433-8092 | Imprint