Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR08-074 | 19th July 2008
Neeraj Kayal, Timur Nezhmetdinov

Factoring groups efficiently

We give a polynomial time algorithm that computes a
decomposition of a finite group G given in the form of its
multiplication table. That is, given G, the algorithm outputs two
subgroups A and B of G such that G is the direct product
of A ... more >>>

TR14-056 | 18th April 2014
Zeev Dvir, Rafael Mendes de Oliveira

Factors of Sparse Polynomials are Sparse

Revisions: 1 , Comments: 1

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$
has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees
of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ... more >>>

TR13-014 | 11th January 2013
Zvika Brakerski, Moni Naor

Fast Algorithms for Interactive Coding

Consider two parties who wish to communicate in order to execute some interactive protocol $\pi$. However, the communication channel between them is noisy: An adversary sees everything that is transmitted over the channel and can change a constant fraction of the bits as he pleases, thus interrupting the execution of ... more >>>

TR14-117 | 18th August 2014
Shiva Manne, Manjish Pal

Fast Approximate Matrix Multiplication by Solving Linear Systems

Comments: 1

In this paper, we present novel deterministic algorithms for multiplying two $n \times n$ matrices approximately. Given two matrices $A,B$ we return a matrix $C'$ which is an \emph{approximation} to $C = AB$. We consider the notion of approximate matrix multiplication in which the objective is to make the Frobenius ... more >>>

TR07-070 | 11th June 2007
Nir Ailon, Edo Liberty

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

The Fast Johnson-Lindenstrauss Transform was recently discovered by
Ailon and Chazelle as a technique for performing fast dimension
reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d,
k^3\})$, where $k$ is the target lower dimension. This beats the
naive $O(dk)$ achieved by multiplying by random dense matrices, as
noticed ... more >>>

TR08-023 | 10th January 2008
Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

Fast Integer Multiplication using Modular Arithmetic

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for
multiplying two $N$-bit integers that improves the $O(N\cdot \log
N\cdot \log\log N)$ algorithm by
Sch\"{o}nhage-Strassen. Both these algorithms use modular
arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log
N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over
complex numbers as opposed to ... more >>>

TR16-019 | 5th February 2016
Ran Raz

Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning

We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial.

More formally, in the problem of ... more >>>

TR14-154 | 20th November 2014
Andris Ambainis, Yuval Filmus, Francois Le Gall

Fast Matrix Multiplication: Limitations of the Laser Method

Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time $O(n^{2.3755})$. Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time $O(n^{2.3729})$. These algorithms are obtained by analyzing higher ... more >>>

TR16-082 | 22nd May 2016
Benny Applebaum, Pavel Raykov

Fast Pseudorandom Functions Based on Expander Graphs

We present direct constructions of pseudorandom function (PRF) families based on Goldreich's one-way function. Roughly speaking, we assume that non-trivial local mappings $f:\{0,1\}^n\rightarrow \{0,1\}^m$ whose input-output dependencies graph form an expander are hard to invert. We show that this one-wayness assumption yields PRFs with relatively low complexity. This includes weak ... more >>>

TR17-134 | 8th September 2017
Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Revisions: 1

The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to ... more >>>

TR06-111 | 18th July 2006
Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

We present two new methods for finding a lowest common ancestor (LCA)
for each pair of vertices of a directed acyclic graph (dag) on
n vertices and m edges.

The first method is a natural approach that solves the all-pairs LCA
problem for the input dag in time O(nm).

The ... more >>>

TR09-065 | 31st July 2009
Panagiotis Voulgaris, Daniele Micciancio

Faster exponential time algorithms for the shortest vector problem

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$.
This improves the best previously known algorithm by Ajtai, Kumar ... more >>>

TR14-111 | 15th August 2014
Vikraman Arvind, Gaurav Rattan

Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

