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

__
TR11-085
| 14th May 2011
__

Yijia Chen, Joerg Flum, Moritz Müller#### Hard instances of algorithms and proof systems

__
TR20-188
| 12th December 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood#### Hard QBFs for Merge Resolution

__
TR17-117
| 20th July 2017
__

Dmitry Itsykson, Alexander Knop#### Hard satisfiable formulas for splittings by linear combinations

__
TR13-151
| 7th November 2013
__

Mark Bun, Justin Thaler#### Hardness Amplification and the Approximate Degree of Constant-Depth Circuits

Revisions: 3

__
TR07-102
| 4th October 2007
__

Andrej Bogdanov, Muli Safra#### Hardness amplification for errorless heuristics

__
TR18-095
| 11th May 2018
__

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin#### Hardness Amplification for Non-Commutative Arithmetic Circuits

__
TR09-072
| 3rd September 2009
__

Paul Beame, Trinh Huynh#### Hardness Amplification in Proof Complexity

Revisions: 2
,
Comments: 2

__
TR19-125
| 27th August 2019
__

Elazar Goldenberg, Karthik C. S.#### Hardness Amplification of Optimization Problems

__
TR07-130
| 3rd December 2007
__

Ronen Shaltiel, Emanuele Viola#### Hardness amplification proofs require majority

__
TR05-057
| 19th May 2005
__

Venkatesan Guruswami, Valentine Kabanets#### Hardness amplification via space-efficient direct products

__
TR10-031
| 4th March 2010
__

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek#### Hardness and Approximability in Multi-Objective Optimization

__
TR11-015
| 8th December 2010
__

Marcel R. Ackermann, Johannes Blömer, Christoph Scholz#### Hardness and Non-Approximability of Bregman Clustering Problems

__
TR18-178
| 9th October 2018
__

Leroy Chew#### Hardness and Optimality in QBF Proof Systems Modulo NP

__
TR20-005
| 17th January 2020
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

Revisions: 1

__
TR06-071
| 25th April 2006
__

John Hitchcock, A. Pavan#### Hardness Hypotheses, Derandomization, and Circuit Complexity

__
TR19-118
| 5th September 2019
__

Lijie Chen, Ce Jin, Ryan Williams#### Hardness Magnification for all Sparse NP Languages

__
TR18-139
| 10th August 2018
__

Igor Carboni Oliveira, Rahul Santhanam#### Hardness Magnification for Natural Problems

__
TR18-158
| 11th September 2018
__

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam#### Hardness magnification near state-of-the-art lower bounds

Revisions: 1

__
TR09-112
| 3rd November 2009
__

Davide Bilò, Luciano Gualà, Guido Proietti#### Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game

__
TR00-062
| 25th August 2000
__

Venkatesan Guruswami, Johan Håstad, Madhu Sudan#### Hardness of approximate hypergraph coloring

__
TR05-127
| 5th November 2005
__

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

Revisions: 1

__
TR10-053
| 28th March 2010
__

Dana Moshkovitz, Subhash Khot#### Hardness of Approximately Solving Linear Equations Over Reals

Comments: 1

__
TR99-029
| 31st August 1999
__

Ilya Dumer, Daniele Micciancio, Madhu Sudan#### Hardness of approximating the minimum distance of a linear code

__
TR06-019
| 24th November 2005
__

Janka Chlebíková, Miroslav Chlebik#### Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

__
TR14-051
| 12th April 2014
__

Subhash Khot, Rishi Saket#### Hardness of Coloring $2$-Colorable $12$-Uniform Hypergraphs with $2^{(\log n)^{\Omega(1)}}$ Colors

__
TR16-063
| 18th April 2016
__

Pavel Hubacek, Eylon Yogev#### Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Revisions: 1

__
TR06-109
| 29th August 2006
__

Julia Chuzhoy, Sanjeev Khanna#### Hardness of Directed Routing with Congestion

__
TR18-118
| 20th June 2018
__

Alexander Durgin, Brendan Juba#### Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs

__
TR19-161
| 13th November 2019
__

Suprovat Ghoshal, Rishi Saket#### Hardness of Learning DNFs using Halfspaces

__
TR06-061
| 5th May 2006
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Learning Halfspaces with Noise

__
TR17-115
| 5th July 2017
__

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket#### Hardness of learning noisy halfspaces using polynomial thresholds

__
TR06-141
| 22nd November 2006
__

Venkatesan Guruswami, Kunal Talwar#### Hardness of Low Congestion Routing in Directed Graphs

