All reports in year 2017:

__
TR17-177
| 16th November 2017
__

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff#### On Communication Complexity of Classification Problems

__
TR17-176
| 15th November 2017
__

Kamil Khadiev, Aliya Khadiev, Alexander Knop#### Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

__
TR17-175
| 13th November 2017
__

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov#### Monotone Circuit Lower Bounds from Resolution

__
TR17-174
| 13th November 2017
__

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao#### On Expressing Majority as a Majority of Majorities

__
TR17-173
| 6th November 2017
__

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam#### An Average-Case Lower Bound against ACC^0

__
TR17-172
| 3rd November 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### From Laconic Zero-Knowledge to Public-Key Cryptography

__
TR17-171
| 6th November 2017
__

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal#### Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity

Revisions: 1

__
TR17-170
| 6th November 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Simulation Beats Richness: New Data-Structure Lower Bounds

__
TR17-169
| 24th October 2017
__

Mark Bun, Robin Kothari, Justin Thaler#### The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials

__
TR17-168
| 5th November 2017
__

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri#### Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Dierentially Private Sampling

Revisions: 1

__
TR17-167
| 3rd November 2017
__

Chin Ho Lee, Emanuele Viola#### More on bounded independence plus noise: Pseudorandom generators for read-once polynomials

__
TR17-166
| 3rd November 2017
__

Emanuele Viola#### A sampling lower bound for permutations

__
TR17-165
| 3rd November 2017
__

Toniann Pitassi, Robert Robere#### Lifting Nullstellensatz to Monotone Span Programs over Any Field

__
TR17-164
| 3rd November 2017
__

Scott Aaronson#### Shadow Tomography of Quantum States

__
TR17-163
| 2nd November 2017
__

Michael Forbes, Amir Shpilka#### A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits

__
TR17-162
| 26th October 2017
__

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson#### Barriers for Rank Methods in Arithmetic Complexity

__
TR17-161
| 30th October 2017
__

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

__
TR17-160
| 29th October 2017
__

Eli Ben-Sasson, Eden Saig#### Collaborative Discovery: A study of Guru-follower dynamics

Revisions: 1

__
TR17-159
| 28th October 2017
__

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri#### A $o(d) \cdot \text{polylog}~n$ Monotonicity Tester for Boolean Functions over the Hypergrid $[n]^d$

__
TR17-158
| 23rd October 2017
__

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan#### Minimum Circuit Size, Graph Isomorphism, and Related Problems

__
TR17-157
| 13th October 2017
__

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

__
TR17-156
| 15th October 2017
__

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan#### Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications

__
TR17-155
| 13th October 2017
__

Alessandro Chiesa, Tom Gur#### Proofs of Proximity for Distribution Testing

Revisions: 1

__
TR17-154
| 12th October 2017
__

Christoph Berkholz#### The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs

__
TR17-153
| 9th October 2017
__

Pranjal Dutta, Nitin Saxena, Amit Sinhababu#### Discovering the roots: Uniform closure results for algebraic classes under factoring

__
TR17-152
| 9th October 2017
__

Swagato Sanyal#### One-way Communication and Non-adaptive Decision Tree

__
TR17-151
| 8th October 2017
__

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere#### Stabbing Planes

__
TR17-150
| 26th September 2017
__

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs#### All Classical Adversary Methods are Equivalent for Total Functions

__
TR17-149
| 7th October 2017
__

Or Meir, Avi Wigderson#### Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 1

__
TR17-148
| 6th October 2017
__

Or Meir, Avishay Tal#### The Choice and Agreement Problems of a Random Function

Revisions: 1

__
TR17-147
| 3rd October 2017
__

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

__
TR17-146
| 1st October 2017
__

Or Meir#### On Derandomized Composition of Boolean Functions

Revisions: 1

__
TR17-145
| 19th September 2017
__

Roei Tell#### Quantified derandomization of linear threshold circuits

Revisions: 1

__
TR17-144
| 27th September 2017
__

Moritz Müller, Ján Pich#### Feasibly constructive proofs of succinct weak circuit lower bounds

__
TR17-143
| 26th September 2017
__

Tom Gur, Govind Ramnarayan, Ron Rothblum#### Relaxed Locally Correctable Codes

Revisions: 1

__
TR17-142
| 21st September 2017
__

Johan Hastad#### On small-depth Frege proofs for Tseitin for grids

__
TR17-141
| 19th September 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover

__
TR17-140
| 11th September 2017
__

Tong Qin, Osamu Watanabe#### An improvement of the algorithm of Hertli for the unique 3SAT problem

__
TR17-139
| 18th September 2017
__

Thomas Watson#### A ZPP^NP[1] Lifting Theorem

__
TR17-138
| 17th September 2017
__

Srikanth Srinivasan, Madhu Sudan#### Local decoding and testing of polynomials over grids

__
TR17-137
| 11th September 2017
__

Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde#### Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs

__
TR17-136
| 10th September 2017
__

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo#### Complete Classification of Generalized Santha-Vazirani Sources

__
TR17-135
| 10th September 2017
__

Ramprasad Saptharishi, Anamay Tengse#### Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees

Revisions: 1

__
TR17-134
| 8th September 2017
__

Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev#### Fast Reed-Solomon Interactive Oracle Proofs of Proximity

Revisions: 1

__
TR17-133
| 7th September 2017
__

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price#### Sample-Optimal Identity Testing with High Probability

__
TR17-132
| 7th September 2017
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Sharp Bounds for Generalized Uniformity Testing

__
TR17-131
| 1st September 2017
__

Joshua Grochow, Cris Moore#### Designing Strassen's algorithm

__
TR17-130
| 30th August 2017
__

Oded Goldreich, Guy Rothblum#### Worst-case to Average-case reductions for subclasses of P

