Eric Blais, Clement Canonne, Tom Gur

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

Anat Ganor, Karthik C. S.

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

Young Kun Ko, Arial Schvartzman

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Andrei Romashchenko, Marius Zimand

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings

$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that

two parties, one having $x$ and the complexity profile of the pair and the ...
more >>>

Jayadev Acharya, Clement Canonne, Himanshu Tyagi

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

Mark Bun, Nikhil Mande, Justin Thaler

The communication class $UPP^{cc}$ is a communication analog of the Turing Machine complexity class $PP$. It is characterized by a matrix-analytic complexity measure called sign-rank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds.

For a communication problem ... more >>>

Amit Chakrabarti, Prantar Ghosh

We give new algorithms in the annotated data streaming setting---also known as verifiable data stream computation---for certain graph problems. This setting is meant to model outsourced computation, where a space-bounded verifier limited to sequential data access seeks to overcome its computational limitations by engaging a powerful prover, without needing to ... more >>>

Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi

Lifting theorems are theorems that relate the query complexity of a function $f:\left\{ 0,1 \right\}^n\to \left\{ 0,1 \right\}$ to the communication complexity of the composed function $f\circ g^n$, for some “gadget” $g:\left\{ 0,1 \right\}^b\times \left\{ 0,1 \right\}^b\to \left\{ 0,1 \right\}$. Such theorems allow transferring lower bounds from query complexity to ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an $NP$ oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... more >>>

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>