We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right] $ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right) $ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>>

We consider two basic computational problems
regarding discrete probability distributions:
(1) approximating the statistical difference (aka variation distance)
between two given distributions,
and (2) approximating the entropy of a given distribution.
Both problems are considered in two different settings.
In the first setting the approximation algorithm
more >>>

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>>

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of ... more >>>

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.
The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ... more >>>

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>

We establish new hardness amplification results for one-way functions in which each input bit influences only a small number of output bits (a.k.a. input-local functions). Our transformations differ from previous ones in that they approximately preserve input locality and at the same time retain the input size of the original ... more >>>

Sublinear time algorithms represent a new paradigm
in computing, where an algorithm must give some sort
of an answer after inspecting only a very small portion
of the input. We discuss the types of answers that
one can hope to achieve in this setting.

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>>

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... more >>>

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

We initiate a study of input-oblivious proof systems, and present a few preliminary results regarding such systems.
Our results offer a perspective on the intersection of the non-uniform complexity class P/poly with uniform complexity classes such as NP and IP.
In particular, we provide a uniform complexity formulation of the ... more >>>

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation
resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ... more >>>

The bin packing problem is to find the minimum
number of bins of size one to pack a list of items with sizes
$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects
a random element from the input list each time, we develop a
randomized $O({n(\log n)(\log\log n)\over ... more >>>

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>>

Locally decodable codes
are error correcting codes with the extra property that, in order
to retrieve the correct value of just one position of the input with
high probability, it is
sufficient to read a small number of
positions of the corresponding,
possibly corrupted ... more >>>

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>

In recent results the complexity of isomorphism testing on
graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].
The computation of canonical forms or a canonical labeling provides more information than
isomorphism testing.
Whether canonization is in NC or even TC$^1$ was stated ... more >>>

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>

We prove that any propagating E0L system cannot generate the language containing all words of the form w#w. This result, together with some known ones, enable us to conclude that the flip-pushdown automata with k pushdown reversals (i.e. the pushdown automata with the ability to flip its pushdown) and E0L ... more >>>

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.
This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.
more >>>

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality ... more >>>

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

We report on some initial results of a brute-force search for determining the maximum correlation between degree-$d$ polynomials modulo $p$ and the $n$-bit mod $q$ function. For various settings of the parameters $n,d,p,$ and $q$, our results indicate that symmetric polynomials yield the maximum correlation. This contrasts with the previously-analyzed ... more >>>

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

Property testing is concerned with deciding whether an object
(e.g. a graph or a function) has a certain property or is ``far''
(for a prespecified distance measure) from every object with
that property. In this work we consider the property of being
computable by a read-once ... more >>>

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic
identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

We revisit the notion of a {\em targeted canonical derandomizer},
introduced in our recent ECCC Report (TR10-135) as a uniform notion of
a pseudorandom generator that suffices for yielding BPP=P.
The original notion was derived (as a variant of the standard notion
of a canonical derandomizer) by providing both ... more >>>

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>>

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \
$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \
local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$
measures the quality of the ... more >>>

Given two sets $A,B\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $y\in B$. We prove an inequality showing that no two sets of large enough Gaussian measure (at least $e^{-\delta n}$ for some constant $\delta >0$) ... more >>>

The group isomorphism problem consists in deciding whether two groups $G$ and $H$
given by their multiplication tables are isomorphic.
An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic
self-correcting algorithm that, with high probability, can correct any coordinate of the
codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the
coordinates are corrupted. LCC's are a stronger form ... more >>>

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.
An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ... more >>>

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)
proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ... more >>>

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 >>>

We show that two complexity classes introduced about two decades ago are equal. ReachUL is the class of problems decided by nondeterministic log-space machines which on every input have at most one computation path from the start configuration to any other configuration. ReachFewL, a natural generalization of ReachUL, is the ... more >>>

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>

We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>>