__
TR10-059
| 8th April 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### Hardness of Parameterized Resolution

__
TR17-147
| 3rd October 2017
__

Venkatesan Guruswami, Rishi Saket#### Hardness of Rainbow Coloring Hypergraphs

__
TR07-073
| 3rd August 2007
__

Parikshit Gopalan, Subhash Khot, Rishi Saket#### Hardness of Reconstructing Multivariate Polynomials over Finite Fields

__
TR09-020
| 2nd March 2009
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

__
TR12-182
| 24th December 2012
__

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor#### Hardness Preserving Reductions via Cuckoo Hashing

Revisions: 2

__
TR07-121
| 21st November 2007
__

Zeev Dvir, Amir Shpilka, Amir Yehudayoff#### Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

__
TR04-072
| 19th August 2004
__

John Hitchcock#### Hausdorff Dimension and Oracle Constructions

__
TR03-034
| 17th March 2003
__

Arnold Beckmann#### Height restricted constant depth LK

__
TR13-074
| 9th May 2013
__

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky#### Helly Circular-Arc Graph Isomorphism is in Logspace

__
TR14-178
| 5th December 2014
__

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Heuristic time hierarchies via hierarchies for sampling distributions

__
TR14-171
| 11th December 2014
__

Lance Fortnow, Rahul Santhanam#### Hierarchies Against Sublinear Advice

__
TR08-097
| 14th November 2008
__

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg#### Hierarchy Theorems for Property Testing

Revisions: 1

__
TR18-098
| 17th May 2018
__

Oded Goldreich#### Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity

Revisions: 1

__
TR17-157
| 13th October 2017
__

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

Revisions: 2

__
TR17-089
| 11th May 2017
__

Irit Dinur, Tali Kaufman#### High dimensional expanders imply agreement expanders

__
TR20-170
| 9th November 2020
__

Max Hopkins, Tali Kaufman, Shachar Lovett#### High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games

__
TR13-053
| 4th April 2013
__

Alan Guo#### High rate locally correctable codes via lifting

Revisions: 1

__
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

__
TR20-162
| 7th November 2020
__

Dean Doron, Mary Wootters#### High-Probability List-Recovery, and Applications to Heavy Hitters

Revisions: 1

__
TR10-148
| 23rd September 2010
__

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin#### High-rate codes with sublinear-time decoding

__
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

__
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

__
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

__
TR95-061
| 27th November 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Hitting sets derandomize BPP

Revisions: 1

__
TR13-175
| 6th December 2013
__

Venkatesan Guruswami, Chaoping Xing#### Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

__
TR20-016
| 17th February 2020
__

Kuan Cheng, William Hoza#### Hitting Sets Give Two-Sided Derandomization of Small Space

Revisions: 1

__
TR17-161
| 30th October 2017
__

Mark Braverman, Gil Cohen, Sumegha Garg#### Hitting Sets with Near-Optimal Error for Read-Once Branching Programs

Revisions: 1

__
TR13-174
| 6th December 2013
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for low-distance multilinear depth-$3$

__
TR14-085
| 29th June 2014
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

__
TR05-099
| 9th September 2005
__

Leslie G. Valiant#### Holographic Algorithms

__
TR06-145
| 1st December 2006
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: From Art to Science

__
TR07-020
| 11th March 2007
__

Jin-Yi Cai, Pinyan Lu#### Holographic Algorithms: The Power of Dimensionality Resolved

__
TR10-146
| 21st September 2010
__

Ron Rothblum#### Homomorphic Encryption: from Private-Key to Public-Key

__
TR14-163
| 29th November 2014
__

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh#### Homomorphism polynomials complete for VP

__
TR05-085
| 5th August 2005
__

Asaf Shapira, Noga Alon#### Homomorphisms in Graph Property Testing - A Survey

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

__
TR11-088
| 7th June 2011
__

Pavel Hrubes#### How much commutativity is needed to prove polynomial identities?

__
TR12-167
| 16th November 2012
__

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis#### How powerful are the DDH hard groups?

__
TR19-157
| 25th September 2019
__

Leroy Chew, Judith Clymo#### How QBF Expansion Makes Strategy Extraction Hard

__
TR17-100
| 7th June 2017
__

Dakshita Khurana, Amit Sahai#### How to Achieve Non-Malleability in One or Two Rounds

__
TR09-132
| 8th December 2009
__

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

__
TR15-055
| 13th April 2015
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### How to Compress Asymmetric Communication

