Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > B:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

B
TR18-055 | 26th March 2018
Titus Dose

Balance Problems for Integer Circuits

Revisions: 5

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits
computing finite sets of natural numbers. These problems naturally build on problems for integer
expressions and integer circuits studied by Stockmeyer and Meyer (1973),
McKenzie and Wagner (2007),
and Glaßer et al (2010).

Our work shows that the ... more >>>

TR09-012 | 4th February 2009
Noga Alon, Shai Gutner

Balanced Hashing, Color Coding and Approximate Counting

Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a ... more >>>

TR06-088 | 9th July 2006
Per Austrin

Balanced Max 2-Sat might not be the hardest

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

TR11-068 | 27th April 2011
L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

Balls and Bins: Smaller Hash Families and Faster Evaluation

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

TR17-162 | 26th October 2017
Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Barriers for Rank Methods in Arithmetic Complexity

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

TR20-030 | 9th March 2020
Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

Barriers for Rectangular Matrix Multiplication

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

TR15-180 | 4th November 2015
Bo Tang, Jiapeng Zhang

Barriers to Black-Box Constructions of Traitor Tracing Systems

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

TR07-003 | 5th January 2007
Jin-Yi Cai, Pinyan Lu

Bases Collapse in Holographic Algorithms

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

TR14-127 | 11th October 2014
Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

Batch Codes through Dense Graphs without Short Cycles

Consider a large database of $n$ data items that need to be stored using $m$ servers.
We study how to encode information so that a large number $k$ of read requests can be performed \textit{in parallel} while the rate remains constant (and ideally approaches one).
This problem is equivalent ... more >>>

TR01-078 | 6th November 2001
Matthias Krause

BDD-based Cryptanalysis of Keystream Generators

Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes ... more >>>

TR18-111 | 4th June 2018
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,
computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or
$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a
deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing
algorithm to check whether $f \equiv 0$ or ... more >>>

TR18-096 | 13th May 2018
Venkatesan Guruswami, Andrii Riazanov

Beating Fredman-Komlós for perfect $k$-hashing

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>

TR19-108 | 23rd August 2019
Chaoping Xing, chen yuan

Beating the probabilistic lower bound on perfect hashing

Revisions: 2

For an interger $q\ge 2$, a perfect $q$-hash code $C$ is a block code over $\ZZ_q:=\ZZ/ q\ZZ$ of length $n$ in which every subset $\{\bc_1,\bc_2,\dots,\bc_q\}$ of $q$ elements is separated, i.e., there exists $i\in[n]$ such that $\{\proj_i(\bc_1),\proj_i(\bc_2),\dots,\proj_i(\bc_q)\}=\ZZ_q$, where $\proj_i(\bc_j)$ denotes the $i$th position of $\bc_j$. Finding the maximum size $M(n,q)$ ... more >>>

TR15-082 | 13th May 2015
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Beating the random assignment on constraint satisfaction problems of bounded degree

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

TR11-027 | 28th February 2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

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

TR07-109 | 7th October 2007
Venkatesan Guruswami, Atri Rudra

Better Binary List-Decodable Codes via Multilevel Concatenation

We give a polynomial time construction of binary codes with the best
currently known trade-off between rate and error-correction
radius. Specifically, we obtain linear codes over fixed alphabets
that can be list decoded in polynomial time up to the so called
Blokh-Zyablov bound. Our work ... more >>>

TR17-072 | 25th April 2017
Eric Allender, Andreas Krebs, Pierre McKenzie

Better Complexity Bounds for Cost Register Machines

Revisions: 1

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

TR03-080 | 12th November 2003
Venkatesan Guruswami

Better Extractors for Better Codes?

We present an explicit construction of codes that can be list decoded
from a fraction $(1-\eps)$ of errors in sub-exponential time and which
have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal
rate of $\Omega(\eps)$, and is the first sub-exponential complexity
construction to beat the rate of $O(\eps^2)$ achieved by ... more >>>

TR10-164 | 4th November 2010
Falk Unger

Better gates can make fault-tolerant computation impossible

Revisions: 1

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>

TR12-123 | 28th September 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

