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

**F**

__
TR08-074
| 19th July 2008
__

Neeraj Kayal, Timur Nezhmetdinov#### Factoring groups efficiently

__
TR14-056
| 18th April 2014
__

Zeev Dvir, Rafael Mendes de Oliveira#### Factors of Sparse Polynomials are Sparse

Revisions: 1
,
Comments: 1

__
TR13-014
| 11th January 2013
__

Zvika Brakerski, Moni Naor#### Fast Algorithms for Interactive Coding

__
TR14-117
| 18th August 2014
__

Shiva Manne, Manjish Pal#### Fast Approximate Matrix Multiplication by Solving Linear Systems

Comments: 1

__
TR07-070
| 11th June 2007
__

Nir Ailon, Edo Liberty#### Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

__
TR08-023
| 10th January 2008
__

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi#### Fast Integer Multiplication using Modular Arithmetic

__
TR16-019
| 5th February 2016
__

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

__
TR14-154
| 20th November 2014
__

Andris Ambainis, Yuval Filmus, Francois Le Gall#### Fast Matrix Multiplication: Limitations of the Laser Method

__
TR16-082
| 22nd May 2016
__

Benny Applebaum, Pavel Raykov#### Fast Pseudorandom Functions Based on Expander Graphs

__
TR17-134
| 8th September 2017
__

Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev#### Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Revisions: 2

__
TR06-111
| 18th July 2006
__

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas#### Faster algorithms for finding lowest common ancestors in directed acyclic graphs

Revisions: 2

__
TR09-065
| 31st July 2009
__

Panagiotis Voulgaris, Daniele Micciancio#### Faster exponential time algorithms for the shortest vector problem

__
TR14-111
| 15th August 2014
__

Vikraman Arvind, Gaurav Rattan#### Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity

__
TR10-152
| 6th October 2010
__

Alexey Pospelov#### Faster Polynomial Multiplication via Discrete Fourier Transforms

__
TR12-111
| 5th September 2012
__

Venkatesan Guruswami, Ali Kemal Sinop#### Faster SDP hierarchy solvers for local rounding algorithms

__
TR94-011
| 12th December 1994
__

R. Beigel, W. Hurwood, N. Kahale#### Fault Diagnosis in a Flash

__
TR15-059
| 10th April 2015
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Feasible Interpolation for QBF Resolution Calculi

__
TR95-004
| 1st January 1995
__

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

__
TR17-144
| 27th September 2017
__

Moritz Müller, Ján Pich#### Feasibly constructive proofs of succinct weak circuit lower bounds

__
TR03-016
| 15th January 2003
__

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis#### FIFO is Unstable at Arbitrarily Low Rates

Revisions: 1

__
TR06-115
| 26th July 2006
__

Artur Czumaj, Andrzej Lingas#### Finding a Heaviest Triangle is not Harder than Matrix Multiplication

__
TR05-050
| 18th April 2005
__

Uriel Feige, Eran Ofek#### Finding a Maximum Independent Set in a Sparse Random Graph

Revisions: 1

__
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

__
TR12-006
| 21st January 2012
__

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

Revisions: 2

__
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

__
TR03-078
| 23rd October 2003
__

Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao#### Finding Favorites

Comments: 2

__
TR06-156
| 7th December 2006
__

Tomas Feder, Rajeev Motwani#### Finding large cycles in Hamiltonian graphs

__
TR06-027
| 22nd February 2006
__

Hermann Gruber, Markus Holzer#### Finding Lower Bounds for Nondeterministic State Complexity is Hard

__
TR15-207
| 23rd December 2015
__

Ofer Grossman#### Finding Primitive Roots Pseudo-Deterministically

__
TR08-102
| 9th November 2008
__

Adi Akavia#### Finding Significant Fourier Transform Coefficients Deterministically and Locally

__
TR06-004
| 6th January 2006
__

Jesper Torp Kristensen, Peter Bro Miltersen#### Finding small OBDDs for incompletely specified truth tables is hard

__
TR16-137
| 3rd September 2016
__

Mrinal Kumar, Ramprasad Saptharishi#### Finer separations between shallow arithmetic circuits

__
TR96-026
| 25th March 1996
__

Stasys Jukna#### Finite Limits and Monotone Computations

