All reports in year 2018:

__
TR18-115
| 11th June 2018
__

Valentine Kabanets, Zhenjian Lu#### Satisfiability and Derandomization for Small Polynomial Threshold Circuits

__
TR18-114
| 6th June 2018
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

__
TR18-113
| 30th May 2018
__

Dominik Scheder#### PPSZ for $k \geq 5$: More Is Better

__
TR18-112
| 5th June 2018
__

Raghu Meka, Omer Reingold, Avishay Tal#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

__
TR18-111
| 4th June 2018
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

__
TR18-110
| 4th June 2018
__

Fu Li, David Zuckerman#### Improved Extractors for Recognizable and Algebraic Sources

__
TR18-109
| 29th May 2018
__

Kasper Green Larsen, Jesper Buus Nielsen#### Yes, There is an Oblivious RAM Lower Bound!

__
TR18-108
| 1st June 2018
__

Andrzej Lingas#### Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

__
TR18-107
| 31st May 2018
__

Ran Raz, Avishay Tal#### Oracle Separation of BQP and PH

__
TR18-106
| 30th May 2018
__

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari#### Reachability in $O(\log n)$ Genus Graphs is in Unambiguous

Revisions: 1

__
TR18-105
| 30th May 2018
__

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen#### Quantum proof systems for iterated exponential time, and beyond

__
TR18-104
| 29th May 2018
__

Oded Goldreich#### Flexible models for testing graph properties

Revisions: 1

__
TR18-103
| 30th April 2018
__

Zhao Song, David Woodruff, Peilin Zhong#### Relative Error Tensor Low Rank Approximation

__
TR18-102
| 15th May 2018
__

Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan#### Short Proofs in QBF Expansion

__
TR18-101
| 20th May 2018
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### Finding forbidden minors in sublinear time: a $O(n^{1/2+o(1)})$-query one-sided tester for minor closed properties on bounded degree graphs

__
TR18-100
| 18th May 2018
__

Eshan Chattopadhyay, Anindya De, Rocco Servedio#### Simple and efficient pseudorandom generators from Gaussian processes

__
TR18-099
| 19th May 2018
__

Scott Aaronson#### PDQP/qpoly = ALL

__
TR18-098
| 17th May 2018
__

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

__
TR18-097
| 15th May 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Approximating Operator Norms via Generalized Krivine Rounding

__
TR18-096
| 13th May 2018
__

Venkatesan Guruswami, Andrii Riazanov#### Beating Fredman-Komlós for perfect $k$-hashing

__
TR18-095
| 11th May 2018
__

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

__
TR18-094
| 2nd May 2018
__

Amit Levi, Erik Waingarten#### Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

__
TR18-093
| 10th May 2018
__

Irit Dinur, Pasin Manurangsi#### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

__
TR18-092
| 4th May 2018
__

Marco Carmosino, Russell Impagliazzo, Manuel Sabin#### Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

__
TR18-091
| 4th May 2018
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters#### Improved decoding of Folded Reed-Solomon and Multiplicity Codes

__
TR18-090
| 4th May 2018
__

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf#### Worst-case to average case reductions for the distance to a code

Revisions: 1

__
TR18-089
| 27th April 2018
__

Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, Alexander Smal#### Half-duplex communication complexity

Revisions: 1

__
TR18-088
| 24th April 2018
__

Ilya Volkovich#### A story of AM and Unique-SAT

__
TR18-087
| 20th April 2018
__

Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang#### Quantum Lov{\'a}sz Local Lemma: Shearer's Bound is Tight

__
TR18-086
| 23rd April 2018
__

Joseph Swernofsky#### Tensor Rank is Hard to Approximate

__
TR18-085
| 26th April 2018
__

Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan#### XOR Codes and Sparse Random Linear Equations with Noise

__
TR18-084
| 24th April 2018
__

Iftach Haitner, Nikolaos Makriyannis, Eran Omri#### On the Complexity of Fair Coin Flipping

__
TR18-083
| 25th April 2018
__

Tom Gur, Yang Liu, Ron D. Rothblum#### An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

__
TR18-082
| 21st April 2018
__

Xin Li, Shachar Lovett, Jiapeng Zhang#### Sunflowers and Quasi-sunflowers from Randomness Extractors

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-080
| 6th March 2018
__