Better pseudorandom generators from milder pseudorandom restrictions

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

TR20-008 | 26th January 2020
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 1

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined authorized'' sets of parties can reconstruct the secret, and all other unauthorized'' sets learn nothing about $s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

TR04-090 | 3rd November 2004
Kazuyuki Amano, Akira Maruoka

Better Simulation of Exponential Threshold Weights by Polynomial Weights

We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

TR19-168 | 20th November 2019
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Beyond Natural Proofs: Hardness Magnification and Locality

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

TR14-125 | 9th October 2014
Anindya De

Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums

In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}
and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that
more >>>

TR02-005 | 3rd January 2002
A. Pavan, Alan L. Selman

Bi-Immunity Separates Strong NP-Completeness Notions

We prove that if for some epsilon > 0 NP contains a set that is
DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing
complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo
(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the
same consequence using strong ... more >>>

TR13-138 | 5th October 2013
Itai Benjamini, Gil Cohen, Igor Shinkar

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

TR15-096 | 5th June 2015
Abhishek Bhowmick, Shachar Lovett

Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

TR19-029 | 20th February 2019
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

TR16-112 | 18th July 2016
Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

Bicovering: Covering edges with two small subsets of vertices

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

TR15-177 | 9th November 2015
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

Bipartite Perfect Matching is in quasi-NC

Revisions: 2

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

TR09-005 | 7th December 2008
Emanuele Viola

Bit-Probe Lower Bounds for Succinct Data Structures

We prove lower bounds on the redundancy necessary to
represent a set $S$ of objects using a number of bits
close to the information-theoretic minimum $\log_2 |S|$,
while answering various queries by probing few bits. Our
main results are:

\begin{itemize}
\item To represent $n$ ternary values $t \in \zot^n$ in ... more >>>

TR07-042 | 7th May 2007
Zohar Karnin, Amir Shpilka

Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

In this paper we consider the problem of determining whether an
unknown arithmetic circuit, for which we have oracle access,
computes the identically zero polynomial. Our focus is on depth-3
circuits with a bounded top fan-in. We obtain the following
results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

TR01-050 | 24th June 2001
Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

We show that any concurrent zero-knowledge protocol for a non-trivial
language (i.e., for a language outside $\BPP$), whose security is proven
via black-box simulation, must use at least $\tilde\Omega(\log n)$
rounds of interaction. This result achieves a substantial improvement
over previous lower bounds, and is the first bound to rule ... more >>>

TR15-056 | 3rd April 2015
Sanjam Garg, Steve Lu, Rafail Ostrovsky

Black-Box Garbled RAM

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

TR11-046 | 2nd April 2011
Shubhangi Saraf, Ilya Volkovich

Black-Box Identity Testing of Depth-4 Multilinear Circuits

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

TR10-102 | 12th May 2010
Per Kristian Lehre, Carsten Witt

Black-Box Search by Unbiased Variation

Revisions: 1

The complexity theory for black-box algorithms, introduced by
Droste et al. (2006), describes common limits on the efficiency of
a broad class of randomised search heuristics. There is an
obvious trade-off between the generality of the black-box model
and the strength of the bounds that can be proven in such ... more >>>

TR07-044 | 23rd April 2007
Philipp Hertel

Black-White Pebbling is PSPACE-Complete

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

TR10-167 | 5th November 2010

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed ... more >>>

TR09-032 | 16th April 2009
Neeraj Kayal, Shubhangi Saraf

Blackbox Polynomial Identity Testing for Depth 3 Circuits

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

TR12-160 | 20th November 2012
Frederic Green, Daniel Kreymer, Emanuele Viola

Block-symmetric polynomials correlate with parity better than symmetric

We show that degree-$d$ block-symmetric polynomials in
$n$ variables modulo any odd $p$ correlate with parity
exponentially better than degree-$d$ symmetric
polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995 \cdot p^t - 1,p^t)$ for some $t \ge 1$. For these
infinitely many degrees, our result ... more >>>

TR95-049 | 19th October 1995
Anna Gal, Avi Wigderson

Boolean complexity classes vs. their arithmetic analogs