Revisions: 1
,
Comments: 1

__
TR13-004
| 11th November 2012
__

A. C. Cem Say, Abuzer Yakaryilmaz#### Finite state verifiers with constant randomness

__
TR06-038
| 10th February 2006
__

David Doty, Jack H. Lutz, Satyadev Nandakumar#### Finite-State Dimension and Real Arithmetic

__
TR15-135
| 19th August 2015
__

Arnab Bhattacharyya, Palash Dey#### Fishing out Winners from Vote Streams

Revisions: 1

__
TR08-030
| 16th November 2007
__

Bruno Durand, Alexander Shen, Andrei Romashchenko#### Fixed Point and Aperiodic Tilings

__
TR06-157
| 14th December 2006
__

Lance Fortnow, Rahul Santhanam#### Fixed-Polynomial Size Circuit Bounds

__
TR11-034
| 20th January 2011
__

Pavol Duris, Marek Kosta#### Flip-Pushdown Automata with k Pushdown Reversals and E0L Systems are Incomparable

__
TR12-036
| 12th April 2012
__

Venkatesan Guruswami, Chaoping Xing#### Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding

__
TR10-006
| 11th January 2010
__

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan#### Fooling functions of halfspaces under product distributions

Revisions: 2

__
TR14-022
| 19th February 2014
__

Shay Moran, Makrand Sinha, Amir Yehudayoff#### Fooling Pairs in Randomized Communication Complexity

Revisions: 1

__
TR04-088
| 12th October 2004
__

Emanuele Viola, Dan Gutfreund#### Fooling Parity Tests with Parity Gates

__
TR06-140
| 8th November 2006
__

Paul Beame, Russell Impagliazzo, Nathan Segerlind#### Formula Caching in DPLL

__
TR12-061
| 16th May 2012
__

Pavel Hrubes, Amir Yehudayoff#### Formulas are exponentially stronger than monotone circuits in non-commutative setting

__
TR13-169
| 2nd December 2013
__

Benjamin Rossman#### Formulas vs. Circuits for Small Distance Connectivity

__
TR17-032
| 17th February 2017
__

Olaf Beyersdorff, Joshua Blinkhorn#### Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds

__
TR14-155
| 21st November 2014
__

Scott Aaronson, Andris Ambainis#### Forrelation: A Problem that Optimally Separates Quantum from Classical Computing

__
TR13-163
| 28th November 2013
__

Russell Impagliazzo, Valentine Kabanets#### Fourier Concentration from Shrinkage

Revisions: 2

__
TR17-075
| 29th April 2017
__

Clement Canonne, Ilias Diakonikolas, Alistair Stewart#### Fourier-Based Testing for Families of Distributions

Revisions: 1

__
TR03-061
| 29th August 2003
__

Jan Kára, Daniel Král#### Free Binary Decision Diagrams for Computation of EAR_n

__
TR95-024
| 23rd May 1995
__

Mihir Bellare, Oded Goldreich, Madhu Sudan#### Free bits, PCP and Non-Approximability - Towards tight results

Revisions: 4

__
TR95-036
| 5th July 1995
__

Richard Beigel, William Gasarch, Efim Kinber#### Frequency Computation and Bounded Queries

__
TR09-031
| 6th April 2009
__

Zvika Brakerski, Oded Goldreich#### From absolute distinguishability to positive distinguishability

__
TR10-144
| 20th September 2010
__

Eli Ben-Sasson, Noga Ron-Zewi#### From Affine to Two-Source Extractors via Approximate Duality

Revisions: 1

__
TR12-171
| 3rd December 2012
__

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein#### From Information to Exact Communication

__
TR11-154
| 17th November 2011
__

Klim Efremenko#### From Irreducible Representations to Locally Decodable Codes

__
TR17-172
| 3rd November 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### From Laconic Zero-Knowledge to Public-Key Cryptography

__
TR04-093
| 9th November 2004
__

Oded Goldreich, Madhu Sudan, Luca Trevisan#### From logarithmic advice to single-bit advice

__
TR15-206
| 15th December 2015
__

Benny Applebaum, Pavel Raykov#### From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

__
TR12-125
| 2nd October 2012
__

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola#### From RAM to SAT

Revisions: 1

__
TR09-077
| 16th September 2009
__

