Under the auspices of the Computational Complexity Foundation (CCF)

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

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

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

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

#### Hard QBFs for Merge Resolution

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

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 &delta; > ... 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Revisions: 1

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

ISSN 1433-8092 | Imprint