All reports in year 2018:

__
TR18-001
| 2nd January 2018
__

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

__
TR18-002
| 31st December 2017
__

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

__
TR18-003
| 2nd January 2018
__

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

Revisions: 4

__
TR18-004
| 3rd January 2018
__

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

__
TR18-005
| 9th January 2018
__

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

__
TR18-006
| 10th January 2018
__

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

Revisions: 2

__
TR18-007
| 9th January 2018
__

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

__
TR18-008
| 10th January 2018
__

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

__
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-010
| 14th January 2018
__

Alexander A. Sherstov#### Algorithmic polynomials

__
TR18-011
| 18th January 2018
__

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

__
TR18-012
| 20th January 2018
__

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

__
TR18-013
| 18th January 2018
__

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

__
TR18-014
| 10th January 2018
__

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

__
TR18-015
| 25th January 2018
__

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

Revisions: 1
,
Comments: 1

__
TR18-016
| 25th January 2018
__

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

Revisions: 1

__
TR18-017
| 26th January 2018
__

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

__
TR18-018
| 22nd January 2018
__

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

__
TR18-019
| 28th January 2018
__

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

Revisions: 1

__
TR18-020
| 30th January 2018
__

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

Comments: 1

__
TR18-021
| 30th January 2018
__

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

__
TR18-022
| 1st February 2018
__

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

__
TR18-023
| 4th February 2018
__

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

Revisions: 1

__
TR18-024
| 1st February 2018
__

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

__
TR18-025
| 1st February 2018
__

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

__
TR18-026
| 7th February 2018
__

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

Revisions: 1

__
TR18-027
| 8th February 2018
__

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

__
TR18-028
| 7th February 2018
__

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

Revisions: 1

__
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: 2

__
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-031
| 15th February 2018
__

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

Revisions: 2

__
TR18-032
| 14th February 2018
__

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

__
TR18-033
| 16th February 2018
__

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

__
TR18-034
| 15th February 2018
__

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

__
TR18-035
| 21st February 2018
__

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

__
TR18-036
| 21st February 2018
__

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

__
TR18-037
| 21st February 2018
__

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

__
TR18-038
| 21st February 2018
__

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

__
TR18-039
| 23rd February 2018
__

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

__
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-041
| 26th February 2018
__

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

__
TR18-042
| 1st March 2018
__

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

__
TR18-043
| 22nd February 2018
__

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

Revisions: 2

__
TR18-044
| 5th March 2018
__

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

Revisions: 1

__
TR18-045
| 6th March 2018
__

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

__
TR18-046
| 9th March 2018
__

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

Revisions: 2

__
TR18-047
| 7th March 2018
__

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

Revisions: 1

__
TR18-048
| 11th March 2018
__

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

__
TR18-049
| 14th March 2018
__

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

Revisions: 1

__
TR18-050
| 15th March 2018
__

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

__
TR18-051
| 15th March 2018
__

Stasys Jukna#### Derandomizing Dynamic Programming and Beyond

__
TR18-052
| 16th March 2018
__

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

__
TR18-053
| 19th March 2018
__

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

__
TR18-054
| 24th March 2018
__

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

Revisions: 1

__
TR18-055
| 26th March 2018
__

Titus Dose#### Balance Problems for Integer Circuits

Revisions: 5

__
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-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-058
| 5th April 2018
__

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

__
TR18-059
| 6th April 2018
__

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

Revisions: 1

__
TR18-060
| 6th April 2018
__

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

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

__
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-063
| 5th April 2018
__

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

Revisions: 1

__
TR18-064
| 3rd April 2018
__

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

__
TR18-065
| 8th April 2018
__

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

Revisions: 1

__
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-067
| 9th April 2018
__

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

Revisions: 1

__
TR18-068
| 8th April 2018
__

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

Revisions: 1

__
TR18-069
| 14th April 2018
__

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

Revisions: 1

__
TR18-070
| 13th April 2018
__

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

Revisions: 2