Moritz Gobbert#### Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games

__
TR18-079
| 19th April 2018
__

Jayadev Acharya, Clement Canonne, Himanshu Tyagi#### Distributed Simulation and Distributed Inference

__
TR18-078
| 23rd April 2018
__

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra#### Small Set Expansion in The Johnson Graph

__
TR18-077
| 23rd April 2018
__

Boaz Barak, Pravesh Kothari, David Steurer#### Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture

__
TR18-076
| 22nd April 2018
__

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao#### Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 1

__
TR18-075
| 23rd April 2018
__

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 1

__
TR18-074
| 23rd April 2018
__

Daniel Kane, Shachar Lovett, Shay Moran#### Generalized comparison trees for point-location problems

__
TR18-073
| 21st April 2018
__

Amey Bhangale#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

__
TR18-072
| 19th April 2018
__

Avi Wigderson#### On the nature of the Theory of Computation (ToC)

__
TR18-071
| 15th April 2018
__

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak#### Computational Two-Party Correlation

__
TR18-070
| 13th April 2018
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More

__
TR18-069
| 14th April 2018
__

Oded Goldreich, Guy Rothblum#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

__
TR18-068
| 8th April 2018
__

Mrinal Kumar#### On top fan-in vs formal degree for depth-3 arithmetic circuits

Revisions: 1

__
TR18-067
| 9th April 2018
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### Testing Linearity against Non-Signaling Strategies

__
TR18-066
| 8th April 2018
__

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma#### Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

__
TR18-065
| 8th April 2018
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

__
TR18-064
| 3rd April 2018
__

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Generalized Matrix Completion and Algebraic Natural Proofs

__
TR18-063
| 5th April 2018
__

William Hoza, David Zuckerman#### Simple Optimal Hitting Sets for Small-Success $\mathbf{RL}$

Revisions: 1

__
TR18-062
| 7th April 2018
__

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

__
TR18-061
| 6th April 2018
__

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola#### Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs

Revisions: 4

__
TR18-060
| 6th April 2018
__

Emanuele Viola#### Sampling lower bounds: boolean average-case and permutations

__
TR18-059
| 6th April 2018
__

Joshua Brakensiek, Venkatesan Guruswami#### Combining LPs and Ring Equations via Structured Polymorphisms

__
TR18-058
| 5th April 2018
__

Thomas Watson#### Amplification with One NP Oracle Query

__
TR18-057
| 26th March 2018
__

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi#### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

__
TR18-056
| 20th March 2018
__

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs#### Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing

__
TR18-055
| 26th March 2018
__

Titus Dose#### Balance Problems for Integer Circuits

Revisions: 4

__
TR18-054
| 24th March 2018
__

Klim Efremenko, Elad Haramaty, Yael Kalai#### Interactive Coding with Constant Round and Communication Blowup

Revisions: 1

__
TR18-053
| 19th March 2018
__

Nader Bshouty#### Lower Bound for Non-Adaptive Estimate the Number of Defective Items

__
TR18-052
| 16th March 2018
__

Chi-Ning Chou, Mrinal Kumar, Noam Solomon#### Some Closure Results for Polynomial Factorization and Applications

__
TR18-051
| 15th March 2018
__

Stasys Jukna#### Derandomizing Dynamic Programming and Beyond

__
TR18-050
| 15th March 2018
__

Irit Dinur, Oded Goldreich, Tom Gur#### Every set in P is strongly testable under a suitable encoding

__
TR18-049
| 14th March 2018
__

Stasys Jukna, Hannes Seiwert#### Greedy can also beat pure dynamic programming

Revisions: 1

__
TR18-048
| 11th March 2018
__

Ofer Grossman, Yang Liu#### Reproducibility and Pseudo-Determinism in Log-Space

__
TR18-047
| 7th March 2018
__

Shachar Lovett#### A proof of the GM-MDS conjecture

Revisions: 1

__
TR18-046
| 9th March 2018
__

Oded Goldreich, Guy Rothblum#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 1

__
TR18-045
| 6th March 2018
__

Oded Goldreich, Dana Ron#### The Subgraph Testing Model

__
TR18-044
| 5th March 2018
__

Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner#### Spatial Isolation Implies Zero Knowledge Even in a Quantum World

__
TR18-043
| 22nd February 2018
__

