Under the auspices of the Computational Complexity Foundation (CCF)

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

I
TR04-058 | 28th May 2004
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

Identifying Clusters from Positive Data

The present work studies clustering from an abstract point of view
and investigates its properties in the framework of inductive inference.
Any class $S$ considered is given by a numbering
$A_0,A_1,...$ of nonempty subsets of the natural numbers
or the rational k-dimensional vector space as a hypothesis space.
A clustering ... more >>>

TR15-184 | 21st November 2015
Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).
In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ... more >>>

TR16-193 | 22nd November 2016
Vikraman Arvind, Pushkar Joglekar, Partha Mukhopadhyay, Raja S

Identity Testing for +-Regular Noncommutative Arithmetic Circuits

An efficient randomized polynomial identity test for noncommutative
polynomials given by noncommutative arithmetic circuits remains an
open problem. The main bottleneck to applying known techniques is that
a noncommutative circuit of size $s$ can compute a polynomial of
degree exponential in $s$ with a double-exponential number of nonzero
monomials. ... more >>>

TR16-009 | 28th January 2016
Rohit Gurjar, Arpita Korwar, Nitin Saxena

Identity Testing for constant-width, and commutative, read-once oblivious ABPs

We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost $(nw)^{O(\log n)}$, where $n$ is the number of variables and $w$ is the width of ... more >>>

TR03-055 | 20th July 2003
Jan Krajicek

Implicit proofs

We describe a general method how to construct from
a propositional proof system P a possibly much stronger
proof system iP. The system iP operates with
exponentially long P-proofs described implicitly''
by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF,
corresponds to bounded ... more >>>

TR07-028 | 12th February 2007
Daniel Sawitzki

Implicit Simulation of FNC Algorithms

Implicit algorithms work on their input's characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms ... more >>>

TR00-039 | 25th April 2000
Yevgeniy Dodis

Collective Coin-Flipping is a classical problem where n
computationally unbounded processors are trying to generate a random
bit in a setting where only a single broadcast channel is available
for communication. The protocol is said to be b(n)-resilient if any
adversary that can corrupt up to b(n) players, still cannot ... more >>>

TR20-098 | 4th July 2020
Manindra Agrawal, Rohit Gurjar, Thomas Thierauf

Impossibility of Derandomizing the Isolation Lemma for all Families

The Isolation Lemma states that when random weights are assigned to the elements of a finite set $E$, then in any given family of subsets of $E$, exactly one set has the minimum weight, with high probability. In this note, we present two proofs for the fact that it is ... more >>>

TR11-001 | 2nd January 2011
Scott Aaronson

Impossibility of Succinct Quantum Proofs for Collision-Freeness

We show that any quantum algorithm to decide whether a function $f:\left[n\right] \rightarrow\left[ n\right]$ is a permutation or far from a permutation\ must make $\Omega\left( n^{1/3}/w\right)$ queries to $f$, even if the algorithm is given a $w$-qubit quantum witness in support of $f$ being a permutation. This implies ... more >>>

TR19-093 | 15th July 2019
Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

Improved 3LIN Hardness via Linear Label Cover

We prove that for every constant $c$ and $\epsilon = (\log n)^{-c}$, there is no polynomial time algorithm that when given an instance of 3LIN with $n$ variables where an $(1 - \epsilon)$-fraction of the clauses are satisfiable, finds an assignment that satisfies at least $(\frac{1}{2} + \epsilon)$-fraction of clauses ... more >>>

TR06-110 | 15th August 2006
Nishanth Chandran, Ryan Moriarty, Rafail Ostrovsky, Omkant Pandey, Amit Sahai

Improved Algorithms for Optimal Embeddings

In the last decade, the notion of metric embeddings with
small distortion received wide attention in the literature, with
applications in combinatorial optimization, discrete mathematics, functional
analysis and bio-informatics. The notion of embedding is, given two metric
spaces on the same number of points, to find a bijection that minimizes
more >>>

TR15-112 | 16th July 2015
Ruiwen Chen, Rahul Santhanam

Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-$k$-CSP. For instances with $n$ variables and $cn$ clauses (constraints), we give algorithms running in time $\poly(n)\cdot 2^{n(1-\mu)}$ for
\begin{itemize}
\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,
\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and ... more >>>

TR10-041 | 11th March 2010
Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