__
TR18-071
| 15th April 2018
__

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

__
TR18-072
| 19th April 2018
__

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

__
TR18-073
| 21st April 2018
__

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

__
TR18-074
| 23rd April 2018
__

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

__
TR18-075
| 23rd April 2018
__

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

Revisions: 2

__
TR18-076
| 22nd April 2018
__

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

Revisions: 2

__
TR18-077
| 23rd April 2018
__

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

__
TR18-078
| 23rd April 2018
__

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

__
TR18-079
| 19th April 2018
__

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

Revisions: 1

__
TR18-080
| 6th March 2018
__

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

__
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-082
| 21st April 2018
__

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

__
TR18-083
| 25th April 2018
__

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

Revisions: 2

__
TR18-084
| 24th April 2018
__

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

__
TR18-085
| 26th April 2018
__

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

__
TR18-086
| 23rd April 2018
__

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

Revisions: 1

__
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-088
| 24th April 2018
__

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

__
TR18-089
| 27th April 2018
__

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

Revisions: 2

__
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-091
| 4th May 2018
__

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

__
TR18-092
| 4th May 2018
__

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

__
TR18-093
| 10th May 2018
__

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

__
TR18-094
| 2nd May 2018
__

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

__
TR18-095
| 11th May 2018
__

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

__
TR18-096
| 13th May 2018
__

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

__
TR18-097
| 15th May 2018
__

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

__
TR18-098
| 17th May 2018
__

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

Revisions: 1

__
TR18-099
| 19th May 2018
__

Scott Aaronson#### PDQP/qpoly = ALL

__
TR18-100
| 18th May 2018
__

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

Revisions: 1

__
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-102
| 15th May 2018
__

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

__
TR18-103
| 30th April 2018
__

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

__
TR18-104
| 29th May 2018
__

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

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-106
| 30th May 2018
__

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

Revisions: 1

__
TR18-107
| 31st May 2018
__

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

__
TR18-108
| 1st June 2018
__

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

__
TR18-109
| 29th May 2018
__

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

__
TR18-110
| 4th June 2018
__

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

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-112
| 5th June 2018
__

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

Revisions: 1

__
TR18-113
| 30th May 2018
__

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

__
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-115
| 11th June 2018
__

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

__
TR18-116
| 18th June 2018
__

Xue Chen, David Zuckerman#### Existence of Simple Extractors

Revisions: 1

__
TR18-117
| 23rd June 2018
__

Fedor Part, Iddo Tzameret#### Resolution with Counting: Lower Bounds over Different Moduli

Revisions: 1

__
TR18-118
| 20th June 2018
__

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

__
TR18-119
| 21st June 2018
__

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang#### A Tight Lower Bound for Entropy Flattening

Revisions: 1

__
TR18-120
| 21st June 2018
__

Alexandros Hollender, Paul Goldberg#### The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard

__
TR18-121
| 20th June 2018
__

Justin Holmgren, Lisa Yang#### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

__
TR18-122
| 3rd July 2018
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudo-derandomizing learning and approximation

__
TR18-123
| 3rd July 2018
__

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

Revisions: 1

__
TR18-124
| 6th July 2018
__

Amir Yehudayoff#### Separating Monotone VP and VNP

__
TR18-125
| 7th July 2018
__

Zvika Brakerski#### Fundamentals of Fully Homomorphic Encryption – A Survey

__
TR18-126
| 24th June 2018
__

Pravesh Kothari, Ruta Mehta#### Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium

__
TR18-127
| 9th July 2018
__

Stasys Jukna, Hannes Seiwert#### Approximation Limitations of Tropical Circuits

__
TR18-128
| 11th July 2018
__

Ewin Tang#### A quantum-inspired classical algorithm for recommendation systems

Revisions: 3

__
TR18-129
| 13th July 2018
__

Jelani Nelson, Huacheng Yu#### Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

__
TR18-130
| 16th July 2018
__

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich#### Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

__
TR18-131
| 17th July 2018
__