In the gap Hamming distance problem, two parties must
determine whether their respective strings $x,y\in\{0,1\}^n$
are at Hamming distance less than $n/2-\sqrt n$ or greater
than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and
Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound
on the randomized communication ... more >>>

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with ... more >>>

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. ... more >>>

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

The present paper generalises results by Lutz and Ryabko. We prove a
martingale characterisation of exact Hausdorff dimension. On this base we
introduce the notion of exact constructive dimension of (sets of) infinite
strings.

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the
... more >>>

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous
constructions. In particular, we ... more >>>

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>>

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

Affine-invariant properties are an abstract class of properties that generalize some
central algebraic ones, such as linearity and low-degree-ness, that have been
studied extensively in the context of property testing. Affine invariant properties
consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all
properties that form ... more >>>

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

Assume that Alice is running a program $P$ on a RAM, and an adversary
Bob would like to get some information about the input or output of the
program. At each time, during the execution of $P$, Bob is able to see
the addresses of the memory cells involved in ... more >>>

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several
settings.

Decomposition theorems in classical Fourier analysis enable us to express a bounded function in terms of few linear phases with large Fourier coefficients plus a part that is pseudorandom with respect to linear phases. The Goldreich-Levin algorithm can be viewed as an algorithmic analogue of such a decomposition as it ... more >>>

Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>

In [IPL2005],
Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:
for some constant $c>0$:
\[
\left(1+\frac{\log n}{n}-\frac{c}{n}\right)
\frac{2^n}{n}
\leq
L(n)
\leq
\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)
\frac{2^n}{n}.
\]
In this note,
we announce a modest ... more >>>

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

Let $f$ be a non-commutative polynomial such that $f=0$ if we assume that the variables in $f$ commute. Let $Q(f)$ be the smallest $k$ such that there exist polynomials $g_1,g_1', g_2, g_2',\dots, g_k, g_k' $ with \[f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,\]
where $[g,h]=gh-hg$. Then $Q(f)\leq {n\choose 2}$, where ... more >>>

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for ... more >>>

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

We show that the black-box complexity with memory restriction one of the $n$-dimensional $\onemax$ function class is at most $2n$. This disproves the $\Theta(n \log n)$ conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006) 525--544).

In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>>

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

In the setting known as DLOGTIME-uniformity,
the fundamental complexity classes
$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several
robust characterizations.
In this paper we refine uniformity further and examine the impact
of these refinements on $NC^1$ and its subclasses.
When applied to the logarithmic circuit depth characterization of $NC^1$,
some refinements leave ... more >>>

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

We study the lift-and-project procedures of Lovasz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We ... more >>>

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani ... more >>>

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small
redundancy, low locality for information coordinates, large distance, and ... more >>>

In this paper, we study the problem of testing the conductance of a
given graph in the general graph model. Given distance parameter
$\varepsilon$ and any constant $\sigma>0$, there exists a tester
whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log
n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where
$n$ is the number of vertices and $m$ is the number ... more >>>

For each natural number $d$ we consider a finite structure $M_{d}$ whose
universe is the set of all $0,1$-sequence of length $n=2^{d}$, each
representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace
$ in binary form.
The operations included in the structure are the
constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

We initiate the study of the relationship between two complexity classes, BQP
(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,
Directed). We first give a conjecture that PPAD is contained in BQP, and show
a necessary and sufficient condition for the conjecture to hold. Then we prove
that the conjecture ... more >>>

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... more >>>

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>>

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the ... more >>>

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ... more >>>