__
TR17-129
| 27th August 2017
__

Or Meir#### An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds

Revisions: 7

__
TR17-128
| 15th August 2017
__

Or Meir#### The Direct Sum of Universal Relations

Revisions: 3
,
Comments: 1

__
TR17-127
| 12th August 2017
__

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi#### Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Revisions: 1

__
TR17-126
| 7th August 2017
__

Swastik Kopparty, Shubhangi Saraf#### Local Testing and Decoding of High-Rate Error-Correcting Codes

__
TR17-125
| 7th August 2017
__

Badih Ghazi, Pritish Kamath, Prasad Raghavendra#### Dimension Reduction for Polynomials over Gaussian Space and Applications

__
TR17-124
| 6th August 2017
__

Mrinal Kumar, Ben Lee Volk#### An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

Revisions: 2

__
TR17-123
| 2nd August 2017
__

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
TR17-122
| 28th July 2017
__

Rohit Gurjar, Ben Lee Volk#### Pseudorandom Bits for Oblivious Branching Programs

__
TR17-121
| 31st July 2017
__

Sumegha Garg, Ran Raz, Avishay Tal#### Extractor-Based Time-Space Lower Bounds for Learning

__
TR17-120
| 31st July 2017
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions

Revisions: 1

__
TR17-119
| 25th July 2017
__

Badih Ghazi, T.S. Jayram#### Resource-Efficient Common Randomness and Secret-Key Schemes

__
TR17-118
| 20th July 2017
__

Xiaotie Deng, Zhe Feng, Rucha Kulkarni#### Octahedral Tucker is PPA-Complete

__
TR17-117
| 20th July 2017
__

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

__
TR17-116
| 5th July 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Strong Lower Bounds for Space Bounded Learning

__
TR17-115
| 5th July 2017
__

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

__
TR17-114
| 1st July 2017
__

Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk#### Proper Learning of k-term DNF Formulas from Satisfying Assignments

__
TR17-113
| 1st July 2017
__

Andrej Bogdanov, Alon Rosen#### Pseudorandom Functions: Three Decades Later

__
TR17-112
| 27th June 2017
__

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

__
TR17-111
| 2nd June 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

__
TR17-110
| 22nd June 2017
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Axis-Parallel Tests for Tensor Product Codes

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR17-106
| 16th June 2017
__

Mateus de Oliveira Oliveira, Pavel Pudlak#### Representations of Monotone Boolean Functions by Linear Programs

__
TR17-105
| 14th June 2017
__

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden#### Pseudo-Deterministic Proofs

__
TR17-104
| 13th June 2017
__

Brett Hemenway, Noga Ron-Zewi, Mary Wootters#### Local List Recovery of High-rate Tensor Codes & Applications

__
TR17-103
| 12th June 2017
__

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Parameterized Property Testing of Functions

__
TR17-102
| 9th June 2017
__

Oded Goldreich#### Overview of the doubly-efficient interactive proof systems of RRR

__
TR17-101
| 8th June 2017
__

Oded Goldreich#### On the doubly-efficient interactive proof systems of GKR

__
TR17-100
| 7th June 2017
__

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

__
TR17-099
| 5th June 2017
__

Nir Bitansky, Omer Paneth, Yael Tauman Kalai#### Multi-Collision Resistance: A Paradigm for Keyless Hash Functions

Revisions: 1

__
TR17-098
| 28th May 2017
__

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee#### Understanding Deep Neural Networks with Rectified Linear Units

Revisions: 1

__
TR17-097
| 31st May 2017
__

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan#### Multi Collision Resistant Hash Functions and their Applications

Revisions: 1

__
TR17-096
| 30th May 2017
__

Irit Dinur, Inbal Livni Navon#### Exponentially Small Soundness for the Direct Product Z-test

__
TR17-095
| 26th May 2017
__

Ran Gelles, Yael Tauman Kalai#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR17-093
| 22nd May 2017
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Interactive Coding Over the Noisy Broadcast Channel

__
TR17-092
| 10th May 2017
__

Shuichi Hirahara#### A Duality Between Depth-Three Formulas and Approximation by Depth-Two

__
TR17-091
| 17th May 2017
__

Andrej Bogdanov#### Small bias requires large formulas

__
TR17-090
| 15th May 2017
__

Chin Ho Lee, Emanuele Viola#### The coin problem for product tests

__
TR17-089
| 11th May 2017
__

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

__
TR17-088
| 10th May 2017
__

Elena Grigorescu, Akash Kumar, Karl Wimmer#### K-Monotonicity is Not Testable on the Hypercube

__
TR17-087
| 9th May 2017
__

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar#### On Weak-Space Complexity over Complex Numbers

__
TR17-086
| 9th May 2017
__

C Ramya, Raghavendra Rao B V#### Linear Projections of the Vandermonde Polynomial

Revisions: 1

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR17-084
| 2nd May 2017
__

Iftach Haitner, Salil Vadhan#### The Many Entropies in One-Way Functions

__
TR17-083
| 5th May 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Weights at the Bottom Matter When the Top is Heavy

Revisions: 1

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR17-081
| 2nd May 2017
__

Badih Ghazi, Madhu Sudan#### The Power of Shared Randomness in Uncertain Communication

__
TR17-080
| 1st May 2017
__

Joshua Brakensiek, Venkatesan Guruswami#### The Quest for Strong Inapproximability Results with Perfect Completeness

__
TR17-079
| 1st May 2017
__

Alexander A. Sherstov, Pei Wu#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

__
TR17-078
| 21st April 2017
__

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski#### Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model

__
TR17-077
| 30th April 2017
__

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan#### Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees

__
TR17-076
| 21st April 2017
__

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee#### New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 2

__
TR17-075
| 29th April 2017
__