Improved Algorithms for Unique Games via Divide and Conquer

We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>>

TR09-076 | 19th August 2009
Christian Glaßer, Christian Reitwießner, Maximilian Witek

Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

TR20-020 | 21st February 2020
Nikhil Mande, Justin Thaler, Shuchen Zhu

Improved Approximate Degree Bounds For $k$-distinctness

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the $k$-distinctness function on inputs of size $N$. While the case of $k=2$ (also called Element Distinctness) is well-understood, there is a polynomial gap between ... more >>>

TR07-120 | 5th October 2007
Sharon Feldman, Guy Kortsarz, Zeev Nutov

Improved approximation algorithms for directed Steiner forest

We consider the k-Directed Steiner Forest} (k-dsf) problem:
given a directed graph G=(V,E) with edge costs, a collection D subseteq V \times V
of ordered node pairs, and an integer k leq |D|, find a minimum cost subgraph
H of G
that contains an st-path for (at least) k ... more >>>

TR03-008 | 11th February 2003
Piotr Berman, Marek Karpinski

Improved Approximation Lower Bounds on Small Occurrence Optimization

We improve a number of approximation lower bounds for
bounded occurrence optimization problems like MAX-2SAT,
E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching.

more >>>

TR00-021 | 19th April 2000
Uriel Feige, Marek Karpinski, Michael Langberg

Improved Approximation of MAX-CUT on Graphs of Bounded Degree

We analyze the addition of a simple local improvement step to various known
randomized approximation algorithms.
Let $\alpha \simeq 0.87856$ denote the best approximation ratio currently
known for the Max Cut problem on general graphs~\cite{GW95}.
We consider a semidefinite relaxation of the Max Cut problem,
round it using the ... more >>>

TR01-097 | 11th December 2001
Piotr Berman, Marek Karpinski

Improved Approximations for General Minimum Cost Scheduling

We give improved trade-off results on approximating general
minimum cost scheduling problems.

more >>>

TR13-058 | 5th April 2013
Ilan Komargodski, Ran Raz, Avishay Tal

Improved Average-Case Lower Bounds for DeMorgan Formula Size

Revisions: 2

We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).

Our technical contributions include a theorem that shows that the expected ... more >>>

TR05-159 | 14th November 2005
Daniel Rolf

Improved Bound for the PPSZ/Schöning-Algorithm for $3$-SAT

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, Schöning proved ... more >>>

TR10-192 | 8th December 2010
Frederic Magniez, Ashwin Nayak, Miklos Santha, David Xiao

Improved bounds for the randomized decision tree complexity of recursive majority

Revisions: 1

