Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > F:
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

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

TR20-077 | 19th May 2020
Amit Sinhababu, Thomas Thierauf

#### Factorization of Polynomials Given by Arithmetic Branching Programs

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size $s$, we show that all its factors can be computed by arithmetic branching programs of size $\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was ... more >>>

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

#### Factors of Sparse Polynomials are Sparse

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

TR20-037 | 18th March 2020
Michal Garlik

#### Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It

We show that for every integer $k \geq 2$, the Res($k$) propositional proof system does not have the weak feasible disjunction property. Next, we generalize a recent result of Atserias and Müller [FOCS, 2019] to Res($k$). We show that if NP is not included in P (resp. QP, SUBEXP) then ... 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

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

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

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

TR22-063 | 30th April 2022
Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

#### Fast Multivariate Multipoint Evaluation Over All Finite Fields

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field $\mathbb{F}$ that outputs the evaluations of an $m$-variate polynomial of ... 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: 2

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

TR21-162 | 14th November 2021
Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra

#### Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications

Revisions: 3

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem is also closely related to fast algorithms for other natural ... 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 k)})$.

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

Revisions: 1

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

TR21-032 | 5th March 2021
Justin Holmgren, Alex Lombardi, Ron Rothblum

#### Fiat-Shamir via List-Recoverable Codes (or: Parallel Repetition of GMW is not Zero-Knowledge)

