Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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
TR22-131 | 18th September 2022
Rafael Mendes de Oliveira, Akash Sengupta

Radical Sylvester-Gallai for Cubics

Let $\mathcal{F} = \{F_1, \ldots, F_m\}$ be a finite set of irreducible homogeneous multivariate polynomials of degree at most $3$ such that $F_i$ does not divide $F_j$ for $i\neq j$.
We say that $\mathcal{F}$ is a cubic radical Sylvester-Gallai configuration if for any two distinct $F_i,F_j$ there exists a ... more >>>


TR23-074 | 14th May 2023
Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta

Radical Sylvester-Gallai Theorem for Tuples of Quadratics

We prove a higher codimensional radical Sylvester-Gallai type theorem for quadratic polynomials, simultaneously generalizing [Han65, Shp20]. Hansen's theorem is a high-dimensional version of the classical Sylvester-Gallai theorem in which the incidence condition is given by high-dimensional flats instead of lines. We generalize Hansen's theorem to the setting of quadratic forms ... more >>>


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

Radio Network Coding Requires Logarithmic Overhead

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


TR23-086 | 8th June 2023
Dmitry Sokolov

Random $(\log n)$-CNF are Hard for Cutting Planes (Again)

The random $\Delta$-CNF model is one of the most important distribution over $\Delta\text{-}\mathrm{SAT}$ instances. It is closely connected to various areas of computer science, statistical physics, and is a benchmark for satisfiability algorithms. Fleming, Pankratov, Pitassi, and Robere and independently Hrubes and Pudlak showed that when $\Delta = \Theta(\log n)$, ... 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

Comments: 1

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


TR21-047 | 26th March 2021
Zander Kelley, Raghu Meka

Random restrictions and PRGs for PTFs in Gaussian Space

Revisions: 1

A polynomial threshold function (PTF) $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is a function of the form $f(x) = sign(p(x))$ where $p$ is a polynomial of degree at most $d$. PTFs are a classical and well-studied complexity class with applications across complexity theory, learning theory, approximation theory, quantum complexity and more. We address ... 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
Ronen Gradwohl, Salil Vadhan, David Zuckerman

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


TR23-128 | 30th August 2023
Xue Chen, Kuan Cheng, Xin Li, Songtao Mao

Random Shortening of Linear Codes and Application

Random linear codes (RLCs) are well known to have nice combinatorial properties and near-optimal parameters in many different settings. However, getting explicit constructions matching the parameters of RLCs is challenging, and RLCs are hard to decode efficiently. This motivated several previous works to study the problem of partially derandomizing RLCs, ... more >>>


TR21-008 | 30th January 2021
Akash Kumar, C. Seshadhri, Andrew Stolman

Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes

Revisions: 3

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, for a sufficiently small ? > 0, one removes
?dn ... more >>>


TR22-163 | 16th November 2022
Gil Cohen, Gal Maor

Random Walks on Rotating Expanders

Random walks on expanders are a powerful tool which found applications in many areas of theoretical computer science, and beyond. However, they come with an inherent cost -- the spectral expansion of the corresponding power graph deteriorates at a rate that is exponential in the length of the walk. As ... 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 >>>


TR22-112 | 12th August 2022
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

Randomised Composition and Small-Bias Minimax

We prove two results about randomised query complexity $\mathrm{R}(f)$. First, we introduce a linearised complexity measure $\mathrm{LR}$ and show that it satisfies an inner-optimal composition theorem: $\mathrm{R}(f\circ g) \geq \Omega(\mathrm{R}(f) \mathrm{LR}(g))$ for all partial $f$ and $g$, and moreover, $\mathrm{LR}$ is the largest possible measure with this property. In particular, ... 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
quadratic, ... more >>>


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

Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests

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


TR24-016 | 27th January 2024
Swagato Sanyal

Randomized query composition and product distributions

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... 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 >>>


TR22-185 | 29th December 2022
Arkadev Chattopadhyay, Yogesh Dahiya, Nikhil Mande, Jaikumar Radhakrishnan, Swagato Sanyal

Randomized versus Deterministic Decision Tree Size

A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been ... more >>>


TR23-096 | 28th June 2023
Huacheng Yu, Wei Zhan

Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