__
TR12-010
| 5th February 2012
__

Shafi Goldwasser, Guy Rothblum#### How to Compute in the Presence of Leakage

__
TR12-140
| 27th October 2012
__

Mark Zhandry#### How to Construct Quantum Random Functions

Revisions: 2

__
TR13-183
| 22nd December 2013
__

Yael Tauman Kalai, Ran Raz, Ron Rothblum#### How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

__
TR12-058
| 5th May 2012
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### How to Garble Arithmetic Circuits

Revisions: 1

__
TR05-145
| 5th December 2005
__

Ronen Shaltiel#### How to get more mileage from randomness extractors

__
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

__
TR09-021
| 2nd March 2009
__

Konstantin Makarychev, Yury Makarychev#### How to Play Unique Games on Expanders

__
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

__
TR16-023
| 23rd February 2016
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### How to Share a Secret, Infinitely

Revisions: 4

__
TR17-112
| 27th June 2017
__

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

__
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

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal

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

Yijia Chen, Joerg Flum, Moritz Müller

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

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomáš Peitl, Gaurav Sood

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

Dmitry Itsykson, Alexander Knop

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

Mark Bun, Justin Thaler

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

Andrej Bogdanov, Muli Safra

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

Marco Carmosino, Russell Impagliazzo, Shachar Lovett, Ivan Mihajlin

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

Paul Beame, Trinh Huynh

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

Elazar Goldenberg, Karthik C. S.

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

Ronen Shaltiel, Emanuele Viola

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

Venkatesan Guruswami, Valentine Kabanets

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

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

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

Marcel R. Ackermann, Johannes Blömer, Christoph Scholz

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

Leroy Chew

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

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

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

John Hitchcock, A. Pavan

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

Lijie Chen, Ce Jin, Ryan Williams

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

Igor Carboni Oliveira, Rahul Santhanam

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

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

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

Davide Bilò, Luciano Gualà, Guido Proietti

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

Venkatesan Guruswami, Johan Håstad, Madhu Sudan

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

Vitaly Feldman

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

Dana Moshkovitz, Subhash Khot

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

Ilya Dumer, Daniele Micciancio, Madhu Sudan

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

Janka Chlebíková, Miroslav Chlebik

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

Subhash Khot, Rishi Saket

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

Pavel Hubacek, Eylon Yogev

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

Julia Chuzhoy, Sanjeev Khanna

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

Alexander Durgin, Brendan Juba

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

Suprovat Ghoshal, Rishi Saket

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

Venkatesan Guruswami, Prasad Raghavendra

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

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

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

Venkatesan Guruswami, Kunal Talwar

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

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

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

Venkatesan Guruswami, Rishi Saket

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

Parikshit Gopalan, Subhash Khot, Rishi Saket

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

Venkatesan Guruswami, Prasad Raghavendra

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

Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor

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

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

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

John Hitchcock

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

Arnold Beckmann

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

Johannes Köbler, Sebastian Kuhnert, Oleg Verbitsky

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

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

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

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

Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg

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

Oded Goldreich

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

Monaldo Mastrolilli

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

Irit Dinur, Tali Kaufman

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

Max Hopkins, Tali Kaufman, Shachar Lovett

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

Alan Guo

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

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

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

Dean Doron, Mary Wootters

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

Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin

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

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

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

Hamed Hatami, Shachar Lovett

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

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

Venkatesan Guruswami, Chaoping Xing

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

Kuan Cheng, William Hoza

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

Mark Braverman, Gil Cohen, Sumegha Garg

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

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

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

Leslie G. Valiant

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

Jin-Yi Cai, Pinyan Lu

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

Jin-Yi Cai, Pinyan Lu

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

Ron Rothblum

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

Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

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

Asaf Shapira, Noga Alon

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

Susanna de Rezende, Jakob Nordström, Marc Vinyals

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

Pavel Hrubes

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

Periklis Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis

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

Leroy Chew, Judith Clymo

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

Dakshita Khurana, Amit Sahai

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

Lior Malka

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

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

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

Shafi Goldwasser, Guy Rothblum

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

Mark Zhandry

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

Yael Tauman Kalai, Ran Raz, Ron Rothblum

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

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

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

Ronen Shaltiel

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

Boaz Barak, Amit Sahai

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

Konstantin Makarychev, Yury Makarychev

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

Claire Kenyon-Mathieu, Warren Schudy

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

Ilan Komargodski, Moni Naor, Eylon Yogev

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

Yehuda Lindell

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

Leonid Gurvits

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