Gautam Kamath, Christos Tzamos#### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

__
TR18-132
| 17th July 2018
__

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 2

__
TR18-133
| 26th July 2018
__

Emanuele Viola#### Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

__
TR18-134
| 24th July 2018
__

Tali Kaufman, David Mass#### Cosystolic Expanders over any Abelian Group

__
TR18-135
| 31st July 2018
__

Prasad Chaugule, Nutan Limaye, Aditya Varre#### Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

__
TR18-136
| 1st August 2018
__

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma#### List Decoding with Double Samplers

__
TR18-137
| 7th August 2018
__

Scott Aaronson#### Quantum Lower Bound for Approximate Counting Via Laurent Polynomials

__
TR18-138
| 10th August 2018
__

Shuichi Hirahara#### Non-black-box Worst-case to Average-case Reductions within NP

Revisions: 1

__
TR18-139
| 10th August 2018
__

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

__
TR18-140
| 11th August 2018
__

Ilan Komargodski, Ran Raz, Yael Tauman Kalai#### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Revisions: 1

__
TR18-141
| 6th August 2018
__

Sandip Sinha, Omri Weinstein#### Local Decodability of the Burrows-Wheeler Transform

Revisions: 1

__
TR18-142
| 17th August 2018
__

Kaave Hosseini, Shachar Lovett#### A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

__
TR18-143
| 16th August 2018
__

Mark Bun, Justin Thaler#### The Large-Error Approximate Degree of AC$^0$

__
TR18-144
| 18th August 2018
__

Mert Saglam#### Near log-convexity of measured heat in (discrete) time and consequences

__
TR18-145
| 13th August 2018
__

Ryan O'Donnell, Rocco Servedio, Li-Yang Tan#### Fooling Polytopes

__
TR18-146
| 18th August 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Shortest path length with bounded-alternation $(\min, +)$ formulas

__
TR18-147
| 19th August 2018
__

Michael Forbes, Zander Kelley#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

__
TR18-148
| 25th August 2018
__

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

__
TR18-149
| 25th August 2018
__

Craig Gentry, Charanjit Jutla#### Obfuscation using Tensor Products

__
TR18-150
| 27th August 2018
__

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan#### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

__
TR18-151
| 29th August 2018
__

Ankit Garg, Rafael Oliveira#### Recent progress on scaling algorithms and applications

__
TR18-152
| 30th August 2018
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Sensitivity, Affine Transforms and Quantum Communication Complexity

__
TR18-153
| 22nd August 2018
__

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma#### New Bounds for Energy Complexity of Boolean Functions

__
TR18-154
| 7th September 2018
__

Stasys Jukna, Andrzej Lingas#### Lower Bounds for Circuits of Bounded Negation Width

__
TR18-155
| 8th September 2018
__

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

__
TR18-156
| 8th September 2018
__

Mark Bun, Robin Kothari, Justin Thaler#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

__
TR18-157
| 10th September 2018
__

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

__
TR18-158
| 11th September 2018
__

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

Revisions: 1

__
TR18-159
| 11th September 2018
__

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell#### Expander-Based Cryptography Meets Natural Proofs

Revisions: 1

__
TR18-160
| 12th September 2018
__

Anna Gal, Avishay Tal, Adrian Trejo Nuñez#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

__
TR18-161
| 13th September 2018
__

Justin Holmgren, Ron Rothblum#### Delegating Computations with (almost) Minimal Time and Space Overhead

__
TR18-162
| 16th September 2018
__

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

__
TR18-163
| 18th September 2018
__

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov#### Adventures in Monotone Complexity and TFNP

__
TR18-164
| 18th September 2018
__

Nikhil Gupta, Chandan Saha#### On the symmetries of design polynomials

__
TR18-165
| 20th September 2018
__

Stefan Dantchev, Nicola Galesi, Barnaby Martin#### Resolution and the binary encoding of combinatorial principles

__
TR18-166
| 18th September 2018
__

Tayfun Pay, James Cox#### An overview of some semantic and syntactic complexity classes