Shortly after the introduction of zero-knowledge proofs, Goldreich, Micali and Wigderson (CRYPTO '86) demonstrated their wide applicability by constructing zero-knowledge proofs for the NP-complete problem of graph 3-coloring. A long-standing open question has been whether parallel repetition of their protocol preserves zero knowledge. In this work, we answer this question ... 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, 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 >>>

TR19-074 | 22nd May 2019
Arka Rai Choudhuri, Pavel Hubá?ek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy Rothblum

#### Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir

The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.

We show that ... 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

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 >>> TR18-148 | 25th August 2018 Akash Kumar, C. Seshadhri, Andrew Stolman #### Finding forbidden minors in sublinear time: a$n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs Let$G$be an undirected, bounded degree graph with$n$vertices. Fix a finite graph$H$, and suppose one must remove$\varepsilon n$edges from$G$to make it$H$-minor free (for some small constant$\varepsilon > 0$). We give an$n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... more >>> TR18-101 | 20th May 2018 Akash Kumar, C. Seshadhri, Andrew Stolman #### Finding forbidden minors in sublinear time: a$O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs Let$G$be an undirected, bounded degree graph with$n$vertices. Fix a finite graph$H$, and suppose one must remove$\varepsilon n$edges from$G$to make it$H$-minor free (for some small constant$\varepsilon > 0$). We give an$n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ... 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 >>> TR19-134 | 4th October 2019 Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten #### Finding monotone patterns in sublinear time We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed$k \in \mathbb{N}$and$\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$monotone subsequence of$f \colon [n] \to \mathbb{R}$, assuming that$f$is$\varepsilon$-far ... 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 >>> TR18-092 | 4th May 2018 Marco Carmosino, Russell Impagliazzo, Manuel Sabin #### Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires$n^{\epsilon k}$time, for some constant$\epsilon > 1/2$, to count (note that these conjectures are significantly ... 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 #### 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 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 >>> TR18-104 | 29th May 2018 Oded Goldreich #### Flexible models for testing graph properties Revisions: 1 The standard models of testing graph properties postulate that the vertex-set consists of$\{1,2,...,n\}$, where$n$is a natural number that is given explicitly to the tester. Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ... 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 >>> TR21-002 | 8th January 2021 Pooya Hatami, William Hoza, Avishay Tal, Roei Tell #### Fooling Constant-Depth Threshold Circuits Revisions: 1 We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth$d\in\mathbb{N}$... 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 >>> TR22-132 | 18th September 2022 Harm Derksen, Emanuele Viola #### Fooling polynomials using invariant theory We revisit the problem of constructing explicit pseudorandom generators that fool with error$\epsilon$degree-$d$polynomials in$n$variables over the field$F_q$, in the case of large$q$. Previous constructions either have seed length at least$2^{d}\log q$, and thus are only non-trivial when the degree is less than ... more >>> TR18-145 | 13th August 2018 Ryan O'Donnell, Rocco Servedio, Li-Yang Tan #### Fooling Polytopes We give a pseudorandom generator that fools$m$-facet polytopes over$\{0,1\}^n$with seed length$\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on$m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any$\{0,1\}$-integer program. 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 >>> TR19-129 | 27th September 2019 Zeev Dvir, Allen Liu #### Fourier and Circulant Matrices are Not Rigid The concept of matrix rigidity was first introduced by Valiant in [Val77]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed that rigidity can be used to prove ... more >>> TR19-017 | 6th February 2019 Chin Ho Lee #### Fourier bounds and pseudorandom generators for product tests We study the Fourier spectrum of functions$f\colon \{0,1\}^{mk} \to \{-1,0,1\}$which can be written as a product of$k$Boolean functions$f_i$on disjoint$m$-bit inputs. We prove that for every positive integer$d$, $\sum_{S \subseteq [mk]: |S|=d} |\hat{f_S}| = O(m)^d .$ Our upper bound ... 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 >>> TR20-175 | 24th November 2020 Emanuele Viola #### Fourier conjectures, correlation bounds, and Majority Revisions: 2 Recently several conjectures were made regarding the Fourier spectrum of low-degree polynomials. We show that these conjectures imply new correlation bounds for functions related to Majority. Then we prove several new results on correlation bounds which aim to, but don't, resolve the conjectures. In particular, we prove several new results ... more >>> TR21-046 | 22nd March 2021 Uma Girish, Avishay Tal, Kewen Wu #### Fourier Growth of Parity Decision Trees We prove that for every parity decision tree of depth$d$on$n$variables, the sum of absolute values of Fourier coefficients at level$\ell$is at most$d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$. Our result is nearly tight for small values of$\ell$and extends a previous Fourier bound ... more >>> TR22-034 | 3rd March 2022 Chin Ho Lee, Edward Pyne, Salil Vadhan #### Fourier Growth of Regular Branching Programs We analyze the Fourier growth, i.e. the$L_1$Fourier weight at level$k$(denoted$L_{1,k}$), of read-once regular branching programs. We prove that every read-once regular branching program$B$of width$w \in [1,\infty]$with$s$accepting states on$n$-bit inputs must have its$L_{1,k}$bounded by$$\min\left\{ ... more >>> TR21-110 | 22nd July 2021 Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco Servedio, Emanuele Viola #### Fourier growth of structured$\mathbb{F}_2$-polynomials and applications We analyze the Fourier growth, i.e. the$L_1$Fourier weight at level$k$(denoted$L_{1,k}$), of various well-studied classes of "structured"$\mathbb{F}_2$-polynomials. This study is motivated by applications in pseudorandomness, in particular recent results and conjectures due to [CHHL19,CHLT19,CGLSS20] which show that upper bounds on Fourier growth (even at ... 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 >>> TR22-107 | 20th July 2022 Shachar Lovett, Jiapeng Zhang #### Fractional certificates for bounded functions A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold ... more >>> TR20-121 | 3rd August 2020 Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty #### Fractional Pseudorandom Generators from the$k$th Fourier Level Revisions: 2 In recent work by Chattopadhyay et al.[CHHL19,CHLT19], the authors exhibit a simple and flexible construction of pseudorandom generators for classes of Boolean functions that satisfy$L_1$Fourier bounds. [CHHL19] show that if a class satisfies such tail bounds at all levels, this implies a PRG whose seed length depends on ... 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 >>> TR19-028 | 1st March 2019 Shachar Lovett, Noam Solomon, Jiapeng Zhang #### From DNF compression to sunflower theorems via regularity Revisions: 1 The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds ... 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 corrupted. 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 >>> TR18-198 | 22nd November 2018 Irit Dinur, Tali Kaufman, Noga Ron-Zewi #### From Local to Robust Testing via Agreement Testing Revisions: 2 A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is {\em robust} if for non-codewords it satisfies the stronger property that ... 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 >>> TR21-105 | 22nd July 2021 Suryajith Chillara #### Functional lower bounds for restricted arithmetic circuits of depth four Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit$d^{O(1)}$-variate and degree$d$polynomial$P_{d} \in VNP$such that if any depth four circuit$C$of bounded formal degree$d$which computes a polynomial of bounded individual degree$O(1)$, that is functionally equivalent to$P_d$, then ... 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 >>> TR18-125 | 7th July 2018 Zvika Brakerski #### Fundamentals of Fully Homomorphic Encryption – A Survey A homomorphic encryption scheme is one that allows computing on encrypted data without decrypting it first. In fully homomorphic encryption it is possible to apply any efficiently computable function to encrypted data. We provide a survey on the origins, definitions, properties, constructions and uses of fully homomorphic encryption. more >>> TR22-018 | 15th February 2022 Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao #### Further Collapses in TFNP We show$\text{EOPL}=\text{PLS}\cap\text{PPAD}$. Here the class$\text{EOPL}\$ consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020). In particular, our result yields a new simpler proof of the breakthrough collapse ... 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