This paper provides logspace and small circuit depth analogs
of the result of Valiant-Vazirani, which is a randomized (or
nonuniform) reduction from NP to its arithmetic analog ParityP.
We show a similar randomized reduction between the
Boolean classes NL and semi-unbounded fan-in Boolean circuits and
their arithmetic counterparts. These ... more >>>

TR18-075 | 23rd April 2018
Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

Boolean function analysis on high-dimensional expanders

Revisions: 2

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

TR13-191 | 26th December 2013
Petr Savicky

Boolean functions with a vertex-transitive group of automorphisms

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

more >>>

TR13-141 | 8th October 2013
Leonid Gurvits

Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with
boolean matrices with prescribed row and (uniformly bounded) column sums within simply ... more >>>

TR07-131 | 16th November 2007
Satyen Kale

Boosting and hard-core set constructions: a simplified approach

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>>

TR18-199 | 24th November 2018
Lijie Chen, Roei Tell

Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative ... more >>>

TR18-035 | 21st February 2018
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Bootstrapping variables in algebraic circuits

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

TR13-135 | 27th September 2013
Scott Aaronson

BosonSampling Is Far From Uniform

Revisions: 2

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

TR20-055 | 22nd April 2020
Ashutosh Kumar, Raghu Meka, David Zuckerman

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

TR04-121 | 7th December 2004
Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

In this paper we study the complexity of Bounded Color
Multiplicity Graph Isomorphism (BCGI): the input is a pair of
vertex-colored graphs such that the number of vertices of a given
color in an input graph is bounded by $b$. We show that BCGI is in the
#L hierarchy ... more >>>

TR99-012 | 19th April 1999
Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Bounded Depth Arithmetic Circuits: Counting and Closure

Constant-depth arithmetic circuits have been defined and studied
in [AAD97,ABL98]; these circuits yield the function classes #AC^0
and GapAC^0. These function classes in turn provide new
characterizations of the computational power of threshold circuits,
and provide a link between the circuit classes AC^0 ... more >>>

TR16-099 | 13th June 2016
Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ is weighted symmetric if there exist a function $g: \mathbb{Z} \to \{0,1\}$ and integers $w_0, w_1, \ldots, w_n$ such that $f(x_1,\ldots,x_n) = g(w_0+\sum_{i=1}^n w_i x_i)$ holds.

In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, ... more >>>

TR09-117 | 18th November 2009
Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

TR09-016 | 21st February 2009
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

Bounded Independence Fools Halfspaces

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

TR16-169 | 3rd November 2016
Elad Haramaty, Chin Ho Lee, Emanuele Viola

Bounded independence plus noise fools products