__
TR18-167
| 25th September 2018
__

Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf#### Improved bounds on Fourier entropy and Min-entropy

__
TR18-168
| 25th September 2018
__

Alex Samorodnitsky#### An upper bound on $\ell_q$ norms of noisy functions

__
TR18-169
| 18th September 2018
__

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev#### Optimality of Linear Sketching under Modular Updates

__
TR18-170
| 4th October 2018
__

Nicola Galesi, Navid Talebanfard, Jacobo Toran#### Cops-Robber games and the resolution of Tseitin formulas

__
TR18-171
| 10th October 2018
__

Oded Goldreich#### Testing Graphs in Vertex-Distribution-Free Models

Revisions: 1

__
TR18-172
| 11th October 2018
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Building Strategies into QBF Proofs

__
TR18-173
| 17th October 2018
__

Eric Allender, Rahul Ilango, Neekon Vafa#### The Non-Hardness of Approximating Circuit Size

Revisions: 1

__
TR18-174
| 19th October 2018
__

Anastasiya Chistopolskaya, Vladimir Podolskii#### Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

__
TR18-175
| 23rd October 2018
__

Bruno Loff, Sagnik Mukhopadhyay#### Lifting Theorems for Equality

Revisions: 2

__
TR18-176
| 26th October 2018
__

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif#### The Log-Approximate-Rank Conjecture is False

__
TR18-177
| 1st October 2018
__

Alexander Knop#### The Diptych of Communication Complexity Classes in the Best-partition Model and the Fixed-partition Model

__
TR18-178
| 9th October 2018
__

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

__
TR18-179
| 31st October 2018
__

Dominik Scheder#### PPSZ on CSP Instances with Multiple Solutions

__
TR18-180
| 3rd November 2018
__

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre#### Lower bounds for arithmetic circuits via the Hankel matrix

__
TR18-181
| 30th October 2018
__

Giuseppe Persiano, Kevin Yeo#### Lower Bounds for Differentially Private RAMs

__
TR18-182
| 31st October 2018
__

Henry Corrigan-Gibbs, Dmitry Kogan#### The Function-Inversion Problem: Barriers and Opportunities

__
TR18-183
| 5th November 2018
__

Dean Doron, Pooya Hatami, William Hoza#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

__
TR18-184
| 5th November 2018
__

Iddo Tzameret, Stephen Cook#### Uniform, Integral and Feasible Proofs for the Determinant Identities

__
TR18-185
| 6th November 2018
__

Yonatan Nakar, Dana Ron#### On the Testability of Graph Partition Properties

__
TR18-186
| 6th November 2018
__

Emanuele Viola#### Lower bounds for data structures with space close to maximum imply circuit lower bounds

Revisions: 1

__
TR18-187
| 4th November 2018
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Revisions: 1

__
TR18-188
| 7th November 2018
__

Zeev Dvir, Alexander Golovnev, Omri Weinstein#### Static Data Structure Lower Bounds Imply Rigidity

Revisions: 2

__
TR18-189
| 8th November 2018
__

Ilias Diakonikolas, Daniel Kane#### Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

__
TR18-190
| 5th November 2018
__

Shachar Lovett, Jiapeng Zhang#### DNF sparsification beyond sunflowers

__
TR18-191
| 10th November 2018
__

Neeraj Kayal, Chandan Saha#### Reconstruction of non-degenerate homogeneous depth three circuits

__
TR18-192
| 12th November 2018
__

Alexander Golovnev, Alexander Kulikov#### Circuit Depth Reductions

Revisions: 2

__
TR18-193
| 14th November 2018
__

Nicollas Sdroievski, Murilo Silva, André Vignatti#### The Hidden Subgroup Problem and MKTP

__
TR18-194
| 15th November 2018
__

Amir Yehudayoff#### Anti-concentration in most directions

Revisions: 5

__
TR18-195
| 18th November 2018
__

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma#### Erasures versus Errors in Local Decoding and Property Testing

