Under the auspices of the Computational Complexity Foundation (CCF)

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

R
TR19-132 | 26th September 2019
Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Revisions: 1

We consider the celebrated radio network model for abstracting communication in wireless networks. In this model, in any round, each node in the network may broadcast a message to all its neighbors. However, a node is able to hear a message broadcast by a neighbor only if no collision occurred, ... more >>>

TR19-094 | 16th July 2019
Venkatesan Guruswami, Sai Sandeep

Rainbow coloring hardness via low sensitivity polymorphisms

A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its vertices such that every hyperedge intersects all $r$ color classes. Given as input such a hypergraph, finding a $r$-rainbow coloring of it is NP-hard for all $k \ge 3$ and $r \ge 2$. ... more >>>

TR06-043 | 22nd March 2006
Eran Ofek, Uriel Feige

Random 3CNF formulas elude the Lovasz theta function

Let $\phi$ be a 3CNF formula with n variables and m clauses. A
simple nonconstructive argument shows that when m is
sufficiently large compared to n, most 3CNF formulas are not
satisfiable. It is an open question whether there is an efficient
refutation algorithm that for most such formulas proves ... more >>>

TR12-033 | 5th April 2012
Ankit Gupta, Neeraj Kayal, Youming Qiao

Random Arithmetic Formulas can be Reconstructed Efficiently

Informally stated, we present here a randomized algorithm that given blackbox access to the polynomial $f$ computed by an unknown/hidden arithmetic formula $\phi$ reconstructs, on the average, an equivalent or smaller formula $\hat{\phi}$ in time polynomial in the size of its output $\hat{\phi}$.

Specifically, we consider arithmetic formulas wherein the ... more >>>

TR17-045 | 7th March 2017
Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Random CNFs are Hard for Cutting Planes

Revisions: 2

The random k-SAT model is the most important and well-studied distribution over
k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for
satisfiablity algorithms, and lastly average-case hardness over this distribution has also
been linked to hardness of approximation via Feige’s hypothesis. In this ... more >>>

TR09-137 | 14th December 2009
Massimo Lauria

Random CNFs require spacious Polynomial Calculus refutations

We study the space required by Polynomial Calculus refutations of random $k$-CNFs. We are interested in how many monomials one needs to keep in memory to carry on a refutation. More precisely we show that for $k \geq 4$ a refutation of a random $k$-CNF of $\Delta n$ clauses and ... more >>>

TR17-042 | 6th March 2017
Pavel Hrubes, Pavel Pudlak

Random formulas, monotone circuits, and interpolation

We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>>

TR09-033 | 16th April 2009
Phokion G. Kolaitis, Swastik Kopparty

Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

TR08-080 | 3rd July 2008
Ido Ben-Eliezer, Rani Hod, Shachar Lovett

Random low degree polynomials are hard to approximate

Revisions: 1

We study the problem of how well a typical multivariate polynomial can be approximated by lower degree polynomials over $\F$.
We prove that, with very high probability, a random degree $d$ polynomial has only an exponentially small correlation with all polynomials of degree $d-1$, for all degrees $d$ up to ... more >>>

TR02-006 | 8th November 2001
Philippe Moser

Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

We construct a nondeterministic analogue to \textbf{APP}, denoted
\textbf{NAPP}; which is the set of all real valued functions
$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,
by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$).
We show that the subset of all Boolean ... more >>>

TR16-175 | 8th November 2016
Pavel Pudlak, Neil Thapen

Random resolution refutations

Revisions: 2