We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), {\em without Gentry's bootstrapping procedure}.

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

The 3SUM problem asks if there are three integers $a,b,c$ summing to $0$ in a given set of $n$ integers of magnitude poly($n$). Patrascu (STOC '10) reduces solving 3SUM in time $n^{2-\Omega(1)}$ to listing $m$ triangles in a graph with $m$ edges in time $m^{4/3-\Omega(1)}$.
In this note we present ... more >>>

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $D$ that is $\delta$-dense in a distribution that is ... more >>>

We study the computability of one-way functions and pseudorandom generators
by monotone circuits, showing a substantial gap between the two:
On one hand, there exist one-way functions that are computable
by (uniform) polynomial-size monotone functions, provided (of course)
that one-way functions exist at all.
On the other hand, ... more >>>

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

The primary goal of this paper is to define and study the interactive information complexity of functions. Let $f(x,y)$ be a function, and suppose Alice is given $x$ and Bob is given $y$. Informally, the interactive information complexity $IC(f)$ of $f$ is the least amount of information Alice and Bob ... more >>>

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was ... more >>>

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show ... more >>>

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

We construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $D:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $D(V)=\set{0,1}$. This improves the best previous construction of Ben-Sasson and Kopparty ... more >>>

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]
that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most
$$
\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),
$$
and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:
every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

Suppose $f$ is a univariate polynomial of degree $r=r(n)$ that is computed by a size $n$ arithmetic circuit.
It is a basic fact of algebra that a nonzero univariate polynomial of degree $r$ can vanish on at most $r$ points. This implies that for checking whether $f$ is identically zero, ... more >>>

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

In this paper we introduce a new type of probabilistic search algorithm, which we call the
{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,
and to produce a correct and {\it unique} solution with high probability.
We argue the applicability of such algorithms ... more >>>

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>>

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

The long code is a central tool in hardness of approximation, especially in
questions related to the unique games conjecture. We construct a new code that
is exponentially more ecient, but can still be used in many of these applications.
Using the new code we obtain exponential improvements over several ... more >>>

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic
communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$
These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties
were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ... more >>>

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$
satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ... more >>>

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.
The obvious way to construct such a reduction is via a {\em planarizing ... more >>>

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code
$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,
using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>>

Locally Decodable Code (LDC) is a code that encodes a message in a way that one can decode any particular symbol of the message by reading only a constant number of locations, even if a constant fraction of the encoded message is adversarially
corrupted.

In this paper we ... more >>>

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

We study the approximation hardness of the Shortest Superstring, the Maximal Compression and
the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem.
We introduce a new reduction method that produces strongly restricted instances of
the Shortest Superstring problem, in which the maximal orbit size is eight
(with no ... more >>>

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>>

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\begin{enumerate}
\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ... more >>>

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.

An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least $(1-g(\varepsilon))$-fraction of the constraints given a $(1-\varepsilon)$-satisfiable instance, where $g(\varepsilon) \rightarrow 0$ as $\varepsilon \rightarrow 0$, $g(0)=0$.
Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ... more >>>

This paper provides the first general technique for proving information lower bounds on two-party
unbounded-rounds communication problems. We show that the discrepancy lower bound, which
applies to randomized communication complexity, also applies to information complexity. More
precisely, if the discrepancy of a two-party function $f$ with respect ... more >>>

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

Assume that $NP\ne RP$. Gutfreund, Shaltiel, and Ta-Shma in [Computational Complexity 16(4):412-441 (2007)] have proved that for every randomized polynomial time decision algorithm $D$ for SAT there is a polynomial time samplable distribution such that $D$ errs with probability at least $1/6-\epsilon$ on a random formula chosen with respect to ... more >>>

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in ... more >>>

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\begin{equation} \label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n
\end{equation}
We prove in this paper the following generalization (or just clever ... more >>>

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

A discrete distribution $p$, over $[n]$, is a $k$-histogram if its probability distribution function can be
represented as a piece-wise constant function with $k$ pieces. Such a function
is
represented by a list of $k$ intervals and $k$ corresponding values. We consider
the following problem: given a collection of samples ... more >>>

We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting.

Our characterization is enabled by a novel, constructive proof of Border's theorem [Border ... more >>>

We consider first order logic over words and show FO+MOD[<] is contained in MAJ[<] with three variables.
It is known that for the classes FO[<], FO+MOD[<], FO+GROUP[<] three variables suffice. In the case of MOD[<] even two variables are sufficient.

As a consequence we know that if TC^ 0 neq ... more >>>

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>