We give a $O^*(k^{O(k)})$ time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by $k$ which improves on the previous
best running time bound of $O^*(2^{O(k^2/\log

more >>>

TR10-152 | 6th October 2010
Alexey Pospelov

Faster Polynomial Multiplication via Discrete Fourier Transforms

We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different ... more >>>

TR12-111 | 5th September 2012
Venkatesan Guruswami, Ali Kemal Sinop

Faster SDP hierarchy solvers for local rounding algorithms

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>

TR94-011 | 12th December 1994
R. Beigel, W. Hurwood, N. Kahale

Fault Diagnosis in a Flash

We consider the fault diagnosis problem: how to use parallel testing
rounds to identify which processors in a set are faulty. We prove
that 4 rounds suffice when 3% or less of the processors are faulty,
and 4 rounds are necessary when any nontrivial constant fraction of
the processors are ... more >>>

TR15-059 | 10th April 2015
Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

Feasible Interpolation for QBF Resolution Calculi

In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or expansion-based solving. This both provides the first general lower bound method for QBF ... more >>>

TR95-004 | 1st January 1995
Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

It was shown some years ago that the computation time for many important
Boolean functions of n arguments on concurrent-read exclusive-write
parallel random-access machines
(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.
On the other hand, it ... more >>>

TR17-144 | 27th September 2017
Moritz Müller, Ján Pich

Feasibly constructive proofs of succinct weak circuit lower bounds

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

TR03-016 | 15th January 2003
Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

In this work, we study the stability of the {\sf FIFO} ({\sf
First-In-First-Out}) protocol in the context of Adversarial
Queueing Theory. As an important intermediate step, we consider
{\em dynamic capacities}, where each network link capacity may
arbitrarily take on values in the two-valued set of integers
$\{1,C\}$ for $C>1$ ... more >>>

TR06-115 | 26th July 2006
Artur Czumaj, Artur Czumaj, Andrzej Lingas

Finding a Heaviest Triangle is not Harder than Matrix Multiplication

We show that for any $\epsilon > 0$, a maximum-weight triangle in an
undirected graph with $n$ vertices and real weights assigned to
vertices can be found in time $\O(n^{\omega} + n^{2 + \epsilon})$,
where $\omega $ is the exponent of fastest matrix multiplication
algorithm. By the currently best bound ... more >>>

TR05-050 | 18th April 2005
Uriel Feige, Eran Ofek

Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

We consider the problem of finding a maximum independent set in a
random graph. The random graph $G$ is modelled as follows. Every
edge is included independently with probability $\frac{d}{n}$, where
$d$ is some sufficiently large constant. Thereafter, for some
constant $\alpha$, a subset $I$ of $\alpha n$ vertices is ... more >>>

TR07-038 | 23rd April 2007
Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

Finding Collisions in Interactive Protocols -- A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme ... more >>>

TR12-006 | 21st January 2012
Gregory Valiant

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise

Revisions: 2

Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< ... more >>>

TR12-035 | 5th April 2012
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

Finding Cycles and Trees in Sublinear Time

Revisions: 1 , Comments: 1

(This is a revised version of work that was posted on arXiv in July 2010.)

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq3$ and tree-minors in bounded-degree graphs.
The complexity of these algorithms is related to the distance
of the graph from being ... more >>>

TR03-078 | 23rd October 2003
Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao

Finding Favorites

Comments: 2

We investigate a new type of information-theoretic identification problem, suggested to us by Alan Taylor. In this problem we are given a set of items, more than half of which share a common ``good" value. The other items have various other values which are called ``bad". The only method we ... more >>>

TR06-156 | 7th December 2006
Tomas Feder, Rajeev Motwani

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length
$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general
result in which we show that if $G$ has maximum degree $d$ and has a
cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),
then ... more >>>

TR06-027 | 22nd February 2006
Hermann Gruber, Markus Holzer

Finding Lower Bounds for Nondeterministic State Complexity is Hard

We investigate the following lower bound methods for regular
languages: The fooling set technique, the extended fooling set
technique, and the biclique edge cover technique. It is shown that
the maximal attainable lower bound for each of the above mentioned
techniques can be algorithmically deduced from ... more >>>

TR15-207 | 23rd December 2015
Ofer Grossman

Finding Primitive Roots Pseudo-Deterministically

Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous ... more >>>

TR08-102 | 9th November 2008
Adi Akavia

Finding Significant Fourier Transform Coefficients Deterministically and Locally

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear ... more >>>

TR06-004 | 6th January 2006
Jesper Torp Kristensen, Peter Bro Miltersen

Finding small OBDDs for incompletely specified truth tables is hard

We present an efficient reduction mapping undirected graphs
G with n = 2^k vertices for integers k
to tables of partially specified Boolean functions
g: {0,1}^(4k+1) -> {0,1,*} so that for any integer m,
G has a vertex colouring using m colours if and only if g ... more >>>

TR16-137 | 3rd September 2016
Mrinal Kumar, Ramprasad Saptharishi

Finer separations between shallow arithmetic circuits

In this paper, we show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d = O(\log^2 n)$, such that

1. $P_n$ can be computed by linear sized homogeneous depth-$5$ circuits.

2. $P_n$ can be computed by ... more >>>

TR96-026 | 25th March 1996
Stasys Jukna

Finite Limits and Monotone Computations

Revisions: 1 , Comments: 1

We prove a general combinatorial lower bound on the
size of monotone circuits. The argument is different from
Razborov's method of approximation, and is based on Sipser's
notion of `finite limit' and Haken's `counting bottlenecks' idea.
We then apply this criterion to the ... more >>>

TR13-004 | 11th November 2012
A. C. Cem Say, Abuzer Yakaryilmaz

Finite state verifiers with constant randomness

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

TR06-038 | 10th February 2006
David Doty, Jack H. Lutz, Satyadev Nandakumar, Satyadev Nandakumar

Finite-State Dimension and Real Arithmetic

We use entropy rates and Schur concavity to prove that, for every integer k >= 2, every nonzero rational number q, and every real number alpha, the base-k expansions of alpha, q+alpha, and q*alpha all have the same finite-state dimension and the same finite-state strong dimension. This extends, and gives ... more >>>

TR15-135 | 19th August 2015
Arnab Bhattacharyya, Palash Dey

Fishing out Winners from Vote Streams

Revisions: 1

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined ... more >>>

TR08-030 | 16th November 2007
Bruno Durand, Alexander Shen, Andrei Romashchenko

Fixed Point and Aperiodic Tilings

An aperiodic tile set was first constructed by R.Berger while
proving the undecidability of the domino problem. It turned out
that aperiodic tile sets appear in many topics ranging from
logic (the Entscheidungsproblem) to physics (quasicrystals)

We present a new construction of an aperiodic tile set. The
flexibility of this ... more >>>

TR06-157 | 14th December 2006
Lance Fortnow, Rahul Santhanam

Fixed-Polynomial Size Circuit Bounds

We explore whether various complexity classes can have linear or
more generally $n^k$-sized circuit families for some fixed $k$. We

1) The following are equivalent,
- NP is in SIZE(n^k) (has O(n^k)-size circuit families) for some k
- P^NP|| is in SIZE(n^k) for some k
- ONP/1 is in ... more >>>

TR11-034 | 20th January 2011
Pavol Duris, Marek Kosta

Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

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

TR12-036 | 12th April 2012
Venkatesan Guruswami, Chaoping Xing

Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The worst-case list size output by the algorithm is $O(1/\epsilon)$, matching the existential bound for random ... more >>>

TR10-006 | 11th January 2010
YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

Fooling functions of halfspaces under product distributions

Revisions: 2

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

TR14-022 | 19th February 2014
Shay Moran, Makrand Sinha, Amir Yehudayoff

Fooling Pairs in Randomized Communication Complexity

Revisions: 1

Fooling pairs are one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity.
We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We then conclude that the private-coin randomized ... more >>>

TR04-088 | 12th October 2004
Emanuele Viola, Dan Gutfreund

Fooling Parity Tests with Parity Gates

We study the complexity of computing $k$-wise independent and
$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.
Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.
given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.
Mansour, Nisan and Tiwari (1990) show that ... more >>>

TR06-140 | 8th November 2006
Paul Beame, Russell Impagliazzo, Nathan Segerlind

Formula Caching in DPLL

We consider extensions of the DPLL approach to satisfiability testing that add a version of memoization, in which formulas that the algorithm has previously shown to be unsatisfiable are remembered for later use. Such formula caching algorithms have been suggested for satisfiability and stochastic satisfiability. We formalize these methods by ... more >>>

TR12-061 | 16th May 2012
Pavel Hrubes, Amir Yehudayoff

Formulas are exponentially stronger than monotone circuits in non-commutative setting

We give an example of a non-commutative monotone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general ... more >>>

TR13-169 | 2nd December 2013
Benjamin Rossman

Formulas vs. Circuits for Small Distance Connectivity

We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance $k(n)$ Connectivity, which asks whether two specified nodes in a graph of size $n$ are connected by a path of length at most $k(n)$. This problem is solvable (by ... more >>>

TR17-032 | 17th February 2017
Olaf Beyersdorff, Joshua Blinkhorn

Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds

We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution.

Our technique exploits a clear semantic paradigm, showing the ... more >>>

TR14-155 | 21st November 2014
Scott Aaronson, Andris Ambainis

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum ... more >>>

TR13-163 | 28th November 2013
Russell Impagliazzo, Valentine Kabanets

Fourier Concentration from Shrinkage

Revisions: 2

For Boolean functions computed by de Morgan formulas of subquadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on ``small-degree'' coefficients. For a Boolean function $f:\{0,1\}^n\to\{1,-1\}$ computable by a de Morgan formula of size $s$, we show that
\sum_{A\subseteq [n]\; :\; |A|>s^{1/\Gamma ... more >>>

TR17-075 | 29th April 2017
Clement Canonne, Ilias Diakonikolas, Alistair Stewart

Fourier-Based Testing for Families of Distributions

Revisions: 1

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

TR03-061 | 29th August 2003
Jan Kára, Daniel Král

Free Binary Decision Diagrams for Computation of EAR_n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with a constraint (additional to binary decision diagrams) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined
for n x n Boolean matrices: EAR_n(M)=1 iff the matrix ... more >>>

TR95-024 | 23rd May 1995
Mihir Bellare, Oded Goldreich, Madhu Sudan

Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

This paper continues the investigation of the connection between proof
systems and approximation. The emphasis is on proving ``tight''
non-approximability results via consideration of measures like the
``free bit complexity'' and the ``amortized free bit complexity'' of
proof systems.

The first part of the paper presents a collection of new ... more >>>

TR95-036 | 5th July 1995
Richard Beigel, William Gasarch, Efim Kinber

Frequency Computation and Bounded Queries

For a set A and a number n let F_n^A(x_1,...,x_n) =
A(x_1)\cdots A(x_n). We study how hard it is to approximate this
function in terms of the number of queries required. For a general
set A we have exact bounds that depend on functions from coding
theory. These are applied ... more >>>

TR09-031 | 6th April 2009
Zvika Brakerski, Oded Goldreich

From absolute distinguishability to positive distinguishability

We study methods of converting algorithms that distinguish pairs
of distributions with a gap that has an absolute value that is noticeable
into corresponding algorithms in which the gap is always positive.
Our focus is on designing algorithms that, in addition to the tested string,
obtain a ... more >>>

TR10-144 | 20th September 2010
Eli Ben-Sasson, Noga Ron-Zewi

From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

Two-source and affine extractors and dispersers are fundamental objects studied in the context of derandomization. This paper shows how to construct two-source extractors and dispersers for arbitrarily small min-entropy rate in a black-box manner from affine extractors with sufficiently good parameters. Our analysis relies on the study of approximate duality, ... more >>>

TR12-171 | 3rd December 2012
Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

From Information to Exact Communication

We develop a new local characterization of the zero-error information complexity function for two party communication problems, and use it to compute the exact internal and external information complexity of the 2-bit AND function: $IC(AND,0) = C_{\wedge}\approx 1.4923$ bits, and $IC^{ext}(AND,0) = \log_2 3 \approx 1.5839$ bits. This leads to ... more >>>

TR11-154 | 17th November 2011
Klim Efremenko

From Irreducible Representations to Locally Decodable Codes

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

In this paper we ... more >>>

TR17-172 | 3rd November 2017
Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

From Laconic Zero-Knowledge to Public-Key Cryptography

Since its inception, public-key encryption (PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is ... more >>>

TR04-093 | 9th November 2004
Oded Goldreich, Madhu Sudan, Luca Trevisan

From logarithmic advice to single-bit advice

Building on Barak's work (Random'02),
Fortnow and Santhanam (FOCS'04) proved a time hierarchy
for probabilistic machines with one bit of advice.
Their argument is based on an implicit translation technique,
which allow to translate separation results for short (say logarithmic)
advice (as shown by Barak) into separations for ... more >>>

TR15-206 | 15th December 2015
Benny Applebaum, Pavel Raykov

From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

Goos, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the ... more >>>

TR12-125 | 2nd October 2012
Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

From RAM to SAT

Revisions: 1

Common presentations of the NP-completeness of SAT suffer
from two drawbacks which hinder the scope of this
flagship result. First, they do not apply to machines
equipped with random-access memory, also known as
direct-access memory, even though this feature is
critical in basic algorithms. Second, they incur a
quadratic blow-up ... more >>>

TR09-077 | 16th September 2009
Zeev Dvir

From Randomness Extraction to Rotating Needles

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

TR14-081 | 13th June 2014
Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

From Small Space to Small Width in Resolution

In 2003, Atserias and Dalmau resolved a major open question about the resolution proof system by establishing that the space complexity of CNF formulas is always an upper bound on the width needed to refute them. Their proof is beautiful but somewhat mysterious in that it relies heavily on tools ... more >>>

TR10-013 | 31st January 2010
Nitin Saxena, C. Seshadhri

From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-box Identity Test for Depth-3 Circuits

Revisions: 1

We study the problem of identity testing for depth-3 circuits, over the
field of reals, of top fanin k and degree d (called sps(k,d)
identities). We give a new structure theorem for such identities and improve
the known deterministic d^{k^k}-time black-box identity test (Kayal &
Saraf, FOCS 2009) to one ... more >>>

TR16-117 | 31st July 2016
Mrinalkanti Ghosh, Madhur Tulsiani

From Weak to Strong LP Gaps for all CSPs

Revisions: 1

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $\Omega\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ... more >>>

TR11-111 | 10th August 2011
Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan

Fully Homomorphic Encryption without Bootstrapping

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

... more >>>

TR16-045 | 22nd March 2016
Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P \in F[x_1, x_2, \ldots, x_n]$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to {syntactically} computing $P$, when $C \equiv P$ as formal polynomials. In this ... more >>>

TR03-018 | 28th March 2003
Matthias Galota, Heribert Vollmer

Functions Computable in Polynomial Space

We show that the class of integer-valued functions computable by
polynomial-space Turing machines is exactly the class of functions f
for which there is a nondeterministic polynomial-time Turing
machine with a certain order on its paths that on input x outputs a 3x3
matrix with entries from {-1,0,1} on each ... more >>>

TR16-004 | 26th December 2015
Dax Enshan Koh

Further extensions of Clifford circuits and their classical simulation complexities

Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations that might just be slightly different, lead to ... more >>>

ISSN 1433-8092 | Imprint