Clement Canonne, Ilias Diakonikolas, Alistair Stewart#### Fourier-Based Testing for Families of Distributions

Revisions: 1

__
TR17-074
| 29th April 2017
__

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S#### Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

__
TR17-073
| 28th April 2017
__

Eric Allender, Shuichi Hirahara#### New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

__
TR17-072
| 25th April 2017
__

Eric Allender, Andreas Krebs, Pierre McKenzie#### Better Complexity Bounds for Cost Register Machines

Revisions: 1

__
TR17-071
| 14th April 2017
__

Young Kun Ko, Arial Schvartzman#### Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

Revisions: 1

__
TR17-070
| 15th April 2017
__

Shachar Lovett, Sankeerth Rao, Alex Vardy#### Probabilistic Existence of Large Sets of Designs

__
TR17-069
| 17th April 2017
__

Jacob Steinhardt#### Does robustness imply tractability? A lower bound for planted clique in the semi-random model

__
TR17-068
| 20th April 2017
__

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie#### Settling the query complexity of non-adaptive junta testing

__
TR17-067
| 21st April 2017
__

Benny Applebaum#### Garbled Circuits as Randomized Encodings of Functions: a Primer

__
TR17-066
| 20th April 2017
__

Josh Alman, Joshua Wang, Huacheng Yu#### Cell-Probe Lower Bounds from Online Communication Complexity

Revisions: 1

__
TR17-065
| 20th April 2017
__

Boaz Barak#### The Complexity of Public-Key Cryptograph

__
TR17-064
| 20th April 2017
__

Venkatesan Guruswami, Chaoping Xing, chen yuan#### Subspace Designs based on Algebraic Function Fields

__
TR17-063
| 10th April 2017
__

Benny Applebaum#### Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

__
TR17-062
| 9th April 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Dual polynomials and communication complexity of XOR functions

__
TR17-061
| 3rd April 2017
__

Anat Ganor, Karthik C. S.#### Communication Complexity of Correlated Equilibrium in Two-Player Games

__
TR17-060
| 9th April 2017
__

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari#### Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

Revisions: 1

__
TR17-059
| 6th April 2017
__

Ola Svensson, Jakub Tarnawski#### The Matching Problem in General Graphs is in Quasi-NC

Revisions: 1

__
TR17-058
| 7th April 2017
__

Noga Alon, Omri Ben-Eliezer, Eldar Fischer#### Testing hereditary properties of ordered graphs and matrices

Revisions: 1

__
TR17-057
| 7th April 2017
__

Alessandro Chiesa, Michael Forbes, Nicholas Spooner#### A Zero Knowledge Sumcheck and its Applications

__
TR17-056
| 7th April 2017
__

Paul Goldberg, Christos Papadimitriou#### Towards a Unified Complexity Theory of Total Functions

__
TR17-055
| 26th March 2017
__

Maya Leshkowitz#### Round Complexity Versus Randomness Complexity in Interactive Proofs

__
TR17-054
| 22nd March 2017
__

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay#### Lifting randomized query complexity to randomized communication complexity

Revisions: 3

__
TR17-053
| 22nd March 2017
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for BPP

__
TR17-052
| 19th March 2017
__

Dieter van Melkebeek, Gautam Prakriya#### Derandomizing Isolation in Space-Bounded Settings

__
TR17-051
| 16th March 2017
__

Mark Bun, Justin Thaler#### A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

__
TR17-050
| 15th March 2017
__

Joe Boninger, Joshua Brody, Owen Kephart#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

__
TR17-049
| 14th March 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

__
TR17-048
| 14th March 2017
__

Pavel Hrubes, Pavel Pudlak#### A note on monotone real circuits

__
TR17-047
| 10th March 2017
__

Kasper Green Larsen, Omri Weinstein, Huacheng Yu#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

__
TR17-046
| 8th March 2017
__

Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk#### Learning Residual Alternating Automata

__
TR17-045
| 7th March 2017
__

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere#### Random CNFs are Hard for Cutting Planes

Revisions: 1

__
TR17-044
| 21st February 2017
__

Olaf Beyersdorff, Luke Hinde, Ján Pich#### Reasons for Hardness in QBF Proof Systems

Revisions: 1

__
TR17-043
| 3rd March 2017
__

Alexey Milovanov, Nikolay Vereshchagin#### Stochasticity in Algorithmic Statistics for Polynomial Time

__
TR17-042
| 6th March 2017
__

Pavel Hrubes, Pavel Pudlak#### Random formulas, monotone circuits, and interpolation

__
TR17-041
| 6th March 2017
__

Amnon Ta-Shma#### Explicit, almost optimal, epsilon-balanced codes

__
TR17-040
| 4th March 2017
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

__
TR17-039
| 28th February 2017
__

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan#### Average-Case Fine-Grained Hardness

__
TR17-038
| 23rd February 2017
__

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan#### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

__
TR17-037
| 25th February 2017
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Understanding Cutting Planes for QBFs

__
TR17-036
| 22nd February 2017
__

Dean Doron, Francois Le Gall, Amnon Ta-Shma#### Probabilistic logarithmic-space algorithms for Laplacian solvers

__
TR17-035
| 23rd February 2017
__

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

__
TR17-034
| 21st February 2017
__

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam#### On algebraic branching programs of small width

Revisions: 1

__
TR17-033
| 19th February 2017
__

Daniel Kane, Shachar Lovett, Sankeerth Rao#### Labeling the complete bipartite graph with no zero cycles

Revisions: 2

__
TR17-032
| 17th February 2017
__

Olaf Beyersdorff, Joshua Blinkhorn#### Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds

__
TR17-031
| 15th February 2017
__

Thomas Watson#### Quadratic Simulations of Merlin-Arthur Games

