Joshua Buresh-Oppenheim, David Mitchell

We prove exponential separations between the sizes of

particular refutations in negative, respectively linear, resolution and

general resolution. Only a superpolynomial separation between negative

and general resolution was previously known. Our examples show that there

is no strong relationship between the size and width of refutations in

negative and ...
more >>>

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

Jakob Nordström

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

Alan Nash, Russell Impagliazzo, Jeff Remmel

Diagonalization is a powerful technique in recursion theory and in

computational complexity \cite{For00}. The limits of this technique are

not clear. On the one hand, many people argue that conflicting

relativizations mean a complexity question cannot be resolved using only

diagonalization. On the other hand, it is not clear that ...
more >>>

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound of

$\Omega{n^{1/(k-1)}}$ on the probabilistic communication

complexity of pointer jumping in a $k$-layered tree, where the

pointers of the $i$-th ...
more >>>

Jakob Nordström, Johan Håstad

Most state-of-the-art satisfiability algorithms today are variants of

the DPLL procedure augmented with clause learning. The main bottleneck

for such algorithms, other than the obvious one of time, is the amount

of memory used. In the field of proof complexity, the resources of

time and memory correspond to the length ...
more >>>

Eli Ben-Sasson, Jakob Nordström

For current state-of-the-art satisfiability algorithms based on the

DPLL procedure and clause learning, the two main bottlenecks are the

amounts of time and memory used. Understanding time and memory

consumption, and how they are related to one another, is therefore a

question of considerable practical importance. In the field of ...
more >>>

Eli Ben-Sasson, Jakob Nordström

The k-DNF resolution proof systems are a family of systems indexed by

the integer k, where the kth member is restricted to operating with

formulas in disjunctive normal form with all terms of bounded arity k

(k-DNF formulas). This family was introduced in [Krajicek 2001] as an

extension of the ...
more >>>

Dmytro Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

Eli Ben-Sasson, Jakob Nordström

For current state-of-the-art satisfiability algorithms based on the DPLL procedure and clause learning, the two main bottlenecks are the amounts of time and memory used. In the field of proof complexity, these resources correspond to the length and space of resolution proofs for formulas in conjunctive normal form (CNF). There ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Properties of Boolean functions on the hypercube that are invariant

with respect to linear transformations of the domain are among some of

the most well-studied properties in the context of property testing.

In this paper, we study a particular natural class of linear-invariant

properties, called matroid freeness properties. These properties ...
more >>>

Zander Kelley, Shachar Lovett, Raghu Meka

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function $f:[N]^3 \to \{0,1\}$, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing ... more >>>