__
TR18-196
| 19th November 2018
__

Omri Ben-Eliezer#### Testing local properties of arrays

__
TR18-197
| 22nd November 2018
__

Andrej Bogdanov#### Approximate degree of AND via Fourier analysis

Revisions: 1

__
TR18-198
| 22nd November 2018
__

Irit Dinur, Tali Kaufman, Noga Ron-Zewi#### From Local to Robust Testing via Agreement Testing

Revisions: 1

__
TR18-199
| 24th November 2018
__

Lijie Chen, Roei Tell#### Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

__
TR18-200
| 29th November 2018
__

Ashutosh Kumar, Raghu Meka, Amit Sahai#### Leakage-Resilient Secret Sharing

__
TR18-201
| 30th November 2018
__

Anurag Anshu, Naresh Boddu, Dave Touchette#### Quantum Log-Approximate-Rank Conjecture is also False

Comments: 1

__
TR18-202
| 1st December 2018
__

Xinyu Wu#### A stochastic calculus approach to the oracle separation of BQP and PH

__
TR18-203
| 1st December 2018
__

Yael Kalai, Dakshita Khurana#### Non-Interactive Non-Malleability from Quantum Supremacy

__
TR18-204
| 30th November 2018
__

Makrand Sinha, Ronald de Wolf#### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

__
TR18-205
| 3rd December 2018
__

Siddhesh Chaubal, Anna Gal#### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

__
TR18-206
| 3rd December 2018
__

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals#### Equality Alone Does Not Simulate Randomness

Revisions: 1

__
TR18-207
| 5th December 2018
__

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan#### On the Probabilistic Degree of OR over the Reals

__
TR18-208
| 27th November 2018
__

Benny Applebaum, Prashant Nalini Vasudevan#### Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

Revisions: 1

__
TR18-209
| 8th December 2018
__

Emanuele Viola#### AC0 unpredictability

__
TR18-210
| 30th November 2018
__

Karthik C. S., Pasin Manurangsi#### On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

__
TR18-211
| 3rd December 2018
__

Kshitij Gajjar, Jaikumar Radhakrishnan#### Parametric Shortest Paths in Planar Graphs

Revisions: 1

__
TR18-212
| 26th December 2018
__

Prerona Chatterjee, Ramprasad Saptharishi#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

__
TR18-213
| 28th December 2018
__

Moni Naor, Merav Parter, Eylon Yogev#### The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Ofer Grossman, Yang P. 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 >>>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Tom Gur, Yang P. 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 >>>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

Xue Chen, David Zuckerman

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>>

Fedor Part, Iddo Tzameret

Resolution over linear equations (introduced in [RT08]) emerged recently as an important object of study. This refutation system, denoted Res(lin$_R$), operates with disjunction of linear equations over a ring $R$. On the one hand, the system captures a natural ``minimal'' extension of resolution in which efficient counting can be achieved; ... 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 >>>

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

Alexandros Hollender, Paul Goldberg

The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we ... more >>>

Justin Holmgren, Lisa Yang

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser

[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed

output with high probability. We explore pseudo-determinism in the settings of learning and ap-

proximation. Our goal is to simulate known randomized algorithms in these settings ...
more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

Amir Yehudayoff

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

Zvika Brakerski

A homomorphic encryption scheme is one that allows computing on encrypted data without decrypting it first. In fully homomorphic encryption it is possible to apply any efficiently computable function to encrypted data. We provide a survey on the origins, definitions, properties, constructions and uses of fully homomorphic encryption.

more >>>Pravesh Kothari, Ruta Mehta

Several works have shown unconditional hardness (via integrality gaps) of computing equilibria using strong hierarchies of convex relaxations. Such results however only apply to the problem of computing equilibria that optimize a certain objective function and not to the (arguably more fundamental) task of finding \emph{any} equilibrium.

We present ... more >>>

Stasys Jukna, Hannes Seiwert

We develop general lower bound arguments for approximating tropical

(min,+) and (max,+) circuits, and use them to prove the

first non-trivial, even super-polynomial, lower bounds on the size

of such circuits approximating some explicit optimization

problems. In particular, these bounds show that the approximation

powers of pure dynamic programming algorithms ...
more >>>

Ewin Tang

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an $m\times n$ matrix of small rank $k$. We give the first classical algorithm to produce a recommendation in $O(\text{poly}(k)\text{polylog}(m,n))$ time, which is an exponential improvement on previous ... more >>>

Jelani Nelson, Huacheng Yu

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the ... more >>>

Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d) \log n}$. Prior to our ... more >>>