Andrei Romashchenko, Marius Zimand#### An operational characterization of mutual information in algorithmic information theory

__
TR18-042
| 1st March 2018
__

Stasys Jukna#### Incremental versus Non-Incremental Dynamic Programming

__
TR18-041
| 26th February 2018
__

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Reordering Rule Makes OBDD Proof Systems Stronger

__
TR18-040
| 21st February 2018
__

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan#### Non-Malleable Codes for Small-Depth Circuits

__
TR18-039
| 23rd February 2018
__

Md Lutfar Rahman, Thomas Watson#### Complexity of Unordered CNF Games

__
TR18-038
| 21st February 2018
__

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann#### Tight Bounds using Hankel Matrix for Arithmetic Circuits with Unique Parse Trees

__
TR18-037
| 21st February 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Inapproximability of Matrix $p \rightarrow q$ Norms

__
TR18-036
| 21st February 2018
__

Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Towards blackbox identity testing of log-variate circuits

__
TR18-035
| 21st February 2018
__

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena#### Bootstrapping variables in algebraic circuits

__
TR18-034
| 15th February 2018
__

Young Kun Ko#### On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

__
TR18-033
| 16th February 2018
__

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz#### The Communication Complexity of Private Simultaneous Messages, Revisited

__
TR18-032
| 14th February 2018
__

Gil Cohen, Bernhard Haeupler, Leonard Schulman#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

__
TR18-030
| 9th February 2018
__

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam#### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

__
TR18-029
| 9th February 2018
__

Neeraj Kayal, vineet nair, Chandan Saha#### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

Revisions: 1

__
TR18-028
| 7th February 2018
__

Xin Li#### Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications

Revisions: 1

__
TR18-027
| 8th February 2018
__

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan#### General Strong Polarization

__
TR18-026
| 7th February 2018
__

Lijie Chen#### On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Revisions: 1

__
TR18-025
| 1st February 2018
__

Olaf Beyersdorff, Judith Clymo#### More on Size and Width in QBF Resolution

__
TR18-024
| 1st February 2018
__

Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin#### The Riis Complexity Gap for QBF Resolution

__
TR18-023
| 4th February 2018
__

Eran Iceland, Alex Samorodnitsky#### On coset leader graphs of structured linear codes

Revisions: 1

__
TR18-022
| 1st February 2018
__

Omer Reingold, Guy Rothblum, Ron Rothblum#### Efficient Batch Verification for UP

__
TR18-021
| 30th January 2018
__

Omri Ben-Eliezer, Eldar Fischer#### Earthmover Resilience and Testing in Ordered Structures

__
TR18-020
| 30th January 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Computing the maximum using $(\min, +)$ formulas

Comments: 1

__
TR18-019
| 28th January 2018
__

Zeyu Guo, Nitin Saxena, Amit Sinhababu#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

__
TR18-018
| 22nd January 2018
__

John Hitchcock, Adewale Sekoni, Hadi Shafei#### Polynomial-Time Random Oracles and Separating Complexity Classes

__
TR18-017
| 26th January 2018
__

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing#### Lossless dimension expanders via linearized polynomials and subspace designs

__
TR18-016
| 25th January 2018
__

Naomi Kirshner, Alex Samorodnitsky#### On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

Revisions: 1

__
TR18-015
| 25th January 2018
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett#### Pseudorandom Generators from Polarizing Random Walks

Revisions: 1
,
Comments: 1

__
TR18-014
| 10th January 2018
__

Swagato Sanyal#### A Composition Theorem via Conflict Complexity

__
TR18-013
| 18th January 2018
__

John Hitchcock, Adewale Sekoni#### Nondeterminisic Sublinear Time Has Measure 0 in P

__
TR18-012
| 20th January 2018
__

Valentine Kabanets, Zhenjian Lu#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

__
TR18-011
| 18th January 2018
__

John Hitchcock, Hadi Shafei#### Nonuniform Reductions and NP-Completeness

__
TR18-010
| 14th January 2018
__

Alexander A. Sherstov#### Algorithmic polynomials

__
TR18-009
| 9th January 2018
__

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

__
TR18-008
| 10th January 2018
__

Tom Gur, Igor Shinkar#### An Entropy Lower Bound for Non-Malleable Extractors

__
TR18-007
| 9th January 2018
__