We prove the first polynomial separation between randomized and deterministic time-space tradeoffs of multi-output functions. In particular, we present a total function that on the input of $n$ elements in $[n]$, outputs $O(n)$ elements, such that:

- There exists a randomized oblivious algorithm with space $O(\log n)$, time $O(n\log n)$ ... 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 >>>


TR23-125 | 25th August 2023
Omar Alrabiah, Venkatesan Guruswami, Ray Li

Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields

Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field elements. They are widely known for their optimal unique-decoding capabilities, but their list-decoding capabilities are not fully understood. Given the prevalence of Reed-Solomon codes, a ... 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 >>>


TR24-040 | 29th February 2024
Kuan Cheng, Ruiyang Wu

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant ... 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 >>>

TR23-021 | 9th March 2023
Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms

Revisions: 2

Range Avoidance (AVOID) is a total search problem where, given a Boolean circuit $C\colon\{0,1\}^n\to\{0,1\}^m$, $m>n$, the task is to find a $y\in\{0,1\}^m$ outside the range of $C$. For an integer $k\geq 2$, $NC^0_k$-AVOID is a special case of AVOID where each output bit of $C$ depends on at most $k$ ... more >>>


TR22-102 | 15th July 2022
Venkatesan Guruswami, Xin Lyu, Xiuhan Wang

Range Avoidance for Low-depth Circuits and Connections to Pseudorandomness

In the range avoidance problem, the input is a multi-output Boolean circuit with more outputs than inputs, and the goal is to find a string outside its range (which is guaranteed to exist). We show that well-known explicit construction questions such as finding binary linear codes achieving the Gilbert-Varshamov bound ... more >>>


TR23-072 | 18th May 2023
Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren

Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms

The *range avoidance problem*, denoted as $\mathcal{C}$-$\rm Avoid$, asks to find a non-output of a given $\mathcal{C}$-circuit $C:\{0,1\}^n\to\{0,1\}^\ell$ with stretch $\ell>n$. This problem has recently received much attention in complexity theory for its connections with circuit lower bounds and other explicit construction problems. Inspired by the Algorithmic Method for circuit ... 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

Revisions: 1

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, N. V. Vinodchandran

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

Read-Once Polynomial Identity Testing

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

Real Advantage

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


TR22-121 | 27th August 2022
William Hoza

Recent Progress on Derandomizing Space-Bounded Computation

Revisions: 1

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... 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 >>>


TR20-178 | 30th November 2020
Stasys Jukna, Hannes Seiwert, Igor Sergeev

Reciprocal Inputs in Arithmetic and Tropical Circuits

It is known that the size of monotone arithmetic $(+,\ast)$ circuits can be exponentially decreased by allowing just one division "at the very end," at the output gate. A natural question is: can the size of $(+,\ast)$ circuits be substantially reduced if we allow divisions "at the very beginning," that ... 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 >>>


TR21-045 | 22nd March 2021
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... 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 >>>


TR22-171 | 21st November 2022
ECCC Admin

Record removed

This record is a placeholder, replacing a record that was generated by mistake.

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


TR23-130 | 8th September 2023
Eshan Chattopadhyay, Jyun-Jie Liao

Recursive Error Reduction for Regular Branching Programs

Revisions: 1

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... 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
Paul Goldberg, Christos H. Papadimitriou

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


TR23-073 | 15th May 2023
Xi Chen, Yuhao Li, Mihalis Yannakakis

Reducing Tarski to Unique Tarski (in the Black-box Model)

We study the problem of finding a Tarski fixed point over the $k$-dimensional grid $[n]^k$. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... 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

Revisions: 1

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

Reductions Between Classification Tasks

There are two approaches to solving a new supervised learning task: either
analyze the task independently or reduce it to a task that has already
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
Prasad Raghavendra, David Steurer, Madhur Tulsiani

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


TR24-045 | 6th March 2024
Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria

Redundancy for MaxSAT

The concept of redundancy in SAT lead to more expressive and powerful proof search techniques, e.g. able to express various inprocessing techniques, and to interesting hierarchies of proof systems [Heule et.al’20, Buss-Thapen’19].
We propose a general way to integrate redundancy rules in MaxSAT, that is we define MaxSAT variants of ... 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 >>>