Gautam Kamath, Christos Tzamos

We investigate distribution testing with access to non-adaptive conditional samples.

In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.

In the non-adaptive setting, ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

Emanuele Viola

Research in the 80's and 90's showed how to construct a pseudorandom

generator from a function that is hard to compute on more than $99\%$

of the inputs. A more recent line of works showed however that if

the generator has small error, then the proof of correctness cannot

be ...
more >>>

Tali Kaufman, David Mass

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>

Prasad Chaugule, Nutan Limaye, Aditya Varre

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

Scott Aaronson

We consider the following problem: estimate the size of a nonempty set $S\subseteq\left[ N\right] $, given both quantum queries to a membership oracle for $S$, and a device that generates equal superpositions $\left\vert S\right\rangle $ over $S$ elements. We show that, if $\left\vert S\right\vert $ is neither too large nor ... more >>>

Shuichi Hirahara

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... 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 >>>

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>

Sandip Sinha, Omri Weinstein

The Burrows-Wheeler Transform (BWT) is among the most influential discoveries in text compression and DNA storage. It is a \emph{reversible} preprocessing step that rearranges an $n$-letter string into runs of identical characters (by exploiting context regularities), resulting in highly compressible strings, and is the basis for the ubiquitous \texttt{bzip} program. ... more >>>

Kaave Hosseini, Shachar Lovett

The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role

in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c

applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem

with effective bounds.

more >>>

Mark Bun, Justin Thaler

We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight $\tilde{\Omega}(n^{1/2})$ lower bound on the threshold degree of the Surjectivity function on $n$ variables. This matches the best known threshold degree bound for any AC$^0$ ... more >>>

Mert Saglam

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... more >>>

Ryan O'Donnell, Rocco Servedio, Li-Yang Tan

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program.

more >>>Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study bounded depth $(\min, +)$ formulas computing the shortest path polynomial. For depth $2d$ with $d \geq 2$, we obtain lower bounds parametrized by certain fan-in restrictions on all $+$ gates except those at the bottom level. For depth $4$, in two regimes of the parameter, the bounds are ... more >>>

Michael Forbes, Zander Kelley

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

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

Craig Gentry, Charanjit Jutla

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

Ankit Garg, Rafael Oliveira

Scaling problems have a rich and diverse history, and thereby have found numerous

applications in several fields of science and engineering. For instance, the matrix scaling problem

has had applications ranging from theoretical computer science to telephone forecasting,

economics, statistics, optimization, among many other fields. Recently, a generalization of matrix

more >>>

Krishnamoorthy Dinesh, Jayalal Sarma

In this paper, we study the Boolean function parameters sensitivity ($\mathbf{s}$), block sensitivity ($\mathbf{bs}$), and alternation ($\mathbf{alt}$) under specially designed affine transforms and show several applications. For a function $f:\mathbb{F}_2^n \to \{0,1\}$, and $A = Mx+b$ for $M \in \mathbb{F}_2^{n \times n}$ and $b \in \mathbb{F}_2^n$, the result of the ... more >>>

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>

Stasys Jukna, Andrzej Lingas

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the ``amount of negation'' in such circuits, we introduce the concept of their ``negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give ... more >>>

Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... 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 >>>

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... more >>>

Anna Gal, Avishay Tal, Adrian Trejo Nuñez

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

Justin Holmgren, Ron Rothblum

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