We study the \emph{random resolution} refutation system defined in~[Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the ... more >>>

TR19-165 | 18th November 2019
Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... more >>>

TR01-100 | 14th December 2001
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Random Sampling and Approximation of MAX-CSP Problems

We present a new efficient sampling method for approximating
r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on
n variables up to an additive error \epsilon n^r.We prove a new
general paradigm in that it suffices, for a given set of constraints,
to pick a small uniformly random ... more >>>

TR06-026 | 27th February 2006

Random Selection with an Adversarial Majority

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>

TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

Random Walks, Conditional Hitting Sets and Partial Derandomization

In this work we use random walks on expanders in order to
relax the properties of hitting sets required for partially
derandomizing one-side error algorithms. Building on a well-known
probability amplification technique [AKS87,CW89,IZ89], we use
random walks on expander graphs of subexponential (in the
random bit complexity) size so as ... more >>>

TR05-065 | 26th June 2005
Alexander Barvinok, Alex Samorodnitsky

Random Weighting, Asymptotic Counting, and Inverse Isoperimetry

For a family X of k-subsets of the set 1...n, let |X| be the cardinality of X and let Gamma(X, mu) be the expected maximum weight of a subset from X when the weights of 1...n are chosen independently at random from a symmetric probability distribution mu on R. We ... more >>>

TR10-056 | 1st April 2010
Kord Eickmeyer, Martin Grohe

Randomisation and Derandomisation in Descriptive Complexity Theory

Revisions: 1

We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic $\mathcal{L}$ we introduce a new logic $\mathsf{BP}\mathcal{L}$, bounded error probabilistic $\mathcal{L}$, which is defined from $\mathcal{L}$ in a similar way as the
complexity class $\mathsf{BPP}$, bounded error probabilistic polynomial time, is defined ... more >>>

TR97-021 | 16th May 1997
Farid Ablayev

Randomization and nondeterminsm are incomparable for ordered read-once branching programs

In the manuscript F. Ablayev and M. Karpinski, On the power of
randomized branching programs (generalization of ICALP'96 paper
results for the case of pure boolean function, available at
http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions
$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

TR96-058 | 25th November 1996
Dima Grigoriev, Marek Karpinski

Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the
general model of \emph{randomized computation trees} solving
the \emph{Knapsack Problem}, and more generally \emph{Restricted
Integer Programming}. This is the \emph{first nontrivial} lower
bound proven for this model of computation. The method of the ... more >>>

TR20-024 | 20th February 2020
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari

Randomized and Symmetric Catalytic Computation

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

TR00-007 | 14th December 1999
Pavlos S. Efraimidis, Paul Spirakis

Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines

The problem of Scheduling $n$ Independent Jobs
on $m$ Unrelated Parallel Machines, when $m$
is fixed, is considered. The standard problem
of minimizing the makespan of the schedule
(SUM) and the bicriteria problem of scheduling
with bounded makespan and cost (SUMC), are
addressed, and randomized fully linear time
more >>>

TR13-178 | 14th December 2013
Nikolay Vereshchagin

Randomized communication complexity of appropximating Kolmogorov complexity

Revisions: 2

The paper [Harry Buhrman, Michal Koucky, Nikolay Vereshchagin. Randomized Individual Communication Complexity. IEEE Conference on Computational Complexity 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate
more >>>

TR15-169 | 23rd October 2015
Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

Randomized Communication vs. Partition Number

Revisions: 1

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>

TR99-020 | 9th June 1999
Marek Karpinski

Randomized Complexity of Linear Arrangements and Polyhedra

We survey some of the recent results on the complexity of recognizing
n-dimensional linear arrangements and convex polyhedra by randomized
algebraic decision trees. We give also a number of concrete applications
of these results. In particular, we derive first nontrivial, in fact

TR16-089 | 2nd June 2016
Vikraman Arvind, Partha Mukhopadhyay, Raja S

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

Revisions: 2

In this paper we show that polynomial identity testing for
noncommutative circuits of size $s$, computing a polynomial in
$\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$, can be done by a randomized algorithm
with running time polynomial in $s$ and $n$. This answers a question
that has been open for over ten years.

The ... more >>>

TR20-091 | 14th June 2020
Janaky Murthy, vineet nair, Chandan Saha

Equivalence testing for a polynomial family $\{g_m\}_{m \in \mathbb{N}}$ over a field F is the following problem: Given black-box access to an $n$-variate polynomial $f(\mathbb{x})$, where $n$ is the number of variables in $g_m$ for some $m \in \mathbb{N}$, check if there exists an $A \in \text{GL}(n,\text{F})$ such that $f(\mathbb{x}) ... more >>> TR16-087 | 30th May 2016 Shalev Ben-David, Robin Kothari Randomized query complexity of sabotaged and composed functions We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>> TR04-059 | 21st June 2004 Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler Randomized Quicksort and the Entropy of the Random Number Generator The worst-case complexity of an implementation of Quicksort depends on the random number generator that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a function in the entropy of the random source. We give upper and lower bounds ... more >>> TR04-009 | 22nd January 2004 Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda Randomly coloring constant degree graphs We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>> TR19-064 | 23rd April 2019 Igor Carboni Oliveira Randomness and Intractability in Kolmogorov Complexity We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability. This complexity measure gives rise to a ... more >>> TR98-018 | 27th March 1998 Martin Sauerhoff Randomness and Nondeterminism are Incomparable for Read-Once Branching Programs Comments: 1 We extend the tools for proving lower bounds for randomized branching programs by presenting a new technique for the read-once case which is applicable to a large class of functions. This technique fills the gap between simple methods only applicable for OBDDs and the well-known "rectangle technique" of Borodin, Razborov ... more >>> TR10-175 | 14th November 2010 Emanuele Viola Randomness buys depth for approximate counting Revisions: 1 We show that the promise problem of distinguishing$n$-bit strings of hamming weight$\ge 1/2 + \Omega(1/\log^{d-1} n)$from strings of weight$\le 1/2 - \Omega(1/\log^{d-1} n)$can be solved by explicit, randomized (unbounded-fan-in) poly(n)-size depth-$d$circuits with error$\le 1/3$, but cannot be solved by deterministic poly(n)-size depth-$(d+1)$circuits, ... more >>> TR19-183 | 21st December 2019 Marshall Ball, Oded Goldreich, Tal Malkin Randomness Extraction from Somewhat Dependent Sources Revisions: 1 We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness. Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions. Going from the more restricted model ... more >>> TR16-018 | 3rd February 2016 Kuan Cheng, Xin Li Randomness Extraction in$AC^0$and with Small Locality Revisions: 7 We study two variants of seeded randomness extractors. The first one, as studied by Goldreich et al. \cite{goldreich2015randomness}, is seeded extractors that can be computed by$AC^0$circuits. The second one, as introduced by Bogdanov and Guo \cite{bogdanov2013sparse}, is (strong) extractor families that consist of sparse transformations, i.e., functions that ... more >>> TR13-120 | 4th September 2013 Zeyu Guo Randomness-efficient Curve Samplers Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the ... more >>> TR06-058 | 25th April 2006 Alexander Healy Randomness-Efficient Sampling within NC^1 Revisions: 1 We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results: ... more >>> TR12-003 | 13th December 2011 Pratik Worah Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver Lov\'{a}sz and Schrijver introduced several lift and project methods for$0$-$1$integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the$LS$and$LS_+$hierarchies. In this paper we investigate rank bounds in the ... more >>> TR10-149 | 22nd September 2010 Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Revisions: 1 A$(q,k,t)$-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most$q$non-zeros, each column has at least$k$non-zeros and the supports of every two columns intersect in at most t rows. We prove that the rank ... more >>> TR95-018 | 27th March 1995 Jay Belanger, Jie Wang Rankable Distributions Do Not Provide Harder Instances Than Uniform Distributions We show that polynomially rankable distributions do not provide harder instances than uniform distributions for NP problems. In particular, we show that if Levin's randomized tiling problem is solvable in polynomial time on average, then every NP problem under any p-rankable ... more >>> TR20-084 | 31st May 2020 Gil Cohen, Tal Yankovitz Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes In a seminal work, Kopparty et al. (J. ACM 2017) constructed asymptotically good$n$-bit locally decodable codes (LDC) with$2^{\widetilde{O}(\sqrt{\log{n}})}$queries. A key ingredient in their construction is a distance amplification procedure by Alon et al. (FOCS 1995) which amplifies the distance$\delta$of a code to a constant at ... more >>> TR17-010 | 18th January 2017 Xiaodi Wu, Penghui Yao, Henry Yuen Raz-McKenzie simulation with the inner product gadget Revisions: 1 In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions$f$composed with the Inner Product gadget$g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$of logarithmic size. In other words, given a function$f: ... more >>>

TR18-106 | 30th May 2018
Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices
$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous
logarithmic space.

more >>>

TR09-029 | 3rd April 2009
Fabian Wagner, Thomas Thierauf

Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1

We show that the reachability problem for directed graphs
that are either K_{3,3}-free or K_5-free
is in unambiguous log-space, UL \cap coUL.
This significantly extends the result of Bourke, Tewari, and Vinodchandran
that the reachability problem for directed planar graphs
is in UL \cap coUL.

Our algorithm decomposes ... more >>>

TR15-140 | 26th August 2015
Adam Case, Jack H. Lutz, Donald Stull

Reachability Problems for Continuous Chemical Reaction Networks

Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced a new model of chemical kinetics, rate-independent continuous CRNs ... more >>>

TR11-060 | 15th April 2011
Brady Garvin, Derrick Stolee, Raghunath Tewari, Vinodchandran Variyam

ReachFewL = ReachUL

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

TR10-011 | 22nd January 2010
Amir Shpilka, Ilya Volkovich

An \emph{arithmetic read-once formula} (ROF for short) is a
formula (a circuit whose underlying graph is a tree) in which the
operations are $\{+,\times\}$ and such that every input variable
labels at most one leaf. A \emph{preprocessed ROF} (PROF for
short) is a ROF in which we are allowed to ... more >>>

TR95-042 | 14th September 1995
Beate Bollig, Ingo Wegener

Read-once Projections and Formal Circuit Verification with Binary Decision Diagrams

Computational complexity is concerned with the complexity of solving
problems and computing functions and not with the complexity of verifying
circuit designs.
The importance of formal circuit verification is evident.
Therefore, a framework of a complexity theory for formal circuit
verification with binary decision diagrams ... more >>>

TR12-134 | 22nd October 2012
Alexander Razborov, Emanuele Viola

Revisions: 1

We highlight the challenge of proving correlation bounds
between boolean functions and integer-valued polynomials,
where any non-boolean output counts against correlation.

We prove that integer-valued polynomials of degree $\frac 12 \log_2 \log_2 n$ have zero correlation with parity. Such a
result is false for modular and threshold polynomials.
Its proof ... more >>>

TR10-158 | 31st October 2010
Shiva Kintali

Realizable Paths and the NL vs L Problem

Revisions: 2

A celebrated theorem of Savitch states that NSPACE(S) is contained DSPACE(S^2). In particular, Savitch gave a deterministic algorithm to solve ST-CONNECTIVITY (an NL-complete problem) using O(log^2{n}) space, implying NL is in DSPACE(log^2{n}). While Savitch’s theorem itself has not been improved in the last four decades, studying the space complexity of ... more >>>

TR17-044 | 21st February 2017
Olaf Beyersdorff, Luke Hinde, Ján Pich

Reasons for Hardness in QBF Proof Systems

Revisions: 1

We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction.

The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>>

TR14-041 | 31st March 2014
Shachar Lovett

Recent advances on the log-rank conjecture in communication complexity

The log-rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the deterministic communication complexity of any two-party function is equal to the log of the rank of its associated matrix, up to polynomial factors. Despite much research, we still know very little about this ... more >>>

TR18-151 | 29th August 2018
Ankit Garg, Rafael Oliveira

Recent progress on scaling algorithms and applications

Scaling problems have a rich and diverse history, and thereby have found numerous
applications in several fields of science and engineering. For instance, the matrix scaling problem
has had applications ranging from theoretical computer science to telephone forecasting,
economics, statistics, optimization, among many other fields. Recently, a generalization of matrix
more >>>

TR03-062 | 10th July 2003
Andrei Krokhin, Peter Jonsson

Recognizing Frozen Variables in Constraint Satisfaction Problems

In constraint satisfaction problems over finite domains, some variables
can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constraint relations allowed in the
instances. We show that the complexity of ... more >>>

TR05-008 | 11th December 2004
Neeraj Kayal

Recognizing permutation functions in polynomial time.

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.
The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on
the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map
$f : \mathbb{F}_q ... more >>> TR09-119 | 17th November 2009 Frederic Magniez, Claire Mathieu, Ashwin Nayak Recognizing well-parenthesized expressions in the streaming model Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with$s$different types of parenthesis. We present a one-pass randomized streaming ... more >>> TR15-150 | 13th September 2015 Gaurav Sinha Reconstruction of$\Sigma\Pi\Sigma(2)$Circuits over Reals Revisions: 3 Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing$\Sigma\Pi\Sigma(2)$circuits over$\R$, i.e. depth$-3$circuits with fan-in$2$at the top addition ... more >>> TR19-104 | 6th August 2019 Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich Reconstruction of Depth-$4$Multilinear Circuits We present a deterministic algorithm for reconstructing multilinear$\Sigma\Pi\Sigma\Pi(k)$circuits, i.e. multilinear depth-$4$circuits with fan-in$k$at the top$+$gate. For any fixed$k$, given black-box access to a polynomial$f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$computable by a multilinear$\Sigma\Pi\Sigma\Pi(k)$circuit of size$s$, the algorithm runs in time ... more >>> TR11-153 | 13th November 2011 Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam Reconstruction of Depth-4 Multilinear Circuits with Top fanin 2 We present a randomized algorithm for reconstructing multilinear depth-4 arithmetic circuits with fan-in 2 at the top + gate. The algorithm is given blackbox access to a multilinear polynomial f in F[x_1,..,x_n] computable by a multilinear Sum-Product-Sum-Product(SPSP) circuit of size s and outputs an equivalent multilinear SPSP circuit, runs ... more >>> TR17-021 | 11th February 2017 Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas Reconstruction of full rank Algebraic Branching Programs An algebraic branching program (ABP) A can be modelled as a product expression$X_1\cdot X_2\cdot \dots \cdot X_d$, where$X_1$and$X_d$are$1 \times w$and$w \times 1$matrices respectively, and every other$X_k$is a$w \times w$matrix; the entries of these matrices are linear forms ... more >>> TR18-191 | 10th November 2018 Neeraj Kayal, Chandan Saha Reconstruction of non-degenerate homogeneous depth three circuits A homogeneous depth three circuit$C$computes a polynomial $$f = T_1 + T_2 + ... + T_s ,$$ where each$T_i$is a product of$d$linear forms in$n$variables over some underlying field$\mathbb{F}$. Given black-box access to$f$, can we efficiently reconstruct (i.e. proper learn) a ... more >>> TR14-147 | 6th November 2014 Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman Rectangles Are Nonnegative Juntas Revisions: 1 We develop a new method to prove communication lower bounds for composed functions of the form$f\circ g^n$where$f$is any boolean function on$n$inputs and$g$is a sufficiently hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of$f \circ ... more >>>

TR01-004 | 13th October 2000
Tobias Gärtner, Günter Hotz

Recursive analytic functions of a complex variable

We extend the concept of recursive definition on analytic functions. For special cases of linear primitive recursive definitions we show the existence of natural continuations of the over $\N$ primitive recursive functions to analytic functions. Especially, we show that solutions exist if the coefficients of the linear recursive equation are ... more >>>

TR98-007 | 12th January 1998
Luca Trevisan

Recycling Queries in PCPs and in Linearity Tests

We study query-efficient Probabilistically Checkable
Proofs (PCPs) and linearity tests. We focus on the number
of amortized query bits. A testing algorithm uses $q$ amortized
query bits if, for some constant $k$, it reads $qk$ bits and has
error probability at most $2^{-k}$. The best known ... more >>>

TR05-090 | 17th August 2005

Reducibility Among Equilibrium Problems

We address the fundamental question of whether the Nash equilibria of
a game can be computed in polynomial time. We describe certain
efficient reductions between this problem for
normal form games with a fixed number of players
and graphical games with fixed degree. Our main result is that ... more >>>

TR09-041 | 9th April 2009
Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

Reducibility Among Fractional Stability Problems

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

TR11-113 | 11th August 2011
Emanuele Viola

Reducing 3XOR to listing triangles, an exposition

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

TR99-018 | 8th June 1999
Manindra Agrawal, Somenath Biswas

Reducing Randomness via Chinese Remaindering

We give new randomized algorithms for testing multivariate polynomial
identities over finite fields and rationals. The algorithms use
\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil
in case of rationals where C is the largest coefficient)
random bits to test if a
polynomial P(x_1, ..., x_n) is zero where d_i is ... more >>>

TR16-080 | 18th May 2016
Oded Goldreich

Reducing testing affine spaces to testing linearity

Revisions: 4

We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$
is the indicator function of an $(\ell-k)$-dimensional affine space.
An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky ({\em SIDMA}, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, {\em JCSS}, 1993) ... more >>>

TR20-093 | 23rd June 2020
Ronen Eldan, Dana Moshkovitz

Reduction From Non-Unique Games To Boolean Unique Games

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ... more >>>

TR04-077 | 17th July 2004
Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford

There are two approaches to solving a new supervised learning task: either
been thoroughly analyzed. This paper investigates the latter approach for
classification problems. In addition to obvious theoretical motivations,
there is fairly strong empirical evidence that ... more >>>

TR03-027 | 21st April 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta

Reductions between Disjoint NP-Pairs

We prove that all of the following assertions are equivalent:
There is a many-one complete disjoint NP-pair;
there is a strongly many-one complete disjoint NP-pair;
there is a Turing complete disjoint NP-pair such that all reductions
are smart reductions;
there is a complete disjoint NP-pair for one-to-one, invertible ... more >>>

TR10-172 | 11th November 2010

Reductions Between Expansion Problems

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games Conjecture (Khot, STOC 2002). In particular, the Small-Set Expansion Hypothesis implies the Unique ... more >>>

TR07-071 | 1st August 2007
Jacobo Toran

Reductions to Graph Isomorphism

We show that several reducibility notions coincide when applied to the
Graph Isomorphism (GI) problem. In particular we show that if a set is
many-one logspace reducible to GI, then it is in fact many-one AC^0
reducible to GI. For the case of Turing reducibilities we show that ... more >>>

TR12-054 | 2nd May 2012
Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff

Reductions to the set of random strings:the resource-bounded case

Revisions: 1

This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out by [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it ... more >>>

TR05-068 | 7th July 2005
Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

Redundancy in Complete Sets

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

TR10-052 | 8th March 2010
Melanie Winkler, Berthold Vöcking, Sascha Geulen

Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm

Suppose a decision maker has to purchase a commodity over time with
varying prices and demands. In particular, the price per unit might
depend on the amount purchased and this price function might vary from
step to step. The decision maker has a buffer of bounded size for
storing units ... more >>>

TR11-173 | 22nd December 2011
Christoph Behle, Andreas Krebs

Regular Languages in MAJ[<] with three variables

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

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

TR08-103 | 22nd November 2008

Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

We show that every high-entropy distribution is indistinguishable from an
efficiently samplable distribution of the same entropy. Specifically, we prove
that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,
then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most
m)^2}}}$. This implies an$\exp\of{\Omega(n^{1/3})}$bound when the number of pigeons$m$is arbitrary. more >>> TR01-021 | 7th March 2001 Ran Raz Resolution Lower Bounds for the Weak Pigeonhole Principle Revisions: 1 We prove that any Resolution proof for the weak pigeon hole principle, with$n$holes and any number of pigeons, is of length$\Omega(2^{n^{\epsilon}})$, (for some global constant$\epsilon > 0$). more >>> TR07-078 | 11th August 2007 Ran Raz, Iddo Tzameret Resolution over Linear Equations and Multilinear Proofs We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. ... more >>> TR18-117 | 23rd June 2018 Fedor Part, Iddo Tzameret Resolution with Counting: Lower Bounds over Different Moduli Revisions: 1 Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring$R$. On the one hand, the system captures a natural minimal'' extension of resolution in which efficient counting can be achieved; ... more >>> TR01-085 | 1st October 2001 Gerhard J. Woeginger Resource augmentation for online bounded space bin packing We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b>=1. Its performance is measured by comparing the ... more >>> TR04-066 | 6th July 2004 Tomoyuki Yamakami, Toshio Suzuki Resource Bounded Immunity and Simplicity Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>> TR02-038 | 5th June 2002 Rahul Santhanam Resource Tradeoffs and Derandomization Revisions: 1 We consider uniform assumptions for derandomization. We provide intuitive evidence that BPP can be simulated non-trivially in deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP = P. These results extend and complement earlier work of ... more >>> TR17-119 | 25th July 2017 Badih Ghazi, T.S. Jayram Resource-Efficient Common Randomness and Secret-Key Schemes We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with ... more >>> TR12-082 | 28th June 2012 Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes We prove that a random linear code over$\mathbb{F}_q$, with probability arbitrarily close to$1$, is list decodable at radius$1-1/q-\epsilon$with list size$L=O(1/\epsilon^2)$and rate$R=\Omega_q(\epsilon^2/(\log^3(1/\epsilon)))$. Up to the polylogarithmic factor in$1/\epsilon$and constant factors depending on$q$, this matches the lower bound$L=\Omega_q(1/\epsilon^2)$for the list ... more >>> TR00-048 | 3rd July 2000 Beate Bollig Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, i.e., the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once more >>> TR09-094 | 7th October 2009 Bireswar Das, Jacobo Toran, Fabian Wagner Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}. We give restricted space algorithms for these problems proving the following results: Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>> TR11-160 | 1st December 2011 Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff Restriction Access We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{restriction access}. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On ... more >>> TR19-097 | 4th July 2019 Jacobo Toran, Florian Wörz Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space Revisions: 1 , Comments: 1 We show a new connection between the space measure in tree-like resolution and the reversible pebble game in graphs. Using this connection we provide several formula classes for which there is a logarithmic factor separation between the space complexity measure in tree-like and general resolution. We show that these separations ... more >>> TR05-032 | 16th March 2005 Gudmund Skovbjerg Frandsen, Peter Bro Miltersen Reviewing Bounds on the Circuit Size of the Hardest Functions In this paper we review the known bounds for$L(n)$, the circuit size complexity of the hardest Boolean function on$n$input bits. The best known bounds appear to be $$\frac{2^n}{n}(1+\frac{\log n}{n}-O(\frac{1}{n})) \leq L(n) \leq\frac{2^n}{n}(1+3\frac{\log n}{n}+O(\frac{1}{n}))$$ However, the bounds do not seem to be explicitly stated in the literature. We ... more >>> TR19-092 | 9th July 2019 Venkatesan Guruswami, Jakub Opršal, Sai Sandeep Revisiting Alphabet Reduction in Dinur's PCP Dinur's celebrated proof of the PCP theorem alternates two main steps in several iterations: gap amplification to increase the soundness gap by a large constant factor (at the expense of much larger alphabet size), and a composition step that brings back the alphabet size to an absolute constant (at the ... more >>> TR13-113 | 19th August 2013 Moritz Müller, Stefan Szeider Revisiting Space in Proof Complexity: Treewidth and Pathwidth So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations ... more >>> TR02-043 | 11th July 2002 Dalit Naor, Moni Naor, Jeff Lotspiech Revocation and Tracing Schemes for Stateless Receivers We deal with the problem of a center sending a secret message to a group of users such that some subset of the users is considered revoked and should not be able to obtain the content of the message. We concentrate on the stateless receiver case, where the users do ... more >>> TR20-075 | 6th May 2020 Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal Rigid Matrices From Rectangular PCPs Revisions: 1 We introduce a variant of PCPs, that we refer to as *rectangular* PCPs, wherein proofs are thought of as square matrices, and the random coins used by the verifier can be partitioned into two disjoint sets, one determining the *row* of each query and the other determining the *column*. We ... more >>> TR14-066 | 17th April 2014 Suguru Tamaki, Yuichi Yoshida Robust Approximation of Temporal CSP A temporal constraint language$\Gamma$is a set of relations with first-order definitions in$({\mathbb{Q}}; <)$. Let CSP($\Gamma$) denote the set of constraint satisfaction problem instances with relations from$\Gamma$. CSP($\Gamma$) admits robust approximation if, for any$\varepsilon \geq 0$, given a$(1-\varepsilon)$-satisfiable instance of CSP($\Gamma$), we can compute an ... more >>> TR06-118 | 2nd September 2006 Irit Dinur, Madhu Sudan, Avi Wigderson Robust Local Testability of Tensor Products of LDPC Codes Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>> TR04-046 | 4th June 2004 Eli Ben-Sasson, Madhu Sudan Robust Locally Testable Codes and Products of Codes We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically ... more >>> TR11-062 | 18th April 2011 Amit Chakrabarti, Graham Cormode, Andrew McGregor Robust Lower Bounds for Communication and Stream Computation We study the communication complexity of evaluating functions when the input data is randomly allocated (according to some known distribution) amongst two or more players, possibly with information overlap. This naturally extends previously studied variable partition models such as the best-case and worst-case partition models. We aim to understand whether ... more >>> TR16-204 | 20th December 2016 Prahladh Harsha, Srikanth Srinivasan Robust Multiplication-based Tests for Reed-Muller Codes We consider the following multiplication-based tests to check if a given function$f: \mathbb{F}_q^n\to \mathbb{F}_q$is the evaluation of a degree-$d$polynomial over$\mathbb{F}_q$for$q$prime. *$\mathrm{Test}_{e,k}$: Pick$P_1,\ldots,P_k$independent random degree-$e$polynomials and accept iff the function$fP_1\cdots P_k$is the evaluation of a degree-$(d+ek)$polynomial. ... more >>> TR04-021 | 23rd March 2004 Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan Robust PCPs of Proximity, Shorter PCPs and Applications to Coding We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size$n$): We present PCPs of length$\exp(\tildeO(\log\log n)^2)\cdot n$that can be verified by making$o(\log\log n)$Boolean queries. more >>> TR13-143 | 19th October 2013 Yuval Ishai, Eyal Kushilevitz, Xin Li, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai, David Zuckerman Robust Pseudorandom Generators Revisions: 1 Let$G:\{0,1\}^n\to\{0,1\}^m$be a pseudorandom generator. We say that a circuit implementation of$G$is$(k,q)$-robust if for every set$S$of at most$k$wires anywhere in the circuit, there is a set$T$of at most$q|S|$outputs, such that conditioned on the values of$S$and$T$... more >>> TR11-163 | 2nd December 2011 Libor Barto, Marcin Kozik Robust Satisfiability of Constraint Satisfaction Problems An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least$(1-g(\varepsilon))$-fraction of the constraints given a$(1-\varepsilon)$-satisfiable instance, where$g(\varepsilon) \rightarrow 0$as$\varepsilon \rightarrow 0$,$g(0)=0\$.
Guruswami and Zhou conjectured a characterization of constraint languages for which the corresponding constraint satisfaction ... more >>>