Lior Gishboliner, Asaf Shapira#### A Generalized Turan Problem and its Applications

__
TR18-006
| 10th January 2018
__

Subhash Khot, Dor Minzer, Muli Safra#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

__
TR18-005
| 9th January 2018
__

C. Seshadhri, Deeparnab Chakrabarty#### Adaptive Boolean Monotonicity Testing in Total Influence Time

__
TR18-004
| 3rd January 2018
__

Aayush Ojha, Raghunath Tewari#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

__
TR18-003
| 2nd January 2018
__

Roei Tell#### Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

Revisions: 2

__
TR18-002
| 31st December 2017
__

Constantinos Daskalakis, Gautam Kamath, John Wright#### Which Distribution Distances are Sublinearly Testable?

__
TR18-001
| 2nd January 2018
__

Tim Roughgarden#### Complexity Theory, Game Theory, and Economics

Valentine Kabanets, Zhenjian Lu

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>>

Dominik Scheder

We show that for $k \geq 5$, the PPSZ algorithm for $k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every $k\geq 5$, there is a strictly increasing function $f: [0,1] \rightarrow \mathbb{R}$ with $f(0) = 0$ that has the ... more >>>

Raghu Meka, Omer Reingold, Avishay Tal

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,

computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or

$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a

deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing

algorithm to check whether $f \equiv 0$ or ...
more >>>

Fu Li, David Zuckerman

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

Our first method shows that ...
more >>>

Kasper Green Larsen, Jesper Buus Nielsen

An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky

[JACM'96] is a (possibly randomized) RAM, for which the memory access

pattern reveals no information about the operations

performed. The main performance metric of an ORAM is the bandwidth

overhead, i.e., the multiplicative factor extra memory blocks that must be

accessed ...
more >>>

Andrzej Lingas

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... more >>>

Ran Raz, Avishay Tal

We present a distribution $D$ over inputs in $\{-1,1\}^{2N}$, such that:

(1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time $O(\log N)$, that distinguishes between $D$ and the uniform distribution with advantage $\Omega(1/\log N)$.

(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ...
more >>>

Chetan Gupta, Vimalraj Sharma, Raghunath Tewari

Given the polygonal schema embedding of an $O(log n)$ genus graph $G$ and two vertices

$s$ and $t$ in $G$, we show that deciding if there is a path from $s$ to $t$ in $G$ is in unambiguous

logarithmic space.

Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, Henry Yuen

We show that any language in nondeterministic time $\exp(\exp(\cdots\exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - \exp(-C\exp(\cdots\exp(n)))$, ... more >>>

Oded Goldreich

The standard models of testing graph properties postulate that the vertex-set consists of $\{1,2,...,n\}$, where $n$ is a natural number that is given explicitly to the tester.

Here we suggest more flexible models by postulating that the tester is given access to samples the arbitrary vertex-set; that is, the vertex-set ...
more >>>

Zhao Song, David Woodruff, Peilin Zhong

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

Olaf Beyersdorff, Leroy Chew, Judith Clymo, Meena Mahajan

For quantified Boolean formulas (QBF) there are two main different approaches to solving: QCDCL and expansion solving. In this paper we compare the underlying proof systems and show that expansion systems admit strictly shorter proofs than CDCL systems for formulas of bounded quantifier complexity, thus pointing towards potential advantages of ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).

We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Eshan Chattopadhyay, Anindya De, Rocco Servedio

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space.

The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>>

Scott Aaronson

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... 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 >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

Venkatesan Guruswami, Andrii Riazanov

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... 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 >>>

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions ... more >>>

Irit Dinur, Pasin Manurangsi

We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G = (V, E)$, an alphabet set $\Sigma$ and, for each edge $\{u, v\} \in E$, a constraint $C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment $\sigma: V ... more >>>

Marco Carmosino, Russell Impagliazzo, Manuel Sabin

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf, Mary Wootters

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

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Algebraic proof systems reduce computational problems to problems about estimating the distance of a sequence of functions $u=(u_1,\ldots, u_k)$, given as oracles, from a linear error correcting code $V$. The soundness of such systems relies on methods that act ``locally'' on $u$ and map it to a single function $u^*$ ... more >>>

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

Ilya Volkovich

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

Kun He, Qian Li, Xiaoming Sun, Jiapeng Zhang

Lov{\'a}sz Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all ``bad" events under some ``weakly dependent" condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science \cite{moser2010constructive, kolipaka2011moser, harvey2015algorithmic}. ... more >>>

Joseph Swernofsky

We prove that approximating the rank of a 3-tensor to within a factor of $1 + 1/1852 - \delta$, for any $\delta > 0$, is NP-hard over any finite field. We do this via reduction from bounded occurrence 2-SAT.

more >>>Andrej Bogdanov, Manuel Sabin, Prashant Nalini Vasudevan

A $k$-LIN instance is a system of $m$ equations over $n$ variables of the form $s_{i[1]} + \dots + s_{i[k]} =$ 0 or 1 modulo 2 (each involving $k$ variables). We consider two distributions on instances in which the variables are chosen independently and uniformly but the right-hand sides are ... more >>>

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

Tom Gur, Yang Liu, Ron D. Rothblum

Non-interactive proofs of proximity allow a sublinear-time verifier to check that

a given input is close to the language, given access to a short proof. Two natural

variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof

is a function of the input only, and AM-proofs ...
more >>>

Xin Li, Shachar Lovett, Jiapeng Zhang

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Moritz Gobbert

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... more >>>

Jayadev Acharya, Clement Canonne, Himanshu Tyagi

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers

t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if

their intersection is of size t. The Johnson graph arises often ...
more >>>

Boaz Barak, Pravesh Kothari, David Steurer

Dinur, Khot, Kindler, Minzer and Safra (2016) recently showed that the (imperfect completeness variant of) Khot's 2 to 2 games conjecture follows from a combinatorial hypothesis about the soundness of a certain ``Grassmanian agreement tester''.

In this work, we show that the hypothesis of Dinur et al follows from a ...
more >>>

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$

can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ...
more >>>

Amey Bhangale

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.

(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

Avi Wigderson

[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, ... more >>>

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\begin{itemize}

\item We develop new tools to ...
more >>>

Eshan Chattopadhyay, Xin Li

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... more >>>

Oded Goldreich, Guy Rothblum

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.

Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than

the work of Reingold, Rothblum, and Rothblum (STOC, 2016).

Our proof system for AC0[2] supports a more ...
more >>>

Mrinal Kumar

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,

the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.

Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ...
more >>>

Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

William Hoza, David Zuckerman

We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length $r$ with known variable order. Our generator has seed length $O\left(\frac{\log(wr) \log r}{\max\{1, \log \log w - \log \log r\}} + \log(1/\varepsilon)\right)$. This seed length improves on recent work by Braverman, Cohen, and ... more >>>

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Aryeh Grinberg, Ronen Shaltiel, Emanuele Viola

We study how well can $q$-query decision trees distinguish between the

following two distributions: (i) $R=(R_1,\ldots,R_N)$ that are i.i.d.

variables, (ii) $X=(R|R \in A)$ where $A$ is an event s.t. $\Pr[R \in A] \ge

2^{-a}$. We prove two lemmas:

- Forbidden-set lemma: There exists $B \subseteq [N]$ of

size ...
more >>>

Emanuele Viola

We show that for every small AC$^{0}$ circuit

$C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of

$2^{m-m^{\Omega(1)}}$ restrictions that preserve the output distribution of

$C$ and moreover \emph{polarize min-entropy: }the restriction of $C$ to

any $r\in S$ either is constant or has polynomial min-entropy. This

structural result is then applied to ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>>

Thomas Watson

We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our ... more >>>

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs

We present a worst case decoding problem whose hardness reduces to that of solving the Learning Parity with Noise (LPN) problem, in some parameter regime. Prior to this work, no worst case hardness result was known for LPN (as opposed to syntactically similar problems such as Learning with Errors). The ... more >>>

Titus Dose

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the ... more >>>

Klim Efremenko, Elad Haramaty, Yael Kalai

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since ... more >>>

Nader Bshouty

We prove that to estimate within a constant factor the number of defective items in a non-adaptive group testing algorithm we need at least $\tilde\Omega((\log n)(\log(1/\delta)))$ tests. This solves the open problem posed by Damaschke and Sheikh Muhammad.

more >>>Chi-Ning Chou, Mrinal Kumar, Noam Solomon

In a sequence of fundamental results in the 80's, Kaltofen showed that factors of multivariate polynomials with small arithmetic circuits have small arithmetic circuits. In other words, the complexity class $VP$ is closed under taking factors. A natural question in this context is to understand if other natural classes of ... more >>>

Stasys Jukna

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>>

Irit Dinur, Oded Goldreich, Tom Gur

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

Stasys Jukna, Hannes Seiwert

Many dynamic programming algorithms are ``pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on $n$-vertex graphs using only $O(n^2\log n)$ operations. We prove that any pure DP algorithm ... more >>>

Ofer Grossman, Yang Liu

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

Shachar Lovett

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.

Oded Goldreich, Guy Rothblum

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}

\item{\em A worst-case to average-case reduction}:

We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ...
more >>>

Oded Goldreich, Dana Ron

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.

The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.

The tester is ...
more >>>

Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

Andrei Romashchenko, Marius Zimand

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings

$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that

two parties, one having $x$ and the complexity profile of the pair and the ...
more >>>

Stasys Jukna

Many dynamic programming algorithms for discrete optimization problems are "pure" in that they only use min/max and addition operations in their recursions. Some of them, in particular those for various shortest path problems, are even "incremental" in that one of the inputs to the addition operations is a variable. We ... more >>>

Sam Buss, Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

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

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann

This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.

The key notion for understanding the ... more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We study the problem of computing the $p\rightarrow q$ norm of a matrix $A \in R^{m \times n}$, defined as \[ \|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p} \] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$, $q=1$), and has been ... more >>>

Michael Forbes, Sumanta Ghosh, Nitin Saxena

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

Young Kun Ko

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the ... more >>>

Gil Cohen, Bernhard Haeupler, Leonard Schulman

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

Neeraj Kayal, vineet nair, Chandan Saha

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>

Xin Li

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey ... more >>>

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

Lijie Chen

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves ...
more >>>

Olaf Beyersdorff, Judith Clymo

In their influential paper `Short proofs are narrow -- resolution made simple', Ben-Sasson and Wigderson introduced a crucial tool for proving lower bounds on the lengths of proofs in the resolution calculus. Over a decade later their technique for showing lower bounds on the size of proofs, by examining the ... more >>>

Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>

Eran Iceland, Alex Samorodnitsky

We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature.

The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, ... more >>>

Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

Omri Ben-Eliezer, Eldar Fischer

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>>

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$

over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ...
more >>>

Zeyu Guo, Nitin Saxena, Amit Sinhababu

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

John Hitchcock, Adewale Sekoni, Hadi Shafei

Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random

oracle A, with probability 1. We investigate whether this result

extends to individual polynomial-time random oracles. We consider two

notions of random oracles: p-random oracles in the sense of

martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ...
more >>>

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>>

Naomi Kirshner, Alex Samorodnitsky

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

Swagato Sanyal

Let $\R(\cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f \subseteq \{0,1\}^n \times \mathcal{S}$ and partial Boolean function $g \subseteq \{0,1\}^n \times \{0,1\}$, $\R_{1/3}(f \circ g^n) = \Omega(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example ... more >>>

John Hitchcock, Adewale Sekoni

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

Valentine Kabanets, Zhenjian Lu

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

John Hitchcock, Hadi Shafei

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

Tom Gur, Igor Shinkar

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

Lior Gishboliner, Asaf Shapira

Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for ... more >>>

Subhash Khot, Dor Minzer, Muli Safra

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of testing monotonicity

of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention

recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester

of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence

of $f$. We give an adaptive tester whose running ...
more >>>

Aayush Ojha, Raghunath Tewari

Recently, perfect matching in bounded planar cutwidth bipartite graphs

$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that

the problem is in AC$^0$.

In this paper, we disprove their conjecture by showing that the problem is

not in AC$^0[p^{\alpha}]$ for every prime $p$. ...
more >>>

Roei Tell

We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without ... more >>>

Constantinos Daskalakis, Gautam Kamath, John Wright

Given samples from an unknown distribution $p$ and a description of a distribution $q$, are $p$ and $q$ close or far? This question of "identity testing" has received significant attention in the case of testing whether $p$ and $q$ are equal or far in total variation distance. However, in recent ... more >>>

Tim Roughgarden

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.

The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>