Let $D$ be a $b$-wise independent distribution over
$\{0,1\}^m$. Let $E$ be the noise'' distribution over
$\{0,1\}^m$ where the bits are independent and each bit is 1
with probability $\eta/2$. We study which tests $f \colon \{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,
$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ... more >>>

TR16-102 | 4th July 2016
Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Bounded independence vs. moduli

Revisions: 1

Let $k=k(n)$ be the largest integer such that there
exists a $k$-wise uniform distribution over $\zo^n$ that
is supported on the set $S_m := \{x \in \zo^n : \sum_i x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We
2^{\{1,\ldots,r\}}$such that$|A\cap B|\in L$for any$A\in{\cal A}$,$B\in{\cal B}$. We are interested in the maximal product$|{\cal A}|\cdot|{\cal B}|$, given$r$and$L$. We give asymptotically optimal bounds for$L$containing only elements of$s<q$residue classes modulo ... more >>> TR16-013 | 12th January 2016 Ludwig Staiger Bounds on the Kolmogorov complexity function for infinite words Revisions: 1 The Kolmogorov complexity function of an infinite word$\xi$maps a natural number to the complexity$K(\xi|n)$of the$n$-length prefix of$\xi$. We investigate the maximally achievable complexity function if$\xi$is taken from a constructively describable set of infinite words. Here we are interested ... more >>> TR03-029 | 1st April 2003 Philippe Moser BPP has effective dimension at most 1/2 unless BPP=EXP We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP. Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP on infinitely many input lengths. We also prove that BPP has measure zero in the smaller complexity class ... more >>> TR11-103 | 31st July 2011 Yang Li BQP and PPAD 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 >>> TR09-104 | 26th October 2009 Scott Aaronson BQP and the Polynomial Hierarchy The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there ... more >>> TR01-048 | 3rd June 2001 Jui-Lin Lee Branching program, commutator, and icosahedron, part I In this paper we give a direct proof of$N_0=N_0^\prime$, i.e., the equivalence of uniform$NC^1$based on different recursion principles: one is OR-AND complete binary tree (in depth$\log n$) and the other is the recursion on notation with value bounded in$[0,k]$and$|x|(=n)$many ... more >>> TR05-098 | 4th September 2005 Oded Goldreich Bravely, Moderately: A Common Theme in Four Recent Results We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, more >>> TR05-124 | 2nd November 2005 Kooshiar Azimian Breaking Diffie-Hellman is no Easier than Root Finding In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect ... more >>> TR10-068 | 15th April 2010 Shir Ben-Israel, Eli Ben-Sasson, David Karger Breaking local symmetries can dramatically reduce the length of propositional refutations This paper shows that the use of local symmetry breaking'' can dramatically reduce the length of propositional refutations. For each of the three propositional proof systems known as (i) treelike resolution, (ii) resolution, and (iii) k-DNF resolution, we describe families of unsatisfiable formulas in conjunctive normal form (CNF) that are ... more >>> TR07-098 | 2nd October 2007 Tali Kaufman, Simon Litsyn, Ning Xie Breaking the$\epsilon$-Soundness Bound of the Linearity Test over GF(2) For Boolean functions that are$\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted$\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>> TR14-009 | 21st January 2014 Alexander A. Sherstov Breaking the Minsky-Papert Barrier for Constant-Depth Circuits The threshold degree of a Boolean function$f$is the minimum degree of a real polynomial$p$that represents$f$in sign:$f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth$\{\wedge,\vee\}$-circuit in$n$variables with threshold degree$\Omega(n^{1/3}).$This bound underlies ... more >>> TR13-160 | 20th November 2013 Zeev Dvir, Shubhangi Saraf, Avi Wigderson Breaking the quadratic barrier for 3-LCCs over the Reals We prove that 3-query linear locally correctable codes over the Reals of dimension$d$require block length$n>d^{2+\lambda}$for some fixed, positive$\lambda >0$. Geometrically, this means that if$n$vectors in$R^d$are such that each vector is spanned by a linear number of disjoint triples of others, then ... more >>> TR19-054 | 9th April 2019 Joshua Brakensiek, Venkatesan Guruswami Bridging between 0/1 and Linear Programming via Random Walks Under the Strong Exponential Time Hypothesis, an integer linear program with$n$Boolean-valued variables and$m$equations cannot be solved in$c^n$time for any constant$c < 2$. If the domain of the variables is relaxed to$[0,1]$, the associated linear program can of course be solved in polynomial ... more >>> TR16-090 | 27th May 2016 Bernhard Haeupler, Ameya Velingker Bridging the Capacity Gap Between Interactive and One-Way Communication We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise. Recently, Haeupler (FOCS '14) showed that if an$\epsilon > 0\$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

TR19-072 | 17th May 2019
Lijie Chen, Ofer Grossman

Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

TR15-202 | 11th December 2015
Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Building above read-once polynomials: identity testing and hardness of representation

Polynomial Identity Testing (PIT) algorithms have focused on
polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted
formulas (ROFs) and are the simplest of read-restricted polynomials.
Building structures above these, we show the following:
\begin{enumerate}
\item A deterministic polynomial-time non-black-box ... more >>>

TR10-127 | 9th August 2010
Brett Hemenway, Rafail Ostrovsky

Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ... more >>>

TR18-172 | 11th October 2018
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Building Strategies into QBF Proofs

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

TR06-068 | 6th April 2006
Patrick Briest, Piotr Krysta

Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

TR10-177 | 16th November 2010
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>

ISSN 1433-8092 | Imprint