TR16-161 | 26th October 2016
Shachar Lovett, Jiapeng Zhang

Robust sensitivity

Revisions: 1

The sensitivity conjecture is one of the central open problems in boolean complexity. A recent work of Gopalan et al. [CCC 2016] conjectured a robust analog of the sensitivity conjecture, which relates the decay of the Fourier mass of a boolean function to moments of its sensitivity. We prove this ... more >>>

TR15-043 | 2nd April 2015

Robust testing of lifted codes with applications to low-degree testing

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be robust'' ... more >>>

TR17-055 | 26th March 2017
Maya Leshkowitz

Round Complexity Versus Randomness Complexity in Interactive Proofs

Consider an interactive proof system for some set S that has randomness complexity r(n) for instances of length n, and arbitrary round complexity. We show a public-coin interactive proof system for S of round complexity O(r(n)/log n). Furthermore, the randomness complexity is preserved up to a constant factor, and the ... more >>>

TR06-093 | 27th July 2006
Takeshi Koshiba, Yoshiharu Seri

Round-Efficient One-Way Permutation Based Perfectly Concealing Bit Commitment Scheme

We explicitly show the upper bound on the round complexity for perfectly concealing bit commitment schemes based on the general computational assumption. The best known scheme in the literature is the one-way permutation based scheme due to Naor, Ostrovsky, Venkatesan and Yung and its round complexity is O(n). We consider ... more >>>