__
TR17-030
| 15th February 2017
__

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari#### An Improved Dictatorship Test with Perfect Completeness

__
TR17-029
| 18th February 2017
__

Clement Canonne, Tom Gur#### An Adaptivity Hierarchy Theorem for Property Testing

Revisions: 1

__
TR17-028
| 17th February 2017
__

Mrinal Kumar#### A quadratic lower bound for homogeneous algebraic branching programs

Revisions: 1

__
TR17-027
| 16th February 2017
__

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma#### A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate

__
TR17-026
| 17th February 2017
__

Valentine Kabanets, Daniel Kane, Zhenjian Lu#### A Polynomial Restriction Lemma with Applications

__
TR17-025
| 16th February 2017
__

Pooya Hatami, Avishay Tal#### Pseudorandom Generators for Low-Sensitivity Functions

__
TR17-024
| 16th February 2017
__

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for P^NP

__
TR17-023
| 15th February 2017
__

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich#### The Power of Natural Properties as Oracles

__
TR17-022
| 13th February 2017
__

Benjamin Rossman, Srikanth Srinivasan#### Separation of AC$^0[\oplus]$ Formulas and Circuits

__
TR17-021
| 11th February 2017
__

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas#### Reconstruction of full rank Algebraic Branching Programs

__
TR17-020
| 12th February 2017
__

Ran Raz#### A Time-Space Lower Bound for a Large Class of Learning Problems

__
TR17-019
| 8th February 2017
__

Andreas Krebs, Nutan Limaye, Michael Ludwig#### A Unified Method for Placing Problems in Polylogarithmic Depth

Revisions: 2

__
TR17-018
| 6th February 2017
__

Oded Goldreich, Guy Rothblum#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 3

__
TR17-017
| 5th February 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Lower Bounds for Space Bounded Learning

__
TR17-016
| 31st January 2017
__

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena#### Irreducibility and deterministic r-th root finding over finite fields

__
TR17-015
| 4th February 2017
__

Ilan Komargodski, Moni Naor, Eylon Yogev#### White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR17-012
| 17th January 2017
__

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau#### Emptiness Problems for Integer Circuits

__
TR17-011
| 22nd January 2017
__

Boaz Barak, Pravesh Kothari, David Steurer#### Quantum entanglement, sum of squares, and the log rank conjecture

__
TR17-010
| 18th January 2017
__

Xiaodi Wu, Penghui Yao, Henry Yuen#### Raz-McKenzie simulation with the inner product gadget

Revisions: 1

__
TR17-009
| 19th January 2017
__

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf#### Towards an algebraic natural proofs barrier via polynomial identity testing

__
TR17-008
| 14th January 2017
__

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan#### Low-Complexity Cryptographic Hash Functions

__
TR17-007
| 19th January 2017
__

Michael Forbes, Amir Shpilka, Ben Lee Volk#### Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

__
TR17-006
| 15th December 2016
__

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath#### Testing Ising Models

Revisions: 2

__
TR17-005
| 10th January 2017
__

Nir Bitansky#### Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs

Revisions: 3

__
TR17-004
| 8th January 2017
__

Scott Aaronson#### P=?NP

__
TR17-003
| 24th November 2016
__

Yi Deng#### Magic Adversaries Versus Individual Reduction: Science Wins Either Way

Revisions: 1

__
TR17-002
| 6th January 2017
__

Frantisek Duris#### Some notes on two lower bound methods for communication complexity

__
TR17-001
| 6th January 2017
__

Stephen Cook, Bruce Kapron#### A Survey of Classes of Primitive Recursive Functions

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>

Kamil Khadiev, Aliya Khadiev, Alexander Knop

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov

For any unsatisfiable CNF formula $F$ that is hard to refute in the Resolution proof system, we show that a gadget-composed version of $F$ is hard to refute in any proof system whose lines are computed by efficient communication protocols---or, equivalently, that a monotone function associated with $F$ has large ... more >>>

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

In a seminal work, Williams [Wil14] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC^0 circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known.