TR21-061 | 29th April 2021
Noah Fleming, Toniann Pitassi

Reflections on Proof Complexity and Counting Principles

This paper surveys the development of propositional proof complexity and the seminal contributions of Alasdair Urquhart. We focus on the central role of counting principles, and in particular Tseitin's graph tautologies, to most of the key advances in lower bounds in proof complexity. We reflect on a couple of key ... more >>>


TR23-203 | 15th December 2023
Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni

Refuting approaches to the log-rank conjecture for XOR functions

The log-rank conjecture, a longstanding problem in communication complexity, has persistently eluded resolution for decades. Consequently, some recent efforts have focused on potential approaches for establishing the conjecture in the special case of XOR functions, where the communication matrix is lifted from a boolean function, and the rank of ... 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 >>>


TR24-033 | 24th February 2024
Sam Buss, Emre Yolcu

Regular resolution effectively simulates resolution

Regular resolution is a refinement of the resolution proof system requiring that no variable be resolved on more than once along any path in the proof. It is known that there exist sequences of formulas that require exponential-size proofs in regular resolution while admitting polynomial-size proofs in resolution. Thus, with ... more >>>


TR08-103 | 22nd November 2008
Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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
$S\cdot ... more >>>


TR20-159 | 9th October 2020
Leroy Chew, Marijn Heule

Relating existing powerful proof systems for QBF

We advance the theory of QBF proof systems by showing the first simulation of the universal checking format QRAT by a theory-friendly system. We show that the sequent system G fully p-simulates QRAT, including the Extended Universal Reduction (EUR) rule which was recently used to show QRAT does not ... more >>>


TR16-164 | 25th October 2016
Andreas Krebs, Meena Mahajan, Anil Shukla

Relating two width measures for resolution proofs

In this short note, we revisit two hardness measures for resolution proofs: width and asymmetric width. It is known that for every unsatisfiable CNF F,

width(F \derives \Box) \le awidth(F \derives \Box) + max{ awidth(F \derives \Box), width(F)}.

We give a simple direct proof of the upper bound, ... more >>>


TR10-040 | 10th March 2010
Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

Relationless completeness and separations

This paper extends Valiant's work on $\vp$ and $\vnp$ to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds.
We define analogs of Valiant's classes $\vp$ and $\vnp$, as well as of the polynomials permanent ... more >>>


TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>


TR15-028 | 27th February 2015
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Relative Discrepancy does not separate Information and Communication Complexity

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>


TR18-103 | 30th April 2018
Zhao Song, David Woodruff, Peilin Zhong

Relative Error Tensor Low Rank Approximation

We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$ tensor $A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$ tensor $B$ for which $\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where ${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>>


TR01-068 | 19th September 2001
Philippe Moser

Relative to P, APP and promise-BPP are the same

Revisions: 1

We show that for determinictic polynomial time computation, oracle access to
$\mathbf{APP}$, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-$\mathbf{BPP}$. First
we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem
more >>>


TR03-084 | 27th November 2003
Joshua Buresh-Oppenheim, Tsuyoshi Morioka

Relativized NP Search Problems and Propositional Proof Systems

We consider Total Functional $\NP$ ($\TFNP$) search problems. Such problems are based on combinatorial principles that guarantee, through locally checkable conditions, that a solution to the problem exists in an exponentially-large domain, and have the property that any solution has a polynomial-size witness that can be verified in polynomial time. ... more >>>


TR10-042 | 12th March 2010
Thomas Watson

Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

Revisions: 3

We prove that relative to an oracle, there is no worst-case to errorless-average-case reduction for $\NP$. This result is the first progress on an open problem posed by Impagliazzo in 1995, namely to construct an oracle relative to which $\NP$ is worst-case hard but errorless-average-case easy. We also handle classes ... more >>>


TR23-093 | 29th June 2023
Vinayak Kumar, Geoffrey Mon

Relaxed Local Correctability from Local Testing

We cement the intuitive connection between relaxed local correctability and local testing by presenting a concrete framework for building a relaxed locally correctable code from any family of linear locally testable codes with sufficiently high rate. When instantiated using the locally testable codes of Dinur et al. (STOC 2022), this ... more >>>


TR17-143 | 26th September 2017
Tom Gur, Govind Ramnarayan, Ron Rothblum

Relaxed Locally Correctable Codes

Revisions: 1

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... more >>>


TR20-142 | 15th September 2020
Vahid Reza Asadi, Igor Shinkar

Relaxed Locally Correctable Codes with Improved Parameters

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>


TR20-113 | 27th July 2020
Alessandro Chiesa, Tom Gur, Igor Shinkar

Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>


TR22-045 | 4th April 2022
Gil Cohen, Tal Yankovitz

Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring

Revisions: 1

In their highly influential paper, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004) introduced the notion of a relaxed locally decodable code (RLDC). Similarly to a locally decodable code (Katz-Trevisan; STOC 2000), the former admits access to any desired message symbol with only a few queries to a possibly corrupted ... more >>>