TR11-065 | 25th April 2011
Boaz Barak, Prasad Raghavendra, David Steurer

Rounding Semidefinite Programming Hierarchies via Global Correlation

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

TR13-184 | 23rd December 2013
Boaz Barak, Jonathan Kelner, David Steurer

Rounding Sum-of-Squares Relaxations

We present a general approach to rounding semidefinite programming relaxations obtained by the Sum-of-Squares method (Lasserre hierarchy). Our approach is based on using the connection between these relaxations and the Sum-of-Squares proof system to transform a *combining algorithm* -- an algorithm that maps a distribution over solutions into a (possibly ... more >>>

TR03-040 | 3rd June 2003
Philippe Moser

RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

We use recent results on the hardness of resource-bounded
Kolmogorov random strings, to prove that RP is small in SUBEXP
else ZPP=PSPACE and NP=EXP.
We also prove that if NP is not small in SUBEXP, then
NP=AM, improving a former result which held for the measure ... more >>>

TR06-084 | 19th June 2006
Frank Neumann, Carsten Witt

Runtime Analysis of a Simple Ant Colony Optimization Algorithm

Ant Colony Optimization (ACO) has become quite popular in recent
years. In contrast to many successful applications, the theoretical
foundation of this randomized search heuristic is rather weak.
Building up such a theory is demanded to understand how these
heuristics work as well as to ... more >>>

ISSN 1433-8092 | Imprint