Nikhil Gupta, Chandan Saha

In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:

$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$

where $d$ is a prime, $\mathbb{F}_d$ is the ...
more >>>

Stefan Dantchev, Nicola Galesi, Barnaby Martin

We investigate the size complexity of proofs in $RES(s)$ -- an extension of Resolution working on $s$-DNFs instead of clauses -- for families of contradictions given in the {\em unusual binary} encoding. A motivation of our work is size lower bounds of refutations in Resolution for families of contradictions in ... more >>>

Tayfun Pay, James Cox

We review some semantic and syntactic complexity classes that were introduced to better understand the relationship between complexity classes P and NP. We also define several new complexity classes, some of which are associated with Mersenne numbers, and show their location in the complexity hierarchy.

more >>>Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucky, Nitin Saurabh, Ronald de Wolf

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

Alex Samorodnitsky

Let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$ and let $q \ge 1$. We upper bound the $\ell_q$ norm of $T_{\epsilon} f$ by the average $\ell_q$ norm of conditional expectations of $f$, given sets of roughly ... more >>>

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,

the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.

This improves upon the previous work ...
more >>>

Nicola Galesi, Navid Talebanfard, Jacobo Toran

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

Oded Goldreich

Prior studies of testing graph properties presume that the tester can obtain uniformly distributed vertices in the tested graph (in addition to obtaining answers to the some type of graph-queries).

Here we envision settings in which it is only feasible to obtain random vertices drawn according to an arbitrary distribution ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

Eric Allender, Rahul Ilango, Neekon Vafa

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under “local” reductions computable in TIME($n^{0.49}$). The question of whether MCSP is NP-hard (or indeed, hard even for small subclasses of P) ... more >>>

Anastasiya Chistopolskaya, Vladimir Podolskii

We prove a new lower bound on the parity decision tree complexity $D_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $D_{\oplus}(f)\geq k+1$.

This lower bound is ... more >>>

Bruno Loff, Sagnik Mukhopadhyay

We show a deterministic simulation (or lifting) theorem for composed problems $f \circ EQ_n$ where the inner function (the gadget) is Equality on $n$ bits. When $f$ is a total function on $p$ bits, it is easy to show via a rank argument that the communication complexity of $f\circ EQ_n$ ... more >>>

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of $\Omega(\sqrt{n})$. This yields the first exponential gap between the logarithm of the ... more >>>

Alexander Knop

Most of the research in communication complexity theory is focused on the

fixed-partition model (in this model the partition of the input between

Alice and Bob is fixed). Nonetheless, the best-partition model (the model

that allows Alice and Bob to choose the partition) has a lot of

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

Dominik Scheder

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

We study the complexity of representing polynomials by arithmetic circuits in both the commutative and the non-commutative settings. Our approach goes through a precise understanding of the more restricted setting where multiplication is not associative, meaning that we distinguish $(xy)z$ from $x(yz)$.

Our first and main conceptual result is a ... more >>>

Giuseppe Persiano, Kevin Yeo

In this work, we study privacy-preserving storage primitives that are suitable for use in data analysis on outsourced databases within the differential privacy framework. The goal in differentially private data analysis is to disclose global properties of a group without compromising any individual’s privacy. Typically, differentially private adversaries only ever ... more >>>

Henry Corrigan-Gibbs, Dmitry Kogan

We study preprocessing algorithms for the function-inversion problem. In this problem, an algorithm gets oracle access to a function $f\colon[N] \to [N]$ and takes as input $S$ bits of auxiliary information about $f$, along with a point $y \in [N]$. After running for time $T$, the algorithm must output an ... more >>>

Dean Doron, Pooya Hatami, William Hoza

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

Iddo Tzameret, Stephen Cook

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>

Yonatan Nakar, Dana Ron

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>

Emanuele Viola

Let $f:\{0,1\}^{n}\to\{0,1\}^{m}$ be a function computable by a circuit with

unbounded fan-in, arbitrary gates, $w$ wires and depth $d$. With