TR15-199 | 7th December 2015
Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Relaxed partition bound is quadratically tight for product distributions

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>


TR15-014 | 18th January 2015
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Reliable Communication over Highly Connected Noisy Networks

We consider the task of multiparty computation performed over networks in
the presence of random noise. Given an $n$-party protocol that takes $R$
rounds assuming noiseless communication, the goal is to find a coding
scheme that takes $R'$ rounds and computes the same function with high
probability even when the ... more >>>


TR18-041 | 26th February 2018
Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Reordering Rule Makes OBDD Proof Systems Stronger

Atserias, Kolaitis, and Vardi [AKV04] showed that the proof system of Ordered Binary Decision Diagrams with conjunction and weakening, OBDD($\land$, weakening), simulates CP* (Cutting Planes with unary coefficients). We show that OBDD($\land$, weakening) can give exponentially shorter proofs than dag-like cutting planes. This is proved by showing that the Clique-Coloring ... more >>>


TR04-082 | 9th September 2004
Olaf Beyersdorff

Representable Disjoint NP-Pairs

Revisions: 1

We investigate the class of disjoint NP-pairs under different reductions.
The structure of this class is intimately linked to the simulation order
of propositional proof systems, and we make use of the relationship between
propositional proof systems and theories of bounded arithmetic as the main
tool of our analysis.
more >>>


TR15-157 | 1st September 2015
Thomas O'Neil

Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability

A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for ... more >>>


TR17-106 | 16th June 2017
Mateus de Oliveira Oliveira, Pavel Pudlak

Representations of Monotone Boolean Functions by Linear Programs

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of
computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.
2. MLP circuits are exponentially stronger than monotone span programs.
3. ... more >>>


TR06-158 | 8th December 2006
Gyula Gyôr

Representing Boolean OR function by quadratic polynomials modulo 6

We give an answer to the question of Barrington, Beigel and Rudich, asked in 1992, concerning the largest n such that the OR function of n variable can be weakly represented by a quadratic polynomial modulo 6. More specially,we show that no 11-variable quadratic polynomial exists that is congruent to ... more >>>


TR18-048 | 11th March 2018
Ofer Grossman, Yang P. Liu

Reproducibility and Pseudo-Determinism in Log-Space

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits ... more >>>


TR99-042 | 24th October 1999
Ran Canetti, Oded Goldreich, Silvio Micali.

Resettable Zero-Knowledge.

Revisions: 1


We introduce the notion of Resettable Zero-Knowledge (rZK),
a new security measure for cryptographic protocols
which strengthens the classical notion of zero-knowledge.
In essence, an rZK protocol is one that remains zero knowledge
even if an adeversary can interact with the prover many times, each
time ... more >>>


TR04-112 | 26th November 2004
Neil Thapen, Nicola Galesi

Resolution and pebbling games

We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width.

We also use games to give upper ... more >>>


TR18-165 | 20th September 2018
Stefan Dantchev, Nicola Galesi, Barnaby Martin

Resolution and the binary encoding of combinatorial principles

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>


TR14-093 | 22nd July 2014
Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov

Resolution complexity of perfect mathcing principles for sparse graphs

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph $G_n$ such that the resolution complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$, where $n$ is ... more >>>