We show that there is a language L in NEXP (resp. EXP^NP) ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Since its inception, public-key encryption (PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal

We present an explicit pseudorandom generator with seed length $\tilde{O}((\log n)^{w+1})$ for read-once, oblivious, width $w$ branching programs that can read their input bits in any order. This improves upon the work of Impaggliazzo, Meka and Zuckerman (FOCS'12) where they required seed length $n^{1/2+o(1)}$.

A central ingredient in our work ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We develop a technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC'94) and Miltersen, Nisan, Safra and Wigderson (STOC'95). At the core of our technique is a novel simulation theorem: Alice gets a $p \times n$ ... more >>>

Mark Bun, Robin Kothari, Justin Thaler

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. The approximate degree of $f$ is known to be a lower bound on the quantum query complexity of $f$ (Beals et al., FOCS 1998 and ... more >>>

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

In his seminal work, Cleve [STOC 1986] has proved that any r-round coin-flipping protocol can be efficiently biassed by ?(1/r). The above lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner ... more >>>

Chin Ho Lee, Emanuele Viola

We construct pseudorandom generators with improved seed length for

several classes of tests. First we consider the class of read-once

polynomials over GF(2) in $m$ variables. For error $\e$ we obtain seed

length $\tilde O (\log(m/\e)) \log(1/\e)$, where $\tilde O$ hides lower-order

terms. This is optimal up to the factor ...
more >>>

Emanuele Viola

A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol

in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input

symbols in $[n]$. We show that the output distribution of a $d$-local

map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$

from a uniform permutation of $[n]$. This seems to be the ...
more >>>

Toniann Pitassi, Robert Robere

We characterize the size of monotone span programs computing certain "structured" boolean functions by the Nullstellensatz degree of a related unsatisfiable Boolean formula.

This yields the first exponential lower bounds for monotone span programs over arbitrary fields, the first exponential separations between monotone span programs over fields of different ... more >>>

Scott Aaronson

We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $\rho$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $\rho$ are needed to achieve this, ... more >>>

Michael Forbes, Amir Shpilka

In this paper we study the complexity of constructing a hitting set for $\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>>

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

Mark Braverman, Gil Cohen, Sumegha Garg

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

Eli Ben-Sasson, Eden Saig

Gurus are individuals who claim to possess mental powers of insight and prediction that far surpass those of the average person; they compete over followers, offering them insight in return for continued devotion. Followers wish to harness a (true) Guru’s predictive power but (i) have limited attention span and (ii) ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>

Eric Allender, Joshua Grochow, Dieter van Melkebeek, Cris Moore, Andrew Morgan

We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polynomially-related Kolmogorov measure. All prior reductions ... more >>>

Monaldo Mastrolilli

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

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

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

The complexity of Iterated Matrix Multiplication is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within $\mathrm{P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted $\mathrm{IMM}_{d}$, and show ... more >>>

Alessandro Chiesa, Tom Gur

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

Christoph Berkholz

We relate different approaches for proving the unsatisfiability of a system of real polynomial equations over Boolean variables. On the one hand, there are the static proof systems Sherali-Adams and sum-of-squares (a.k.a. Lasserre), which are based on linear and semi-definite programming relaxations. On the other hand, we consider polynomial calculus, ... more >>>

Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>

Swagato Sanyal

Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of ... more >>>

Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere

We introduce and develop a new semi-algebraic proof system, called Stabbing Planes that is in the style of DPLL-based modern SAT solvers. As with DPLL, there is only one rule: the current polytope can be subdivided by

branching on an inequality and its "integer negation.'' That is, we can (nondeterministically ...
more >>>

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions, and are equal to the fractional block sensitivity $\text{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Or Meir, Avishay Tal

The direct-sum question is a classical question that asks whether

performing a task on $m$ independent inputs is $m$ times harder

than performing it on a single input. In order to study this question,

Beimel et. al (Computational Complexity 23(1), 2014) introduced the following related problems:

* The choice ... more >>>

Venkatesan Guruswami, Rishi Saket

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

Or Meir

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$

is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$

and computes

\[

(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).

\]

This operation has been used several times for amplifying different

hardness measures of $f$ and $g$. This comes at a cost: the ...
more >>>

Roei Tell

One of the prominent current challenges in complexity theory is the attempt to prove lower bounds for $TC^0$, the class of constant-depth, polynomial-size circuits with majority gates. Relying on the results of Williams (2013), an appealing approach to prove such lower bounds is to construct a non-trivial derandomization algorithm for ... more >>>

Moritz Müller, Ján Pich

We ask for feasibly constructive proofs of known circuit lower bounds for explicit functions on bit strings of length $n$. In 1995 Razborov showed that many can be proved in Cook’s theory $PV_1$, a bounded arithmetic formalizing polynomial time reasoning. He formalized circuit lower bound statements for small $n$ of ... more >>>

Tom Gur, Govind Ramnarayan, Ron Rothblum

Locally decodable codes (LDCs) and locally correctable codes (LCCs) are error-correcting codes in which individual bits of the message and codeword, respectively, can be recovered by querying only few bits from a noisy codeword. These codes have found numerous applications both in theory and in practice.

A natural relaxation of ... more >>>

Johan Hastad

We prove that a small-depth Frege refutation of the Tseitin contradiction

on the grid requires subexponential size.

We conclude that polynomial size Frege refutations

of the Tseitin contradiction must use formulas of almost

logarithmic depth.

Joshua Brakensiek, Venkatesan Guruswami

We give a family of dictatorship tests with perfect completeness and low-soundness for 2-to-2 constraints. The associated 2-to-2 conjecture has been the basis of some previous inapproximability results with perfect completeness. However, evidence towards the conjecture in the form of integrality gaps even against weak semidefinite programs has been elusive. ... more >>>

Tong Qin, Osamu Watanabe

We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem.

more >>>Thomas Watson

The complexity class ZPP^NP[1] (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity.

For starters, we provide a new characterization: ZPP^NP[1] equals ... more >>>

Srikanth Srinivasan, Madhu Sudan

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate

polynomials of total degree at most $d$ over

grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form

error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$).

In this work we explore their local

decodability and local testability. ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde

As a natural extension of the SAT problem, different proof systems for quantified Boolean formulas (QBF) have been proposed. Many of these extend a propositional system to handle universal quantifiers.

By formalising the construction of the QBF proof system from a propositional proof system, by the addition of the ... more >>>

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Ramprasad Saptharishi, Anamay Tengse

We study the class of non-commutative Unambiguous circuits or Unique-Parse-Tree (UPT) circuits, and a related model of Few-Parse-Trees (FewPT) circuits (which were recently introduced by Lagarde, Malod and Perifel [LMP16] and Lagarde, Limaye and Srinivasan [LLS17]) and give the following constructions:

• An explicit hitting set of quasipolynomial size for ...
more >>>

Eli Ben-Sasson, Iddo Bentov, Ynon Horesh, Michael Riabzev

The family of Reed-Solomon (RS) codes plays a prominent role in the construction of quasilinear probabilistically checkable proofs (PCPs) and interactive oracle proofs (IOPs) with perfect zero knowledge and polylogarithmic verifiers. The large concrete computational complexity required to prove membership in RS codes is one of the biggest obstacles to ... more >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

We study the problem of testing identity against a given distribution (a.k.a. goodness-of-fit) with a focus on the high confidence regime. More precisely, given samples from an unknown distribution $p$ over $n$ elements, an explicitly given distribution $q$, and parameters $0< \epsilon, \delta < 1$, we wish to distinguish, {\em ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We study the problem of {\em generalized uniformity testing}~\cite{BC17} of a discrete probability distribution: Given samples from a probability distribution $p$ over an {\em unknown} discrete domain $\mathbf{\Omega}$, we want to distinguish, with probability at least $2/3$, between the case that $p$ is uniform on some {\em subset} of $\mathbf{\Omega}$ ... more >>>

Joshua Grochow, Cris Moore

In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with ... more >>>

Oded Goldreich, Guy Rothblum

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.

These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.

more >>>

Or Meir

One of the important challenges in circuit complexity is proving strong

lower bounds for constant-depth circuits. One possible approach to

this problem is to use the framework of Karchmer-Wigderson relations:

Karchmer and Wigderson (SIDMA 3(2), 1990) observed that for every Boolean

function $f$ there is a corresponding communication problem $\mathrm{KW}_{f}$,

more >>>

Or Meir

The universal relation is the communication problem in which Alice and Bob get as inputs two distinct strings, and they are required to find a coordinate on which the strings differ. The study of this problem is motivated by its connection to Karchmer-Wigderson relations, which are communication problems that are ... more >>>

Rohit Gurjar, Thomas Thierauf, Nisheeth Vishnoi

We deterministically construct quasi-polynomial weights in quasi-polynomial time, such that in a given polytope with totally unimodular constraints, one vertex is isolated, i.e., there is a unique minimum weight vertex.

More precisely,

the property that we need is that every face of the polytope lies in an affine space defined ...
more >>>

Swastik Kopparty, Shubhangi Saraf

We survey the state of the art in constructions of locally testable

codes, locally decodable codes and locally correctable codes of high rate.

Badih Ghazi, Pritish Kamath, Prasad Raghavendra

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>

Mrinal Kumar, Ben Lee Volk

We prove a lower bound of $\Omega(n^2/\log^2 n)$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial $f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of $\Omega(n^{4/3}/\log^2 n)$ for the same ... more >>>

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Rohit Gurjar, Ben Lee Volk

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior ... more >>>

Badih Ghazi, T.S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with ... more >>>

Xiaotie Deng, Zhe Feng, Rucha Kulkarni

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

Dmitry Itsykson, Alexander Knop

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

Michal Moshkovitz, Dana Moshkovitz

With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses ... more >>>

Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket

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

Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

In certain applications there may only be positive samples available to

to learn concepts of a class of interest,

and this has to be done properly, i.e. the

hypothesis space has to coincide with the concept class,

and without false positives, i.e. the hypothesis always has be a subset ...
more >>>

Andrej Bogdanov, Alon Rosen

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds.

In ... more >>>

Yehuda Lindell

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

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

A Boolean function $f:\{0,1\}^d \to \{0,1\}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadaptive, one-sided error unateness tester must make $\Omega(\frac{d}{\log d})$ queries. This result improves upon the $\Omega(\frac{d}{\log^2 d})$ lower bound for the same class of ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Mateus de Oliveira Oliveira, Pavel Pudlak

We introduce the notion of monotone linear programming circuits (MLP circuits), a model of

computation for partial Boolean functions. Using this model, we prove the following results:

1. MLP circuits are superpolynomially stronger than monotone Boolean circuits.

2. MLP circuits are exponentially stronger than monotone span programs.

3. ...
more >>>

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where

the verifier is guaranteed with high probability to output the same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

In this work, we give the first construction of {\em high-rate} locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block.

In particular, our construction gives the first {\em capacity-achieving} locally list-decodable ...
more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

Oded Goldreich

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).

Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system

in which the prover runs polynomial time ...
more >>>

Oded Goldreich

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).

Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ...
more >>>

Dakshita Khurana, Amit Sahai

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

Nir Bitansky, Omer Paneth, Yael Tauman Kalai

We study multi-collision-resistant hash functions --- a natural relaxation of collision-resistant hashing that only guarantees the intractability of finding many (rather than two) inputs that map to the same image. An appealing feature of such hash functions is that unlike their collision-resistant counterparts, they do not necessarily require a key. ... more >>>

Raman Arora, Amitabh Basu , Poorya Mianjy, Anirbit Mukherjee

In this paper we investigate the family of functions representable by deep neural networks (DNN) with rectified linear units (ReLU). We give the first-ever polynomial time (in the size of data) algorithm to train to global optimality a ReLU DNN with one hidden layer, assuming the input dimension and number ... more >>>

Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan

Collision resistant hash functions are functions that shrink their input, but for which it is computationally infeasible to find a collision, namely two strings that hash to the same value (although collisions are abundant).

In this work we study multi-collision resistant hash functions (MCRH) a natural relaxation of collision resistant ... more >>>

Irit Dinur, Inbal Livni Navon

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ...
more >>>

Ran Gelles, Yael Tauman Kalai

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

The paper investigates expansion properties of the Grassmann graph,

motivated by recent results of [KMS, DKKMS] concerning hardness

of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the

hypotheses put forward by these papers seems to first require a better

understanding of these expansion properties.

We consider the edge ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

A set of $n$ players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player ... more >>>

Shuichi Hirahara

We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the minimum size of depth-3 formulas is (up to a factor of n) equal to the inverse of the maximum, over all depth-2 formulas, of one-sided-error correlation ... more >>>

Andrej Bogdanov

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas ... more >>>

Chin Ho Lee, Emanuele Viola

Let $X_{m, \eps}$ be the distribution over $m$ bits $(X_1, \ldots, X_m)$

where the $X_i$ are independent and each $X_i$ equals $1$ with

probability $(1+\eps)/2$ and $0$ with probability $(1-\eps)/2$. We

consider the smallest value $\eps^*$ of $\eps$ such that the distributions

$X_{m,\eps}$ and $X_{m,0}$ can be distinguished with constant

more >>>

Irit Dinur, Tali Kaufman

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

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

Elena Grigorescu, Akash Kumar, Karl Wimmer

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates between $0$ and $1$ at most $k$ times on every ascending chain. Such functions represent a natural generalization ... more >>>

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>>

C Ramya, Raghavendra Rao B V

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

Iftach Haitner, Salil Vadhan

Computational analogues of information-theoretic notions have given rise to some of the most interesting phenomena in the theory of computation. For example, computational indistinguishability, Goldwasser and Micali '84, which is the computational analogue of statistical distance, enabled the bypassing of Shanon's impossibility results on perfectly secure encryption, and provided the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.

Moreover, the queries we use are comparison ...
more >>>

Badih Ghazi, Madhu Sudan

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect ... more >>>

Alexander A. Sherstov, Pei Wu

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

Nico Döttling, Jesper Buus Nielsen, Maceij Obremski

We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has ... more >>>

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse ... more >>>

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

We present new protocols for conditional disclosure of secrets (CDS),

where two parties want to disclose a secret to a third party if and

only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,

we present two protocols that achieve ...
more >>>

Clement Canonne, Ilias Diakonikolas, Alistair Stewart

We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and ... more >>>

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

Eric Allender, Shuichi Hirahara

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

Young Kun Ko, Arial Schvartzman

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper ... more >>>

Shachar Lovett, Sankeerth Rao, Alex Vardy

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

Jacob Steinhardt

We consider a robust analog of the planted clique problem. In this analog, a set $S$ of vertices is chosen and all edges in $S$ are included; then, edges between $S$ and the rest of the graph are included with probability $\frac{1}{2}$, while edges not touching $S$ are allowed to ... more >>>

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

We prove that any non-adaptive algorithm that tests whether an unknown

Boolean function $f\colon \{0, 1\}^n\to\{0, 1\} $ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ...
more >>>

Benny Applebaum

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of \emph{randomized encoding} (RE) of functions. We review old and new constructions of REs, present some lower bounds, and describe some applications. ... more >>>

Josh Alman, Joshua Wang, Huacheng Yu

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>>

Boaz Barak

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This is a survey that appeared in a book of surveys in honor of ... more >>>

Venkatesan Guruswami, Chaoping Xing, chen yuan

Subspace designs are a (large) collection of high-dimensional subspaces $\{H_i\}$ of $\F_q^m$ such that for any low-dimensional subspace $W$, only a small number of subspaces from the collection have non-trivial intersection with $W$; more precisely, the sum of dimensions of $W \cap H_i$ is at most some parameter $L$. The ... more >>>

Benny Applebaum

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,

we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. ...
more >>>

Anat Ganor, Karthik C. S.

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form ... more >>>

Ola Svensson, Jakub Tarnawski

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in $O(\log^3 n)$ time on $n^{O(\log^2 n)}$ processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the ... more >>>

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

We consider properties of edge-colored vertex-ordered graphs, i.e., graphs with a totally ordered vertex set and a finite set of possible edge colors. We show that any hereditary property of such graphs is strongly testable, i.e., testable with a constant number of queries.

We also explain how the proof can ...
more >>>

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

Paul Goldberg, Christos Papadimitriou

The complexity class TFNP is the set of {\em total function} problems that belong to NP: every input has at least one output and outputs are easy to check for validity, but it may be hard to find an output. TFNP is not believed to have complete problems, but it ... more >>>

Maya Leshkowitz

Consider an interactive proof system for some set S that has randomness complexity r(n) for instances of length n, and arbitrary round complexity. We show a public-coin interactive proof system for S of round complexity O(r(n)/log n). Furthermore, the randomness complexity is preserved up to a constant factor, and the ... more >>>

Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>

Dieter van Melkebeek, Gautam Prakriya

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by ... more >>>

Joe Boninger, Joshua Brody, Owen Kephart

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>>

Pavel Hrubes, Pavel Pudlak

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ...
more >>>

Sebastian Berndt, Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk

Residuality plays an essential role for learning finite automata.

While residual deterministic and nondeterministic

automata have been understood quite well, fundamental

questions concerning alternating automata (AFA) remain open.

Recently, Angluin, Eisenstat, and Fisman have initiated

a systematic study of residual AFAs and proposed an algorithm called AL*

-an extension of ...
more >>>

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

The random k-SAT model is the most important and well-studied distribution over

k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for

satisfiablity algorithms, and lastly average-case hardness over this distribution has also

been linked to hardness of approximation via Feige’s hypothesis. In this ...
more >>>

Olaf Beyersdorff, Luke Hinde, Ján Pich

We aim to understand inherent reasons for lower bounds for QBF proof systems and revisit and compare two previous approaches in this direction.

The first of these relates size lower bounds for strong QBF Frege systems to circuit lower bounds via strategy extraction (Beyersdorff & Pich, LICS'16). Here we ... more >>>

Alexey Milovanov, Nikolay Vereshchagin

A fundamental notion in Algorithmic Statistics is that of a stochastic object, i.e., an object having a simple plausible explanation. Informally, a probability distribution is a plausible explanation for $x$ if it looks likely that $x$ was drawn at random with respect to that distribution. In this paper, we ... more >>>

Pavel Hrubes, Pavel Pudlak

We prove new lower bounds on the sizes of proofs in the Cutting Plane proof system, using a concept that we call "unsatisfiability certificate". This approach is, essentially, equivalent to the well-known feasible interpolation method, but is applicable to CNF formulas that do not seem suitable for interpolation. Specifically, we ... more >>>

Amnon Ta-Shma

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\epsilon}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

Marshall Ball, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., ... more >>>

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

We define a cutting planes system CP+$\forall$red for quantified Boolean formulas (QBF) and analyse the proof-theoretic strength of this new calculus. While in the propositional case, Cutting Planes is of intermediate strength between resolution and Frege, our findings here show that the situation in QBF is slightly more complex: while ... more >>>

Dean Doron, Francois Le Gall, Amnon Ta-Shma

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system $L x=b$, where $L$ is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem.

more >>>

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

Daniel Kane, Shachar Lovett, Sankeerth Rao

Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over

any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn

We devise a new technique to prove lower bounds for the proof size in resolution-type calculi for quantified Boolean formulas (QBF). The new technique applies to the strong expansion system IR-calc and thereby also to the most studied QBF system Q-Resolution.

Our technique exploits a clear semantic paradigm, showing the ... more >>>

Thomas Watson

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic ... more >>>

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

A Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is called a dictator if it depends on exactly one variable i.e $f(x_1, x_2, \ldots, x_n) = x_i$ for some $i\in [n]$. In this work, we study a $k$-query dictatorship test. Dictatorship tests are central in proving many hardness results for constraint satisfaction problems.

... more >>>Clement Canonne, Tom Gur

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>>

Mrinal Kumar

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex $s$, and end vertex $t$ and each edge having a weight which is an affine form in $\F[x_1, x_2, \ldots, x_n]$. An ABP computes a polynomial in a natural way, as the sum of weights of ... more >>>

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma

We show a reduction from the existence of explicit t-non-malleable

extractors with a small seed length, to the construction of explicit

two-source extractors with small error for sources with arbitrarily

small constant rate. Previously, such a reduction was known either

when one source had entropy rate above half [Raz05] or ...
more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

A polynomial threshold function (PTF) of degree $d$ is a boolean function of the form $f=\mathrm{sgn}(p)$, where $p$ is a degree-$d$ polynomial, and $\mathrm{sgn}$ is the sign function. The main result of the paper is an almost optimal bound on the probability that a random restriction of a PTF is ... more >>>

Pooya Hatami, Avishay Tal

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP).

We obtain new circuit lower bounds, as well as some hardness results for the relativized version ...
more >>>

Benjamin Rossman, Srikanth Srinivasan

This paper gives the first separation between the power of {\em formulas} and {\em circuits} of equal depth in the $\mathrm{AC}^0[\oplus]$ basis (unbounded fan-in AND, OR, NOT and MOD$_2$ gates). We show, for all $d(n) \le O(\frac{\log n}{\log\log n})$, that there exist {\em polynomial-size depth-$d$ circuits} that are not equivalent ... more >>>

Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas

An algebraic branching program (ABP) A can be modelled as a product expression $X_1\cdot X_2\cdot \dots \cdot X_d$, where $X_1$ and $X_d$ are $1 \times w$ and $w \times 1$ matrices respectively, and every other $X_k$ is a $w \times w$ matrix; the entries of these matrices are linear forms ... more >>>

Ran Raz

We prove a general time-space lower bound that applies for a large class of learning problems and shows that for every problem in that class, any learning algorithm requires either a memory of quadratic size or an exponential number of samples.

Our result is stated in terms of the norm ... more >>>

Andreas Krebs, Nutan Limaye, Michael Ludwig

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem ... more >>>

Oded Goldreich, Guy Rothblum

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.

Specifically, such ...
more >>>

Michal Moshkovitz, Dana Moshkovitz

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>

Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

Ilan Komargodski, Moni Naor, Eylon Yogev

Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? If the graph is given explicitly, then it is possible to do so ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

Boaz Barak, Pravesh Kothari, David Steurer

For every constant $\epsilon>0$, we give an $\exp(\tilde{O}(\sqrt{n}))$-time algorithm for the $1$ vs $1-\epsilon$ Best Separable State (BSS) problem of distinguishing, given an $n^2\times n^2$ matrix $M$ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state $\rho$ that $M$ accepts with probability $1$, ... more >>>

Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>

Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan

Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is {\em collision resistant} hash functions (CRH), which prevent an efficient attacker from finding ... more >>>

Michael Forbes, Amir Shpilka, Ben Lee Volk

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

Given samples from an unknown multivariate distribution $p$, is it possible to distinguish whether $p$ is the product of its marginals versus $p$ being far from every product distribution? Similarly, is it possible to distinguish whether $p$ equals a given distribution $q$ versus $p$ and $q$ being far from each ... more >>>

Nir Bitansky

Verifiable random functions (VRFs) are pseudorandom functions where the owner of the seed, in addition to computing the function's value $y$ at any point $x$, can also generate a non-interactive proof $\pi$ that $y$ is correct (relative to so), without compromising pseudorandomness at other points. Being a natural primitive with ... more >>>

Scott Aaronson

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, ... more >>>

Yi Deng

We prove that \emph{at least} one of the following statements is true:

-- (Infinitely-often) Public-key encryption and key agreement can be based on injective one-way functions;

-- For every inverse polynomial $\epsilon$, the 4-round protocol from [Feige and Shamir, STOC 90] is distributional concurrent zero knowledge for any ...
more >>>

Frantisek Duris

We compare two methods for proving lower bounds on standard two-party model of communication complexity, the Rank method and Fooling set method. We present bounds on the number of functions $f(x,y)$, $x,y\in\{0,1\}^n$, with rank of size $k$ and fooling set of size at least k, $k\in [1,2^n]$. Using these bounds ... more >>>

Stephen Cook, Bruce Kapron

This paper is a transcription of mimeographed course notes titled ``A Survey of Classes of Primitive Recursive Functions", by S.A. Cook, for the University of California Berkeley course Math 290, Sect. 14, January 1967. The notes present a survey of subrecursive function

classes (and classes of relations based on these ...
more >>>