We consider the randomized decision tree complexity of the recursive 3-majority function. For evaluating a height $h$ formulae, we prove a lower bound for the $\delta$-two-sided-error randomized decision tree complexity of $(1-2\delta)(5/2)^h$, improving the lower bound of $(1-2\delta)(7/3)^h$ given by Jayram et al. (STOC '03). We also state a conjecture ... more >>>

TR19-164 | 6th November 2019
Siddharth Bhandari, Sayantan Chakraborty

Improved bounds for perfect sampling of $k$-colorings in graphs

Revisions: 1

We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k > 3\Delta$, and returns a random proper $k$-coloring of $G$. The
distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; ... more >>>

TR16-191 | 24th November 2016
Roei Tell

Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Revisions: 3

Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.

In ... more >>>

TR19-110 | 23rd August 2019
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang

Improved bounds for the sunflower lemma

A sunflower with $r$ petals is a collection of $r$ sets so that the
intersection of each pair is equal to the intersection of all. Erd\H{o}s and Rado proved the sunflower lemma: for any fixed $r$, any family of sets of size $w$, with at least about $w^w$ sets, must ... more >>>

TR18-167 | 25th September 2018
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

Improved bounds on Fourier entropy and Min-entropy

Given a Boolean function $f: \{-1,1\}^n\rightarrow \{-1,1\}$, define the Fourier distribution to be the distribution on subsets of $[n]$, where each $S\subseteq [n]$ is sampled with probability $\widehat{f}(S)^2$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>

TR19-171 | 27th November 2019
Oded Goldreich

Improved bounds on the AN-complexity of multilinear functions

Revisions: 2

We consider arithmetic circuits with arbitrary large (multi-linear) gates for computing multi-linear functions. An adequate complexity measure for such circuits is the maximum between the arity of the gates and their number.
This model and the corresponding complexity measure were introduced by Goldreich and Wigderson (ECCC, TR13-043, 2013), ... more >>>

TR16-075 | 9th May 2016
Mark Bun, Justin Thaler

Improved Bounds on the Sign-Rank of AC$^0$

Revisions: 1

The sign-rank of a matrix $A$ with entries in $\{-1, +1\}$ is the least rank of a real matrix $B$ with $A_{ij} \cdot B_{ij} > 0$ for all $i, j$. Razborov and Sherstov (2008) gave the first exponential lower bounds on the sign-rank of a function in AC$^0$, answering an ... more >>>

TR16-073 | 7th May 2016
Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Improved concrete efficiency and security analysis of Reed-Solomon PCPPs

A Probabilistically Checkable Proof of Proximity (PCPP) for a linear code $C$, enables to determine very efficiently if a long input $x$, given as an oracle, belongs to $C$ or is far from $C$.
PCPPs are often a central component of constructions of Probabilistically Checkable Proofs (PCP)s [Babai et al. ... more >>>

TR10-190 | 9th December 2010
Xin Li

Improved Constructions of Three Source Extractors

We study the problem of constructing extractors for independent weak random sources. The probabilistic method shows that there exists an extractor for two independent weak random sources on $n$ bits with only logarithmic min-entropy. However, previously the best known explicit two source extractor only achieves min-entropy $0.499n$ \cite{Bourgain05}, and the ... more >>>

TR15-125 | 5th August 2015
Xin Li

Improved Constructions of Two-Source Extractors

Revisions: 2

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$.

... more >>>

TR18-091 | 4th May 2018
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

Improved decoding of Folded Reed-Solomon and Multiplicity Codes

Revisions: 1

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions ... more >>>

TR98-043 | 27th July 1998

Improved decoding of Reed-Solomon and algebraic-geometric codes.

We present an improved list decoding algorithm for decoding
Reed-Solomon codes. Given an arbitrary string of length n, the
list decoding problem is that of finding all codewords within a
specified Hamming distance from the input string.

It is well-known that this decoding problem for Reed-Solomon
codes reduces to the ... more >>>

TR10-080 | 5th May 2010
Andrew Drucker

Improved Direct Product Theorems for Randomized Query Complexity

Revisions: 1

The direct product problem is a fundamental question in complexity theory which seeks to understand how the difficulty of computing a function on each of $k$ independent inputs scales with $k$.
We prove the following direct product theorem (DPT) for query complexity: if every $T$-query algorithm
has success probability at ... more >>>

TR18-110 | 4th June 2018
Fu Li, David Zuckerman

Improved Extractors for Recognizable and Algebraic Sources

Revisions: 1

We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = v} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources.
Our first method shows that ... more >>>

TR13-076 | 15th May 2013
Divesh Aggarwal, Chandan Dubey

Improved hardness results for unique shortest vector problem

Revisions: 1

We give several improvements on the known hardness of the unique shortest vector problem in lattices, i.e., the problem of finding a shortest vector in a given lattice given a promise that the shortest vector is unique upto a uniqueness factor $\gamma$.
We give a deterministic reduction from the ... more >>>

TR09-107 | 28th October 2009
Kevin Dick, Chris Umans

Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

TR09-099 | 16th October 2009
Venkatesan Guruswami, Ali Kemal Sinop

Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

TR20-048 | 16th April 2020
Shachar Lovett, Raghu Meka, Jiapeng Zhang

Improved lifting theorems via robust sunflowers

Lifting theorems are a generic way to lift lower bounds in query complexity to lower bounds in communication complexity, with applications in diverse areas, such as combinatorial optimization, proof complexity, game theory. Lifting theorems rely on a gadget, where smaller gadgets give stronger lower bounds. However, existing proof techniques are ... more >>>

TR20-168 | 11th November 2020
Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters

Improved List-Decodability of Reed–Solomon Codes via Tree Packings

This paper shows that there exist Reed--Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any $\epsilon\in (0,1]$ there exist RS codes with rate $\Omega(\frac{\epsilon}{\log(1/\epsilon)+1})$ that are list-decodable from radius of ... more >>>

TR97-003 | 29th January 1997

Improved low-degree testing and its applications

NP = PCP(log n, 1) and related results crucially depend upon
the close connection between the probability with which a
function passes a low degree test'' and the distance of
this function to the nearest degree d polynomial. In this
paper we study a test ... more >>>

TR06-017 | 12th January 2006
Toshiya Itoh

\{1,2,...,m\}$of the edge-set of$G$such that all of the induced vertex labels computed as$\sigma_{v\in e}f(e)$are distinct. The minimal number$m$for which this is possible is called the minimal irregularity strength$s_{m}(G)$of$G$. The ... more >>> TR02-053 | 20th July 2002 Lars Engebretsen, Venkatesan Guruswami Is Constraint Satisfaction Over Two Variables Always Easy? By the breakthrough work of Håstad, several constraint satisfaction problems are now known to have the following approximation resistance property: satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin and Max E4-Set Splitting. A notable ... more >>> TR20-051 | 15th April 2020 Rafael Pass, Muthuramakrishnan Venkitasubramaniam Is it Easier to Prove Theorems that are Guaranteed to be True? Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in$\NP$imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that ... more >>> TR20-094 | 24th June 2020 Ronen Shaltiel Is it possible to improve Yao’s XOR lemma using reductions that exploit the efficiency of their oracle? Yao's XOR lemma states that for every function$f:\set{0,1}^k \ar \set{0,1}$, if$f$has hardness$2/3$for$P/poly$(meaning that for every circuit$C$in$P/poly$,$\Pr[C(X)=f(X)] \le 2/3$on a uniform input$X$), then the task of computing$f(X_1) \oplus \ldots \oplus f(X_t)$for sufficiently large$t$has hardness ... more >>> TR11-151 | 9th November 2011 Valentine Kabanets, Osamu Watanabe Is the Valiant-Vazirani Isolation Lemma Improvable? Revisions: 2 The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit$C$on$n$input variables, the procedure outputs a new circuit$C'$on the same$n$input variables with the property that ... more >>> TR15-146 | 7th September 2015 Elette Boyle, Moni Naor Is There an Oblivious RAM Lower Bound? Revisions: 1 An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of ... more >>> TR17-127 | 12th August 2017 Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces Revisions: 1 We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex. More precisely, the property that we need is that every face of the polytope lies in an affine space defined ... more >>> TR16-155 | 10th October 2016 Vaibhav Krishan, Nutan Limaye Isolation Lemma for Directed Reachability and NL vs. L In this work we study the problem of efficiently isolating witnesses for the complexity classes NL and LogCFL, which are two well-studied complexity classes contained in P. We prove that if there is a L/poly randomized procedure with success probability at least 2/3 for isolating an s-t path in a ... more >>> TR10-194 | 9th December 2010 Thanh Minh Hoang Isolation of Matchings via Chinese Remaindering In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT suggested by Agrawal in a CCC'03-paper for testing perfect matchings. We show that ... more >>> TR98-019 | 5th April 1998 Eric Allender, Klaus Reinhardt Isolation, Matching, and Counting We show that the perfect matching problem is in the complexity class SPL (in the nonuniform setting). This provides a better upper bound on the complexity of the matching problem, as well as providing motivation for studying the complexity class SPL. Using similar ... more >>> TR11-137 | 14th October 2011 Vikraman Arvind, Yadu Vasudev Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits Given two$n$-variable boolean functions$f$and$g$, we study the problem of computing an$\varepsilon$-approximate isomorphism between them. I.e.\ a permutation$\pi$of the$n$variables such that$f(x_1,x_2,\ldots,x_n)$and$g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$differ on at most an$\varepsilon$fraction of all boolean inputs$\{0,1\}^n$. We give a randomized$2^{O(\sqrt{n}\log(n)^{O(1)})}$algorithm ... more >>> TR20-174 | 18th November 2020 Hadley Black, Iden Kalemaj, Sofya Raskhodnikova Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions$f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function$f\$ over an arbitrary partially ... more >>>

TR14-104 | 9th August 2014
Atri Rudra, Mary Wootters

It'll probably work out: improved list-decoding through random operations

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code.
The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural ... more >>>

TR06-123 | 15th September 2006
Venkatesan Guruswami, Venkatesan Guruswami

Iterative Decoding of Low-Density Parity Check Codes (A Survey)

Much progress has been made on decoding algorithms for