TR19-084 | 26th May 2019
Michal Garlik

Resolution Lower Bounds for Refutation Statements

For any unsatisfiable CNF formula we give an exponential lower bound on the size of resolution refutations of a propositional statement that the formula has a resolution refutation. We describe three applications. (1) An open question in [Atserias-Müller,2019] asks whether a certain natural propositional encoding of the above statement is ... more >>>


TR01-075 | 2nd November 2001
Alexander Razborov

Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

We show that every resolution proof of the {\em functional} version
$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split
between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log
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: 2

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


TR23-179 | 18th November 2023
Ian Mertz

Reusing Space: Techniques and Open Problems

In the world of space-bounded complexity, there is a strain of results showing that space can, somewhat paradoxically, be used for multiple purposes at once. Touchstone results include Barrington’s Theorem and the recent line of work on catalytic computing. We refer to such techniques, in contrast to the usual notion ... 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 >>>


TR21-145 | 19th October 2021
Omar Alrabiah, Venkatesan Guruswami

Revisiting a Lower Bound on the Redundancy of Linear Batch Codes

A recent work of Li and Wootters (2021) shows a redundancy lower bound of $\Omega(\sqrt{Nk})$ for systematic linear $k$-batch codes of block length $N$ by looking at the $O(k)$ tensor power of the dual code. In this note, we present an alternate proof of their result via a linear independence ... 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 >>>


TR22-145 | 4th November 2022
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

Revisiting Time-Space Tradeoffs for Function Inversion

Revisions: 1

We study the black-box function inversion problem, which is the problem of finding $x \in [N]$ such that $f(x) = y$, given as input some challenge point $y$ in the image of a function $f : [N] \to [N]$, using $T$ oracle queries to $f$ and preprocessed advice $\sigma \in ... 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: 2

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


TR22-037 | 10th March 2022
Abhibhav Garg, Rafael Mendes de Oliveira, Akash Sengupta

Robust Radical Sylvester-Gallai Theorem for Quadratics

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials, generalizing the result in [S'20].
More precisely, given a parameter $0 < \delta \leq 1$ and a finite collection $\mathcal{F}$ of irreducible and pairwise independent polynomials of degree at most 2, we say that $\mathcal{F}$ is a ... 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 >>>


TR21-034 | 9th March 2021
Oded Goldreich

Robust Self-Ordering versus Local Self-Ordering

Revisions: 1

We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph.

A {\em local self-ordering} procedure for a graph $G$ is given oracle access to an arbitrary isomorphic copy of ... 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
Alan Guo, Elad Haramaty, Madhu Sudan

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


TR21-005 | 13th January 2021
Anindya De, Elchanan Mossel, Joe Neeman

Robust testing of low-dimensional functions

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>


TR20-149 | 29th September 2020
Oded Goldreich, Avi Wigderson

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2


A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>


TR22-071 | 13th May 2022
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>


TR22-138 | 5th October 2022
Eric Allender, Jacob Gray, Saachi Mutreja, Harsha Tirumala, Pengxiang Wang

Robustness for Space-Bounded Statistical Zero Knowledge

Revisions: 2

We show that the space-bounded Statistical Zero Knowledge classes SZK_L and NISZK_L are surprisingly robust, in that the power of the verifier and simulator can be strengthened or weakened without affecting the resulting class. Coupled with other recent characterizations of these classes, this can be viewed as lending support to ... 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 >>>


TR22-179 | 16th December 2022
Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

Round-vs-Resilience Tradeoffs for Binary Feedback Channels

In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization ... 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 >>>


TR22-136 | 21st September 2022
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Rounds vs Communication Tradeoffs for Maximal Independent Sets

We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges incident on its vertex -- this way, each edge is known by both ... 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 >>>


TR23-047 | 2nd April 2023
Hunter Monroe

Ruling Out Short Proofs of Unprovable Sentences is Hard

If no optimal propositional proof system exists, we (and independently Pudlák) prove that ruling out length $t$ proofs of any unprovable sentence is hard. This mapping from unprovable to hard-to-prove sentences powerfully translates facts about noncomputability into complexity theory. For instance, because proving string $x$ is Kolmogorov random ($x{\in}R$) is ... 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