a very simple argument we show that the $m$-query problem corresponding

to $f$ has data structures with space $s=n+r$ and time $(w/r)^{d}$,

for any $r$. As a consequence, in the ...
more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:

(1) Independence of $n$: There are testers ...
more >>>

Zeev Dvir, Alexander Golovnev, Omri Weinstein

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>

Ilias Diakonikolas, Daniel Kane

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.

It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions

(PTFs)

within the space of all bounded functions. In this paper, we prove a robust ...
more >>>

Shachar Lovett, Jiapeng Zhang

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

Neeraj Kayal, Chandan Saha

A homogeneous depth three circuit $C$ computes a polynomial

$$f = T_1 + T_2 + ... + T_s ,$$ where each $T_i$ is a product of $d$ linear forms in $n$ variables over some underlying field $\mathbb{F}$. Given black-box access to $f$, can we efficiently reconstruct (i.e. proper learn) a ...
more >>>

Alexander Golovnev, Alexander Kulikov

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

Nicollas Sdroievski, Murilo Silva, André Vignatti

We show that the Hidden Subgroup Problem for black-box groups is in $\mathrm{BPP}^\mathrm{MKTP}$ (where $\mathrm{MKTP}$ is the Minimum $\mathrm{KT}$ Problem) using the techniques of Allender et al (2018). We also show that the problem is in $\mathrm{ZPP}^\mathrm{MKTP}$ provided that there is a \emph{pac overestimator} computable in $\mathrm{ZPP}^\mathrm{MKTP}$ for the logarithm ... more >>>

Amir Yehudayoff

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing ... more >>>

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

Omri Ben-Eliezer

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

Andrej Bogdanov

We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula ... more >>>

Irit Dinur, Tali Kaufman, Noga Ron-Zewi

A local tester for an error-correcting code is a probabilistic procedure that queries a small subset of coordinates, accepts codewords with probability one, and rejects non-codewords with probability proportional to their distance from the code. The local tester is {\em robust} if for non-codewords it satisfies the stronger property that ... more >>>

Lijie Chen, Roei Tell

The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative ... more >>>

Ashutosh Kumar, Raghu Meka, Amit Sahai

In this work, we consider the natural goal of designing secret sharing schemes that ensure security against a powerful adaptive adversary who may learn some ``leaked'' information about all the shares. We say that a secret sharing scheme is $p$-party leakage-resilient, if the secret remains statistically hidden even after an ... more >>>

Anurag Anshu, Naresh Boddu, Dave Touchette

In a recent breakthrough result, Chattopadhyay, Mande and Sherif [ECCC TR18-17] showed an exponential separation between the log approximate rank and randomized communication complexity of a total function $f$, hence refuting the log approximate rank conjecture of Lee and Shraibman [2009]. We provide an alternate proof of their randomized communication ... more >>>

Xinyu Wu

After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people

(e.g. Ryan O’Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by

stochastic calculus. In this short note, we describe such a simplification.

Yael Kalai, Dakshita Khurana

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

Makrand Sinha, Ronald de Wolf

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total

Boolean function, the sink function, that has polynomial approximate rank and

polynomial randomized communication complexity. This gives an exponential

separation between randomized communication complexity and logarithm of the

approximate rank, refuting the log-approximate-rank conjecture. We show that ...
more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... more >>>

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>

Benny Applebaum, Prashant Nalini Vasudevan

In the *Conditional Disclosure of Secrets* (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies ... more >>>

Emanuele Viola

We prove that for every distribution $D$ on $n$ bits with Shannon

entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of

the bits $D_{i}$ can be predicted with advantage $\gamma$ by an

AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of

all the bits of $D$ except $D_{i}$. ...
more >>>

Karthik C. S., Pasin Manurangsi

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

Kshitij Gajjar, Jaikumar Radhakrishnan

We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

Prerona Chatterjee, Ramprasad Saptharishi

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>

Moni Naor, Merav Parter, Eylon Yogev

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>>