Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

H
TR18-089 | 27th April 2018
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

Half-duplex communication complexity

Revisions: 6

Suppose Alice and Bob are communicating bits to each other in order to compute some function $f$, but instead of a classical communication channel they have a pair of walkie-talkie devices. They can use some classical communication protocol for $f$ where each round one player sends bit and the other ... more >>>


TR23-011 | 13th February 2023
Mikhail Dektiarev, Nikolay Vereshchagin

Half-duplex communication complexity with adversary? can be less than the classical communication complexity

Half-duplex communication complexity with adversary was defined in [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Half-duplex communication protocols generalize classical protocols defined by Andrew Yao in [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. It has been ... more >>>


TR11-085 | 14th May 2011
Yijia Chen, Joerg Flum, Moritz Müller

Hard instances of algorithms and proof systems

Assuming that the class TAUT of tautologies of propositional logic has no almost optimal algorithm, we show that every algorithm $\mathbb A$ deciding TAUT has a polynomial time computable sequence witnessing that $\mathbb A$ is not almost optimal. The result extends to every $\Pi_t^p$-complete problem with $t\ge 1$; however, we ... more >>>


TR23-213 | 31st December 2023
Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai

Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness

The existence of "unstructured" hard languages in $\text{NP}\cap\text{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\text{P}$ is separated from $\text{NP}\cap\text{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\text{NP}\cap\text{coNP}$ can be constructed in a black-box way ... more >>>


TR20-188 | 12th December 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood

Hard QBFs for Merge Resolution

Revisions: 1

We prove the first proof size lower bounds for the proof system Merge Resolution (MRes [Olaf Beyersdorff et al., 2020]), a refutational proof system for prenex quantified Boolean formulas (QBF) with a CNF matrix. Unlike most QBF resolution systems in the literature, proofs in MRes consist of resolution steps together ... more >>>


TR17-117 | 20th July 2017
Dmitry Itsykson, Alexander Knop

Hard satisfiable formulas for splittings by linear combinations

Itsykson and Sokolov in 2014 introduced the class of DPLL($\oplus$) algorithms that solve Boolean satisfiability problem using the splitting by linear combinations of variables modulo 2. This class extends the class of DPLL algorithms that split by variables. DPLL($\oplus$) algorithms solve in polynomial time systems of linear equations modulo two ... more >>>


TR24-008 | 17th January 2024
Pavel Hrubes

Hard submatrices for non-negative rank and communication complexity }

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always ... more >>>


TR22-153 | 8th November 2022
Eshan Chattopadhyay, Jyun-Jie Liao

Hardness against Linear Branching Programs and More

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once
branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is
a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ... more >>>


TR13-151 | 7th November 2013
Mark Bun, Justin Thaler

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit ... more >>>


TR07-102 | 4th October 2007
Andrej Bogdanov, Muli Safra

Hardness amplification for errorless heuristics

An errorless heuristic is an algorithm that on all inputs returns either the correct answer or the special symbol "I don't know." A central question in average-case complexity is whether every distributional decision problem in NP has an errorless heuristic scheme: This is an algorithm that, for every δ > ... more >>>


TR18-095 | 11th May 2018
Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

Hardness Amplification for Non-Commutative Arithmetic Circuits

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire.

This is part of a recent ... more >>>


TR09-072 | 3rd September 2009
Paul Beame, Trinh Huynh

Hardness Amplification in Proof Complexity

Revisions: 2 , Comments: 2

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>


TR19-125 | 27th August 2019
Elazar Goldenberg, Karthik C. S.

Hardness Amplification of Optimization Problems

In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products.

We say that an optimization problem $\Pi$ is direct product feasible if it is possible to efficiently aggregate any $k$ instances of $\Pi$ and form one large instance ... more >>>


TR07-130 | 3rd December 2007
Ronen Shaltiel, Emanuele Viola

Hardness amplification proofs require majority

Hardness amplification is the fundamental task of
converting a $\delta$-hard function $f : {0,1}^n ->
{0,1}$ into a $(1/2-\eps)$-hard function $Amp(f)$,
where $f$ is $\gamma$-hard if small circuits fail to
compute $f$ on at least a $\gamma$ fraction of the
inputs. Typically, $\eps,\delta$ are small (and
$\delta=2^{-k}$ captures the case ... more >>>


TR05-057 | 19th May 2005
Venkatesan Guruswami, Valentine Kabanets

Hardness amplification via space-efficient direct products

We prove a version of the derandomized Direct Product Lemma for
deterministic space-bounded algorithms. Suppose a Boolean function
$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$
fraction of inputs by any deterministic time $T$ and space $S$
algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step
walks $w=(v_1,\dots, v_t)$ ... more >>>


TR10-031 | 4th March 2010
Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

Hardness and Approximability in Multi-Objective Optimization

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>


TR11-015 | 8th December 2010
Marcel R. Ackermann, Johannes Blömer, Christoph Scholz

Hardness and Non-Approximability of Bregman Clustering Problems

We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>>


TR18-178 | 9th October 2018
Leroy Chew

Hardness and Optimality in QBF Proof Systems Modulo NP

Quantified Boolean Formulas (QBFs) extend propositional formulas with Boolean quantifiers. Working with QBF differs from propositional logic in its quantifier handling, but as propositional satisfiability (SAT) is a subproblem of QBF, all SAT hardness in solving and proof complexity transfers to QBF. This makes it difficult to analyse efforts dealing ... more >>>


TR20-005 | 17th January 2020
Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

We provide a tight characterisation of proof size in resolution for quantified Boolean formulas (QBF) by circuit complexity. Such a characterisation was previously obtained for a hierarchy of QBF Frege systems (Beyersdorff & Pich, LICS 2016), but leaving open the most important case of QBF resolution. Different from the Frege ... more >>>


TR23-181 | 20th November 2023
Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov

Hardness Condensation by Restriction

Can every $n$-bit boolean function with deterministic query complexity $k\ll n$ be restricted to $O(k)$ variables such that the query complexity remains $\Omega(k)$? That is, can query complexity be condensed via restriction? We study such hardness condensation questions in both query and communication complexity, proving two main results.

$\bullet~$ $\mathbf{Negative}$: ... more >>>


TR06-071 | 25th April 2006
John Hitchcock, A. Pavan

Hardness Hypotheses, Derandomization, and Circuit Complexity

We consider hypotheses about nondeterministic computation that
have been studied in different contexts and shown to have interesting
consequences:

1. The measure hypothesis: NP does not have p-measure 0.

2. The pseudo-NP hypothesis: there is an NP language that can be
distinguished from any DTIME(2^n^epsilon) language by an ... more >>>


TR19-118 | 5th September 2019
Lijie Chen, Ce Jin, Ryan Williams

Hardness Magnification for all Sparse NP Languages

In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of ... more >>>


TR18-139 | 10th August 2018
Igor Carboni Oliveira, Rahul Santhanam

Hardness Magnification for Natural Problems

We show that for several natural problems of interest, complexity lower bounds that are barely non-trivial imply super-polynomial or even exponential lower bounds in strong computational models. We term this phenomenon "hardness magnification". Our examples of hardness magnification include:

1. Let MCSP$[s]$ be the decision problem whose YES instances are ... more >>>


TR18-158 | 11th September 2018
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Hardness magnification near state-of-the-art lower bounds

Revisions: 1

This work continues the development of hardness magnification. The latter proposes a strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful.

We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs ... more >>>


TR09-112 | 3rd November 2009
Davide Bilò, Luciano Gualà, Guido Proietti

Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game

Consider a communication network represented by a directed graph $G=(V,E)$ of $n$ nodes and $m$ edges. Assume that edges in $E$ are
partitioned into two sets: a set $C$ of edges with a fixed
non-negative real cost, and a set $P$ of edges whose \emph{price} should instead be set by ... more >>>


TR00-062 | 25th August 2000
Venkatesan Guruswami, Johan Håstad, Madhu Sudan

Hardness of approximate hypergraph coloring

We introduce the notion of covering complexity of a probabilistic
verifier. The covering complexity of a verifier on a given input is
the minimum number of proofs needed to ``satisfy'' the verifier on
every random string, i.e., on every random string, at least one of the
given proofs must be ... more >>>


TR05-127 | 5th November 2005
Vitaly Feldman

Hardness of Approximate Two-level Logic Minimization and PAC Learning with Membership Queries

Revisions: 1

Producing a small DNF expression consistent with given data is a
classical problem in computer science that occurs in a number of forms and
has numerous applications. We consider two standard variants of this
problem. The first one is two-level logic minimization or finding a minimal
more >>>


TR10-053 | 28th March 2010
Dana Moshkovitz, Subhash Khot

Hardness of Approximately Solving Linear Equations Over Reals

Comments: 1

In this paper, we consider the problem of approximately solving a
system of homogeneous linear equations over reals, where each
equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations
exactly, we restrict the assignments to be ``non-trivial". Here is
an informal statement of our ... more >>>


TR99-029 | 31st August 1999
Ilya Dumer, Daniele Micciancio, Madhu Sudan

Hardness of approximating the minimum distance of a linear code

We show that the minimum distance of a linear code (or
equivalently, the weight of the lightest codeword) is
not approximable to within any constant factor in random polynomial
time (RP), unless NP equals RP.
Under the stronger assumption that NP is not contained in RQP
(random ... more >>>


TR06-019 | 24th November 2005
Janka Chlebíková, Miroslav Chlebik

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering problems even if rotations by ninety
more >>>


TR14-051 | 12th April 2014
Subhash Khot, Rishi Saket

Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

We show that it is quasi-NP-hard to color $2$-colorable $12$-uniform hypergraphs with $2^{(\log n)^{\Omega(1) }}$ colors where $n$ is the number of vertices. Previously, Guruswami et al. [GHHSV14] showed that it is quasi-NP-hard to color $2$-colorable $8$-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors. Their result is obtained by composing a ... more >>>


TR21-030 | 2nd March 2021
Shuichi Hirahara, Rahul Ilango, Bruno Loff

Hardness of Constant-round Communication Complexity

How difficult is it to compute the communication complexity of a two-argument total Boolean function $f:[N]\times[N]\to\{0,1\}$, when it is given as an $N\times N$ binary matrix? In 2009, Kushilevitz and Weinreb showed that this problem is cryptographically hard, but it is still open whether it is NP-hard.

In this ... more >>>


TR16-063 | 18th April 2016
Pavel Hubacek, Eylon Yogev

Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Revisions: 1

Local search proved to be an extremely useful tool when facing hard optimization problems (e.g. via the simplex algorithm, simulated annealing, or genetic algorithms). Although powerful, it has its limitations: there are functions for which exponentially many queries are needed to find a local optimum. In many contexts the optimization ... more >>>


TR06-109 | 29th August 2006
Julia Chuzhoy, Sanjeev Khanna

Hardness of Directed Routing with Congestion

Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the ... more >>>


TR18-118 | 20th June 2018
Alexander Durgin, Brendan Juba

Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs

We consider several closely related variants of PAC-learning in which false-positive and false-negative errors are treated differently. In these models we seek to guarantee a given, low rate of false-positive errors and as few false-negative errors as possible given that we meet the false-positive constraint. Bshouty and Burroughs first observed ... more >>>


TR21-057 | 23rd April 2021
Hanlin Ren, Rahul Santhanam

Hardness of KT Characterizes Parallel Cryptography

Revisions: 1

A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity K^t is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures:

1. We show, perhaps surprisingly, that the ... more >>>


TR19-161 | 13th November 2019
Suprovat Ghoshal, Rishi Saket

Hardness of Learning DNFs using Halfspaces

The problem of learning $t$-term DNF formulas (for $t = O(1)$) has been studied extensively in the PAC model since its introduction by Valiant (STOC 1984). A $t$-term DNF can be efficiently learnt using a $t$-term DNF only if $t = 1$ i.e., when it is an AND, while even ... more >>>


TR06-061 | 5th May 2006
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Learning Halfspaces with Noise

Learning an unknown halfspace (also called a perceptron) from
labeled examples is one of the classic problems in machine learning.
In the noise-free case, when a halfspace consistent with all the
training examples exists, the problem can be solved in polynomial
time using linear programming. ... more >>>


TR17-115 | 5th July 2017
Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

Hardness of learning noisy halfspaces using polynomial thresholds

We prove the hardness of weakly learning halfspaces in the presence of adversarial noise using polynomial threshold functions (PTFs). In particular, we prove that for any constants $d \in \mathbb{Z}^+$ and $\epsilon > 0$, it is NP-hard to decide: given a set of $\{-1,1\}$-labeled points in $\mathbb{R}^n$ whether (YES Case) ... more >>>


TR06-141 | 22nd November 2006
Venkatesan Guruswami, Kunal Talwar

Hardness of Low Congestion Routing in Directed Graphs

We prove a strong inapproximability result for routing on directed
graphs with low congestion. Given as input a directed graph on $N$
vertices and a set of source-destination pairs that can be connected
via edge-disjoint paths, we prove that it is hard, assuming NP
doesn't have $n^{O(\log\log n)}$ time randomized ... more >>>


TR22-083 | 2nd June 2022
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Hardness of Maximum Likelihood Learning of DPPs

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fitted to match the data; typically, we ... more >>>


TR10-059 | 8th April 2010
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

Hardness of Parameterized Resolution

Parameterized Resolution and, moreover, a general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that paper, Dantchev et al. show a complexity gap in tree-like Parameterized Resolution for propositional formulas arising from translations of first-order principles.
We broadly investigate Parameterized Resolution obtaining the following ... more >>>


TR17-147 | 3rd October 2017
Venkatesan Guruswami, Rishi Saket

Hardness of Rainbow Coloring Hypergraphs

A hypergraph is $k$-rainbow colorable if there exists a vertex coloring using $k$ colors such that each hyperedge has all the $k$ colors. Unlike usual hypergraph coloring, rainbow coloring becomes harder as the number of colors increases. This work studies the rainbow colorability of hypergraphs which are guaranteed to be ... more >>>


TR23-206 | 9th December 2023
Yilei Chen, Jiatu Li

Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography

A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. Avoid) and the remote point problem (abbrev. RPP). The upper and lower bounds for these meta problems provide a unified ... more >>>


TR07-073 | 3rd August 2007
Parikshit Gopalan, Subhash Khot, Rishi Saket

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

We study the polynomial reconstruction problem for low-degree
multivariate polynomials over finite fields. In the GF[2] version of this problem, we are given a set of points on the hypercube and target values $f(x)$ for each of these points, with the promise that there is a polynomial over GF[2] of ... more >>>


TR09-020 | 2nd March 2009
Venkatesan Guruswami, Prasad Raghavendra

Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>


TR21-082 | 16th June 2021
Rahul Ilango, Hanlin Ren, Rahul Santhanam

Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity

We show that one-way functions exist if and only if there is some samplable distribution D such that it is hard to approximate the Kolmogorov complexity of a string sampled from D. Thus we characterize the existence of one-way functions by the average-case hardness of a natural \emph{uncomputable} problem on ... more >>>


TR12-182 | 24th December 2012
Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

A common method for increasing the usability and uplifting the security of pseudorandom function families (PRFs) is to ``hash" the inputs into a smaller domain before applying the PRF. This approach, known as ``Levin's trick", is used to achieve ``PRF domain extension" (using a short, e.g., fixed, input length PRF ... more >>>


TR22-108 | 18th July 2022
Shuichi Hirahara, Nobutaka Shimizu

Hardness Self-Amplification from Feasible Hard-Core Sets

We consider the question of hardness self-amplification: Given a Boolean function $f$ that is hard to compute on a $o(1)$-fraction of inputs drawn from some distribution, can we prove that $f$ is hard to compute on a $(\frac{1}{2} - o(1))$-fraction of inputs drawn from the same distribution? We prove hardness ... more >>>


TR23-026 | 15th March 2023
Shuichi Hirahara, Nobutaka Shimizu

Hardness Self-Amplification: Simplified, Optimized, and Unified

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove ... more >>>


TR21-080 | 10th June 2021
Lijie Chen, Roei Tell

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

We propose a new approach to the hardness-to-randomness framework and to the promise-BPP=promise-P conjecture. Classical results rely on non-uniform hardness assumptions to construct derandomization algorithms that work in the worst-case, or rely on uniform hardness assumptions to construct derandomization algorithms that work only in the average-case. In both types of ... more >>>


TR07-121 | 21st November 2007
Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... more >>>


TR04-072 | 19th August 2004
John Hitchcock

Hausdorff Dimension and Oracle Constructions

Bennett and Gill (1981) proved that P^A != NP^A relative to a
random oracle A, or in other words, that the set
O_[P=NP] = { A | P^A = NP^A }
has Lebesgue measure 0. In contrast, we show that O_[P=NP] has
Hausdorff dimension 1.

... more >>>


TR23-090 | 15th June 2023
Itay Cohen, Roy Roth, Amnon Ta-Shma

HDX Condensers

More than twenty years ago, Capalbo, Reingold, Vadhan and Wigderson gave the first (and up to date only) explicit construction of a bipartite expander with almost full combinatorial expansion. The construction incorporates zig-zag ideas together with extractor technology, and is rather complicated. We give an alternative construction that builds upon ... more >>>


TR03-034 | 17th March 2003
Arnold Beckmann

Height restricted constant depth LK

Height restricted constant depth LK is a natural restriction of
Gentzen's propositional proof system LK. A sequence of LK-formulas
has polylogarithmic-height restricted depth-d-LK proofs iff the
n-th formula in the sequence possesses LK-proofs where cut-formulas
are of depth d+1 with small bottom fanin
and of ... more >>>


TR13-074 | 9th May 2013
Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

Helly Circular-Arc Graph Isomorphism is in Logspace

We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices ... more >>>


TR14-178 | 5th December 2014
Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

Heuristic time hierarchies via hierarchies for sampling distributions

We give a new simple proof of the time hierarchy theorem for heuristic BPP originally proved by Fortnow and Santhanam [FS04] and then simplified and improved by Pervyshev [P07]. In the proof we use a hierarchy theorem for sampling distributions recently proved by Watson [W13]. As a byproduct we get ... more >>>


TR14-171 | 11th December 2014
Lance Fortnow, Rahul Santhanam

Hierarchies Against Sublinear Advice

We strengthen the non-deterministic time hierarchy theorem of
\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound
holds against sublinear advice. More formally, we show that for any constants
$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$
which is not in $\NTIME(n^c)/n^{1/d}$. ... more >>>


TR08-097 | 14th November 2008
Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

Hierarchy Theorems for Property Testing

Revisions: 1

Referring to the query complexity of property testing,
we prove the existence of a rich hierarchy of corresponding
complexity classes. That is, for any relevant function $q$,
we prove the existence of properties that have testing
complexity Theta(q).
Such results are proven in three standard
domains often considered in property ... more >>>


TR18-098 | 17th May 2018
Oded Goldreich

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

Revisions: 1

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes.
That is, for essentially any function $q:(0,1]\to\N$, we prove the existence ... more >>>


TR17-157 | 13th October 2017
Monaldo Mastrolilli

High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts

Revisions: 2

Chvatal-Gomory (CG) cuts and the Bienstock-Zuckerberg hierarchy capture useful linear programs that the standard bounded degree Lasserre/Sum-of-Squares (SOS) hierarchy fails to capture.

In this paper we present a novel polynomial time SOS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low-degree ... more >>>


TR17-089 | 11th May 2017
Irit Dinur, Tali Kaufman

High dimensional expanders imply agreement expanders

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is *linear* in the size of the universe.

Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree ... more >>>


TR20-170 | 9th November 2020
Max Hopkins, Tali Kaufman, Shachar Lovett

High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

Revisions: 1

Higher order random walks (HD-walks) on high dimensional expanders have played a crucial role in a number of recent breakthroughs in theoretical computer science, perhaps most famously in the recent resolution of the Mihail-Vazirani conjecture (Anari et al. STOC 2019), which focuses on HD-walks on one-sided local-spectral expanders. In this ... more >>>


TR13-053 | 4th April 2013
Alan Guo

High rate locally correctable codes via lifting

Revisions: 1

We present a general framework for constructing high rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes of Guo, Kopparty, ... more >>>


TR15-068 | 21st April 2015
Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 3

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>


TR20-162 | 7th November 2020
Dean Doron, Mary Wootters

High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 3

An error correcting code $\mathcal{C} \colon \Sigma^k \to \Sigma^n$ is list-recoverable from input list size $\ell$ if for any sets $\mathcal{L}_1, \ldots, \mathcal{L}_n \subseteq \Sigma$ of size at most $\ell$, one can efficiently recover the list $\mathcal{L} = \{ x \in \Sigma^k : \forall j \in [n], \mathcal{C}(x)_j \in \mathcal{L}_j ... more >>>


TR10-148 | 23rd September 2010
Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

High-rate codes with sublinear-time decoding

Locally decodable codes are error-correcting codes that admit efficient decoding algorithms; any bit of the original message can be recovered by looking at only a small number of locations of a corrupted codeword. The tradeoff between the rate of a code and the locality/efficiency of its decoding algorithms has been ... more >>>


TR15-110 | 8th July 2015
Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

An error correcting code is said to be \emph{locally testable} if
there is a test that checks whether a given string is a codeword,
or rather far from the code, by reading only a small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their ... more >>>


TR10-181 | 21st November 2010
Hamed Hatami, Shachar Lovett

Higher-order Fourier analysis of $\mathbb{F}_p^n$ and the complexity of systems of linear forms

In this article we are interested in the density of small linear structures (e.g. arithmetic progressions) in subsets $A$ of the group $\mathbb{F}_p^n$. It is possible to express these densities as certain analytic averages involving $1_A$, the indicator function of $A$. In the higher-order Fourier analytic approach, the function $1_A$ ... more >>>


TR96-055 | 22nd October 1996
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting Properties of Hard Boolean Operators and their Consequences on BPP

Revisions: 1 , Comments: 1

We present the first worst-case hardness conditions
on the circuit complexity of EXP functions which are
sufficient to obtain P=BPP. In particular, we show that
from such hardness conditions it is possible to construct
quick Hitting Sets Generators with logarithmic prize.
... more >>>


TR21-014 | 15th February 2021
Dori Medini, Amir Shpilka

Hitting Sets and Reconstruction for Dense Orbits in VP$_e$ and $\Sigma\Pi\Sigma$ Circuits

In this paper we study polynomials in VP$_e$ (polynomial-sized formulas) and in $\Sigma\Pi\Sigma$ (polynomial-size depth-$3$ circuits) whose orbits, under the action of the affine group GL$^{aff}_n({\mathbb F})$, are dense in their ambient class. We construct hitting sets and interpolating sets for these orbits as well as give reconstruction algorithms.

As ... more >>>


TR95-061 | 27th November 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting sets derandomize BPP

Revisions: 1

We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the ... more >>>


TR13-175 | 6th December 2013
Venkatesan Guruswami, Chaoping Xing

Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>


TR21-015 | 15th February 2021
Chandan Saha, Bhargav Thankey

Hitting Sets for Orbits of Circuit Classes and Polynomial Families

Revisions: 2

The orbit of an $n$-variate polynomial $f(\mathbf{x})$ over a field $\mathbb{F}$ is the set $\mathrm{orb}(f) := \{f(A\mathbf{x}+\mathbf{b}) : A \in \mathrm{GL}(n,\mathbb{F}) \ \mathrm{and} \ \mathbf{b} \in \mathbb{F}^n\}$. This paper studies explicit hitting sets for the orbits of polynomials computable by certain well-studied circuit classes. This version of the hitting set ... more >>>


TR21-143 | 13th October 2021
Edward Pyne

Hitting Sets For Regular Branching Programs

Revisions: 2

We construct an explicit $\varepsilon$-hitting set generator (HSG) for regular ordered branching programs of length $n$ and $\textit{unbounded width}$ with a single accept state that has seed length
\[O(\log(n)(\log\log(n)+\log(1/\varepsilon))).\]
Previously, the best known seed length for regular branching programs of width $w$ with a single accept state was ... more >>>


TR20-016 | 17th February 2020
Kuan Cheng, William Hoza

Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

A hitting set is a "one-sided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have one-sided error. We study the problem of using a given hitting set to derandomize algorithms that have two-sided error, focusing on space-bounded algorithms. For our first result, we show that if ... more >>>


TR17-161 | 30th October 2017
Mark Braverman, Gil Cohen, Sumegha Garg

Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

Revisions: 1

Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2{n} + \log{n} \cdot \log(1/\varepsilon))$. A major goal in complexity theory is to reduce the seed length, hopefully, to the optimal $O(\log{n}+\log(1/\varepsilon))$, or to construct improved hitting sets, as ... more >>>


TR13-174 | 6th December 2013
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Hitting-sets for low-distance multilinear depth-$3$

The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>>


TR14-085 | 29th June 2014
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>


TR05-099 | 9th September 2005
Leslie G. Valiant

Holographic Algorithms

Complexity theory is built fundamentally on the notion of efficient
reduction among computational problems. Classical
reductions involve gadgets that map solution fragments of one problem to
solution fragments of another in one-to-one, or
possibly one-to-many, fashion. In this paper we propose a new kind of
reduction that allows for gadgets ... more >>>


TR06-145 | 1st December 2006
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: From Art to Science

We develop the theory of holographic algorithms. We give
characterizations of algebraic varieties of realizable
symmetric generators and recognizers on the basis manifold,
and a polynomial time decision algorithm for the
simultaneous realizability problem.
Using the general machinery we are able to give
unexpected holographic algorithms for
some counting problems, ... more >>>


TR07-020 | 11th March 2007
Jin-Yi Cai, Pinyan Lu

Holographic Algorithms: The Power of Dimensionality Resolved

Valiant's theory of holographic algorithms is a novel methodology
to achieve exponential speed-ups in computation. A fundamental
parameter in holographic algorithms is the dimension of the linear basis
vectors.
We completely resolve the problem of the power of higher dimensional
bases. We prove that 2-dimensional bases are universal for
holographic ... more >>>


TR10-146 | 21st September 2010
Ron Rothblum

Homomorphic Encryption: from Private-Key to Public-Key

We show that any private-key encryption scheme that is weakly
homomorphic with respect to addition modulo 2, can be transformed
into a public-key encryption scheme. The homomorphic feature
referred to is a minimalistic one; that is, the length of a
homomorphically generated encryption should be independent of the
number of ... more >>>


TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>


TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

Homomorphisms in Graph Property Testing - A Survey

Property-testers are fast randomized algorithms for distinguishing
between graphs (and other combinatorial structures) satisfying a
certain property, from those that are far from satisfying it. In
many cases one can design property-testers whose running time is in
fact {\em independent} of the size of the input. In this paper we
more >>>


TR21-006 | 18th January 2021
Susanna de Rezende, Jakob Nordström, Marc Vinyals

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large ... more >>>


TR11-088 | 7th June 2011
Pavel Hrubes

How much commutativity is needed to prove polynomial identities?

Let $f$ be a non-commutative polynomial such that $f=0$ if we assume that the variables in $f$ commute. Let $Q(f)$ be the smallest $k$ such that there exist polynomials $g_1,g_1', g_2, g_2',\dots, g_k, g_k' $ with \[f\in I([g_1,g_1'], [g_2, g_2'],\dots, [g_k, g_k'] )\,,\]
where $[g,h]=gh-hg$. Then $Q(f)\leq {n\choose 2}$, where ... more >>>


TR22-060 | 27th April 2022
Nikolay Vereshchagin

How much randomness is needed to convert MA protocols to AM protocols?

The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The ... more >>>


TR12-167 | 16th November 2012
Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

How powerful are the DDH hard groups?

The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure ... more >>>


TR19-157 | 25th September 2019
Leroy Chew, Judith Clymo

How QBF Expansion Makes Strategy Extraction Hard

In this paper we show that the QBF proof checking format QRAT (Quantified Resolution Asymmetric Tautologies) by Heule, Biere and Seidl cannot have polynomial-time strategy extraction unless P=PSPACE. In our proof, the crucial property that makes strategy extraction PSPACE-hard for this proof format is universal expansion, even expansion on a ... more >>>


TR17-100 | 7th June 2017
Dakshita Khurana, Amit Sahai

How to Achieve Non-Malleability in One or Two Rounds

Despite over 25 years of research on non-malleable commitments in the plain model, their round complexity has remained open. The goal of achieving non-malleable commitment protocols with only one or two rounds has been especially elusive. Pass (TCC 2013, CC 2016) captured this difficulty by proving important impossibility results regarding ... more >>>


TR09-132 | 8th December 2009
Lior Malka

How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge

Perfect zero-knowledge (PZK) proofs have been constructed in various settings and they are
also interesting from a complexity theoretic perspective. Yet, virtually nothing is known about them. This is in contrast to statistical zero-knowledge proofs, where many general results have been proved using an array of tools, none of which ... more >>>


TR15-055 | 13th April 2015
Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

How to Compress Asymmetric Communication

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If $I^A$ denotes the number of bits of information revealed by the first party, $I^B$ denotes the information revealed by the second party, and $C$ is the number of bits of communication in ... more >>>


TR12-010 | 5th February 2012
Shafi Goldwasser, Guy Rothblum

How to Compute in the Presence of Leakage

We address the following problem: how to execute any algorithm P, for an unbounded number of executions, in the presence of an adversary who observes partial information on the internal state of the computation during executions. The security guarantee is that the adversary learns nothing, beyond P's input/output behavior.

This ... more >>>


TR12-140 | 27th October 2012
Mark Zhandry

How to Construct Quantum Random Functions

Revisions: 2

In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on ... more >>>


TR13-183 | 22nd December 2013
Yael Tauman Kalai, Ran Raz, Ron Rothblum

How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>>


TR21-120 | 18th August 2021
Roei Tell

How to Find Water in the Ocean: A Survey on Quantified Derandomization

The focus of this survey is the question of *quantified derandomization*, which was introduced by Goldreich and Wigderson (2014): Does derandomization of probabilistic algorithms become easier if we only want to derandomize algorithms that err with extremely small probability? How small does this probability need to be in order for ... more >>>


TR12-058 | 5th May 2012
Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

How to Garble Arithmetic Circuits

Revisions: 1

Yao's garbled circuit construction transforms a boolean circuit $C:\{0,1\}^n\to\{0,1\}^m$
into a ``garbled circuit'' $\hat{C}$ along with $n$ pairs of $k$-bit keys, one for each
input bit, such that $\hat{C}$ together with the $n$ keys
corresponding to an input $x$ reveal $C(x)$ and no additional information about $x$.
The garbled circuit ... more >>>


TR05-145 | 5th December 2005
Ronen Shaltiel

How to get more mileage from randomness extractors

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>


TR05-096 | 26th August 2005
Boaz Barak, Amit Sahai

How To Play Almost Any Mental Game Over The Net --- Concurrent Composition via Super-Polynomial Simulation

We construct a secure protocol for any multi-party functionality
that remains secure (under a relaxed definition of security) when
executed concurrently with multiple copies of itself and other
protocols. We stress that we do *not* use any assumptions on
existence of trusted parties, common reference string, honest
majority or synchronicity ... more >>>


TR09-021 | 2nd March 2009
Konstantin Makarychev, Yury Makarychev

How to Play Unique Games on Expanders

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>


TR06-144 | 21st November 2006
Claire Kenyon-Mathieu, Warren Schudy

How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments

Suppose you ran a chess tournament, everybody played everybody, and you wanted to use the results to rank everybody. Unless you were really lucky, the results would not be acyclic, so you could not just sort the players by who beat whom. A natural objective is to find a ranking ... more >>>


TR23-087 | 9th June 2023
Benny Applebaum, Oded Nir, Benny Pinkas

How to Recover a Secret with $O(n)$ Additions

Revisions: 1

Threshold cryptography is typically based on the idea of secret-sharing a private-key $s\in F$ ``in the exponent'' of some cryptographic group $G$, or more generally, encoding $s$ in some linearly homomorphic domain. In each invocation of the threshold system (e.g., for signing or decrypting) an ``encoding'' of the secret is ... more >>>


TR16-023 | 23rd February 2016
Ilan Komargodski, Moni Naor, Eylon Yogev

How to Share a Secret, Infinitely

Revisions: 4

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties so that any qualified subset of parties can reconstruct the secret, while every unqualified subset of parties learns nothing about the secret. The collection of qualified subsets is called an access structure. The best ... more >>>


TR17-112 | 27th June 2017
Yehuda Lindell

How To Simulate It -- A Tutorial on the Simulation Proof Technique

One of the most fundamental notions of cryptography is that of \emph{simulation}. It stands behind the concepts of semantic security, zero knowledge, and security for multiparty computation. However, writing a simulator and proving security via the use of simulation is a non-trivial task, and one that many newcomers to the ... more >>>


TR06-025 | 19th January 2006
Leonid Gurvits

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\\ Sharper Bounds , Simpler Proofs and Algorithmic Applications

Let $p(x_1,...,x_n) = p(X) , X \in R^{n}$ be a homogeneous polynomial of degree $n$ in $n$ real variables ,
$e = (1,1,..,1) \in R^n$ be a vector of all ones . Such polynomial $p$ is
called $e$-hyperbolic if for all real vectors $X \in R^{n}$ the univariate polynomial
equation ... more >>>


TR21-169 | 24th November 2021
Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>


TR21-168 | 17th November 2021
Tom Gur, Noam Lifshitz, Siqi Liu

Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for $\epsilon$-Product Spaces

Revisions: 2

We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we ... more >>>




ISSN 1433-8092 | Imprint