Zeev Dvir#### From Randomness Extraction to Rotating Needles

__
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

__
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

__
TR16-117
| 31st July 2016
__

Mrinalkanti Ghosh, Madhur Tulsiani#### From Weak to Strong LP Gaps for all CSPs

Revisions: 1

__
TR11-111
| 10th August 2011
__

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan#### Fully Homomorphic Encryption without Bootstrapping

__
TR16-045
| 22nd March 2016
__

Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi#### Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity

__
TR03-018
| 28th March 2003
__

Matthias Galota, Heribert Vollmer#### Functions Computable in Polynomial Space

__
TR16-004
| 26th December 2015
__

Dax Enshan Koh#### Further extensions of Clifford circuits and their classical simulation complexities

Neeraj Kayal, Timur Nezhmetdinov

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

Zeev Dvir, Rafael Mendes de Oliveira

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

Zvika Brakerski, Moni Naor

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

Shiva Manne, Manjish Pal

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

Nir Ailon, Edo Liberty

\begin{abstract}

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

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

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

Ran Raz

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

Andris Ambainis, Yuval Filmus, Francois Le Gall

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

Benny Applebaum, Pavel Raykov

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

Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

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

Artur Czumaj, Miroslaw Kowaluk, Andrzej Lingas

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

Panagiotis Voulgaris, Daniele Micciancio

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

Vikraman Arvind, Gaurav Rattan

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

k)})$.

Alexey Pospelov

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

Venkatesan Guruswami, Ali Kemal Sinop

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

R. Beigel, W. Hurwood, N. Kahale

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

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

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

Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

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

Moritz Müller, Ján Pich

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

Dimitrios Koukopoulos, Marios Mavronicolas, Paul Spirakis

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

Artur Czumaj, Andrzej Lingas

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

Uriel Feige, Eran Ofek

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

Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev

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

Gregory Valiant

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

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

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

Fan Chung, Ron Graham, Jia Mao, Andrew Chi-Chih Yao

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

Tomas Feder, Rajeev Motwani

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

Hermann Gruber, Markus Holzer

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

Ofer Grossman

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

Adi Akavia

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

Jesper Torp Kristensen, Peter Bro Miltersen

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

Mrinal Kumar, Ramprasad Saptharishi

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

Stasys Jukna

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

A. C. Cem Say, Abuzer Yakaryilmaz

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

David Doty, Jack H. Lutz, Satyadev Nandakumar

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

Arnab Bhattacharyya, Palash Dey

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

Bruno Durand, Alexander Shen, Andrei Romashchenko

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

Lance Fortnow, Rahul Santhanam

We explore whether various complexity classes can have linear or

more generally $n^k$-sized circuit families for some fixed $k$. We

show

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

Pavol Duris, Marek Kosta

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

Venkatesan Guruswami, Chaoping Xing

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

YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

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

Shay Moran, Makrand Sinha, Amir Yehudayoff

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

Emanuele Viola, Dan Gutfreund

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

Paul Beame, Russell Impagliazzo, Nathan Segerlind

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

Pavel Hrubes, Amir Yehudayoff

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

Benjamin Rossman

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

Olaf Beyersdorff, Joshua Blinkhorn

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

Scott Aaronson, Andris Ambainis

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

Russell Impagliazzo, Valentine Kabanets

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

Clement Canonne, Ilias Diakonikolas, Alistair Stewart

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

Jan Kára, Daniel Král

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

Mihir Bellare, Oded Goldreich, Madhu Sudan

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

Richard Beigel, William Gasarch, Efim Kinber

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

Zvika Brakerski, Oded Goldreich

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

Eli Ben-Sasson, Noga Ron-Zewi

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

Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein

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

Klim Efremenko

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

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

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

Oded Goldreich, Madhu Sudan, Luca Trevisan

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

Benny Applebaum, Pavel Raykov

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

Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola

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

Zeev Dvir

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

Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, Marc Vinyals

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

Nitin Saxena, C. Seshadhri

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

Mrinalkanti Ghosh, Madhur Tulsiani

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

Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan

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 >>>Michael Forbes, Mrinal Kumar, Ramprasad Saptharishi

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

Matthias Galota, Heribert Vollmer

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

Dax Enshan Koh

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