All reports in year 2015:

__
| 22nd June 2015 (removed)
__

Mario Szegedy#### An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game

__
TR15-001
| 2nd January 2015
__

Nir Bitansky, Omer Paneth, Alon Rosen#### On the Cryptographic Hardness of Finding a Nash Equilibrium

Revisions: 1

__
TR15-002
| 2nd January 2015
__

Mark Braverman, Rotem Oshman#### The Communication Complexity of Number-In-Hand Set Disjointness with No Promise

__
TR15-003
| 3rd January 2015
__

Oded Goldreich, Emanuele Viola, Avi Wigderson#### On Randomness Extraction in AC0

__
TR15-004
| 4th January 2015
__

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan#### On the Complexity of Noncommutative Polynomial Factorization

__
TR15-005
| 5th January 2015
__

Chin Ho Lee, Emanuele Viola#### Some limitations of the sum of small-bias distributions

Revisions: 1

__
TR15-006
| 6th January 2015
__

Nader Bshouty#### Dense Testers: Almost Linear Time and Locally Explicit Constructions

__
TR15-007
| 8th January 2015
__

Jonah Brown-Cohen, Prasad Raghavendra#### Combinatorial Optimization Algorithms via Polymorphisms

__
TR15-008
| 14th January 2015
__

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen#### The Power of Negations in Cryptography

Revisions: 1

__
TR15-009
| 16th January 2015
__

Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan#### Aggregate Pseudorandom Functions and Connections to Learning

Revisions: 1

__
TR15-010
| 19th January 2015
__

Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel#### Security Levels in Steganography -- Insecurity does not Imply Detectability

__
TR15-011
| 22nd January 2015
__

Subhash Khot, Dor Minzer, Muli Safra#### On Monotonicity Testing and Boolean Isoperimetric type Theorems

__
TR15-012
| 24th January 2015
__

Mika Göös#### Lower Bounds for Clique vs. Independent Set

__
TR15-013
| 28th January 2015
__

Subhash Khot, Igor Shinkar#### On Hardness of Approximating the Parameterized Clique Problem

__
TR15-014
| 18th January 2015
__

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Reliable Communication over Highly Connected Noisy Networks

__
TR15-015
| 30th January 2015
__

Neeraj Kayal, Chandan Saha#### Multi-$k$-ic depth three circuit lower bound

__
TR15-016
| 16th January 2015
__

Diptarka Chakraborty, Raghunath Tewari#### An $O(n^{\epsilon})$ Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

Revisions: 1

__
TR15-017
| 20th January 2015
__

Bruno Bauwens, Marius Zimand#### Linear list-approximation for short programs (or the power of a few random bits)

__
TR15-018
| 31st January 2015
__

Eric Allender, Ian Mertz#### Complexity of Regular Functions

Revisions: 1

__
TR15-019
| 3rd February 2015
__

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira#### Constructing Near Spanning Trees with Few Local Inspections

__
TR15-020
| 31st January 2015
__

Michael Viderman#### Explicit Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 3

__
TR15-021
| 5th February 2015
__

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf#### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

__
TR15-022
| 9th February 2015
__

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for non-commutative skew circuits

Revisions: 1

__
TR15-023
| 10th February 2015
__

Mark Braverman, Jon Schneider#### Information complexity is computable

__
TR15-024
| 16th February 2015
__

Oded Goldreich, Tom Gur, Ron Rothblum#### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

__
TR15-025
| 22nd February 2015
__

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff#### Teaching and compressing for low VC-dimension

__
TR15-026
| 21st February 2015
__

Siyao Guo, Ilan Komargodski#### Negation-Limited Formulas

Revisions: 1

__
TR15-027
| 25th February 2015
__

Benny Applebaum#### Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

__
TR15-028
| 27th February 2015
__

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland#### Relative Discrepancy does not separate Information and Communication Complexity

__
TR15-029
| 18th February 2015
__

Stanislav Zak#### Inherent logic and complexity

__
TR15-030
| 6th March 2015
__

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie#### ${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revisions: 1

__
TR15-031
| 2nd March 2015
__

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev#### Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

__
TR15-032
| 21st February 2015
__

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky#### Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

__
TR15-033
| 6th March 2015
__

Alexander Razborov#### An Ultimate Trade-Off in Propositional Proof Complexity

Revisions: 1

__
TR15-034
| 8th March 2015
__

Xin Li#### Three-Source Extractors for Polylogarithmic Min-Entropy

__
TR15-035
| 22nd February 2015
__

Sunil K S, Balagopal Komarath, Jayalal Sarma#### Comparator Circuits over Finite Bounded Posets

Revisions: 1

__
TR15-036
| 17th February 2015
__

David Gajser#### Verifying whether One-Tape Turing Machines Run in Linear Time

__
TR15-037
| 20th February 2015
__

Arnab Bhattacharyya, Palash Dey#### Sample Complexity for Winner Prediction in Elections

__
TR15-038
| 11th March 2015
__

Gil Cohen#### Local Correlation Breakers and Applications to Three-Source Extractors and Mergers

Revisions: 1

__
TR15-039
| 16th March 2015
__

Anup Rao, Makrand Sinha#### On Parallelizing Streaming Algorithms

__
TR15-040
| 24th March 2015
__

Shay Moran, Amir Yehudayoff#### Proper PAC learning is compressing

Revisions: 1

__
TR15-041
| 25th March 2015
__

Mark Bun, Justin Thaler#### Dual Polynomials for Collision and Element Distinctness

__
TR15-042
| 30th March 2015
__

Ilya Volkovich#### Computations beyond Exponentiation Gates and Applications

__
TR15-043
| 2nd April 2015
__

Alan Guo, Elad Haramaty, Madhu Sudan#### Robust testing of lifted codes with applications to low-degree testing

__
TR15-044
| 2nd April 2015
__

Timothy Gowers, Emanuele Viola#### The communication complexity of interleaved group products

Revisions: 1

__
TR15-045
| 1st April 2015
__

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz#### Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

Revisions: 1

__
TR15-046
| 2nd April 2015
__

Talya Eden, Amit Levi, Dana Ron#### Approximately Counting Triangles in Sublinear Time

Comments: 1

__
TR15-047
| 2nd April 2015
__

Swastik Kopparty, Mrinal Kumar, Michael Saks#### Efficient indexing of necklaces and irreducible polynomials over finite fields

__
TR15-048
| 14th February 2015
__

Kamil Khadiev#### Width Hierarchy for $k$-OBDD of Small Width

Revisions: 1

__
TR15-049
| 3rd April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### The Landscape of Communication Complexity Classes

Revisions: 1

__
TR15-050
| 4th April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Deterministic Communication vs. Partition Number

Revisions: 1

__
TR15-051
| 5th April 2015
__

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang#### Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterminsitic Reductions

Revisions: 2

__
TR15-052
| 6th April 2015
__

Partha Mukhopadhyay#### Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

__
TR15-053
| 7th April 2015
__

Massimo Lauria, Jakob Nordström#### Tight Size-Degree Bounds for Sums-of-Squares Proofs

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR15-055
| 13th April 2015
__

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

__
TR15-056
| 3rd April 2015
__

Sanjam Garg, Steve Lu, Rafail Ostrovsky#### Black-Box Garbled RAM

__
TR15-057
| 13th April 2015
__

Anup Rao, Makrand Sinha#### Simplified Separation of Information and Communication

Revisions: 3

__
TR15-058
| 1st April 2015
__

Peng Cui#### Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion

__
TR15-059
| 10th April 2015
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Feasible Interpolation for QBF Resolution Calculi

__
TR15-060
| 14th April 2015
__

Omri Weinstein#### Information Complexity and the Quest for Interactive Compression

Revisions: 1

__
TR15-061
| 14th April 2015
__

Benny Applebaum, Jonathan Avron, Christina Brzuska#### Arithmetic Cryptography

Revisions: 1

__
TR15-062
| 15th April 2015
__

Sangxia Huang#### $2^{(\log N)^{1/4-o(1)}}$ Hardness for Hypergraph Coloring

Revisions: 2

__
TR15-063
| 15th April 2015
__

Clement Canonne#### A Survey on Distribution Testing: Your Data is Big. But is it Blue?

Revisions: 1

__
TR15-064
| 19th April 2015
__

Ilan Komargodski, Pravesh Kothari, Madhu Sudan#### Communication with Contextual Uncertainty

Revisions: 1

__
TR15-065
| 18th April 2015
__

Benjamin Rossman, Rocco Servedio, Li-Yang Tan#### An average-case depth hierarchy theorem for Boolean circuits

__
TR15-066
| 20th April 2015
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### The Classification of Reversible Bit Operations

__
TR15-067
| 21st April 2015
__

Pavel Hrubes#### On hardness of multilinearization, and VNP completeness in characteristics two

__
TR15-068
| 21st April 2015
__

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf#### High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

Revisions: 2

__
TR15-069
| 21st April 2015
__

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat#### On Fortification of General Games

Revisions: 1

__
TR15-070
| 22nd April 2015
__

Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe#### Information Complexity Density and Simulation of Protocols

Revisions: 1

__
TR15-071
| 23rd April 2015
__

Mrinal Kumar, Shubhangi Saraf#### Sums of products of polynomials in few variables : lower bounds and polynomial identity testing

__
TR15-072
| 23rd April 2015
__

Roei Tell#### On Being Far from Far and on Dual Problems in Property Testing

Revisions: 4

__
TR15-073
| 25th April 2015
__

Neeraj Kayal, Chandan Saha#### Lower Bounds for Sums of Products of Low arity Polynomials

__
TR15-074
| 29th April 2015
__

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

__
TR15-075
| 29th April 2015
__

Eshan Chattopadhyay, Vipul Goyal, Xin Li#### Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Revisions: 1

__
TR15-076
| 28th April 2015
__

Mahdi Cheraghchi, Piotr Indyk#### Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

__
TR15-077
| 4th May 2015
__

Arnab Bhattacharyya, Abhishek Bhowmick#### Using higher-order Fourier analysis over general fields

__
TR15-078
| 4th May 2015
__

Mladen Mikša, Jakob Nordström#### A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds

__
TR15-079
| 7th May 2015
__

Oded Goldreich, Avishay Tal#### Matrix Rigidity of Random Toeplitz Matrices

__
TR15-080
| 7th May 2015
__

Noam Ta-Shma#### A simple proof of the Isolation Lemma

__
TR15-081
| 12th May 2015
__

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette#### Near-optimal bounds on bounded-round quantum communication complexity of disjointness

__
TR15-082
| 13th May 2015
__

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright#### Beating the random assignment on constraint satisfaction problems of bounded degree

__
TR15-083
| 14th May 2015
__

Omri Weinstein, David Woodruff#### The Simultaneous Communication of Disjointness with Applications to Data Streams

__
TR15-084
| 21st May 2015
__

Or Ordentlich, Ofer Shayevitz, Omri Weinstein#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

__
TR15-085
| 23rd May 2015
__

Irit Dinur, Prahladh Harsha, Guy Kindler#### Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

__
TR15-086
| 28th May 2015
__

Jop Briet#### On Embeddings of $\ell_1^k$ from Locally Decodable Codes

__
TR15-087
| 30th May 2015
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Communication Complexity of Permutation-Invariant Functions

__
TR15-088
| 31st May 2015
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Communication and External Information

__
TR15-089
| 31st May 2015
__

Eldar Fischer, Oded Lachish, Yadu Vadusev#### Trading query complexity for sample-based testing and multi-testing scalability}

__
TR15-090
| 1st June 2015
__

Alexander Kozachinsky#### On Slepian--Wolf Theorem with Interaction

Revisions: 1

__
TR15-091
| 3rd June 2015
__

Joshua Brody, Mario Sanchez#### Dependent Random Graphs and Multiparty Pointer Jumping

__
TR15-092
| 31st May 2015
__

Yael Tauman Kalai, Ilan Komargodski#### Compressing Communication in Distributed Protocols

Revisions: 2

__
TR15-093
| 5th June 2015
__

Aviad Rubinstein#### Inapproximability of Nash Equilibrium

__
TR15-094
| 10th June 2015
__

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi#### On Public Key Encryption from Noisy Codewords

__
TR15-095
| 14th June 2015
__

Gil Cohen#### Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs

__
TR15-096
| 5th June 2015
__

Abhishek Bhowmick, Shachar Lovett#### Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

__
TR15-097
| 16th June 2015
__

Marek Karpinski#### Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

__
TR15-098
| 15th June 2015
__

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs#### Separations in Query Complexity Based on Pointer Functions

Revisions: 2

__
TR15-099
| 12th June 2015
__

Ruiwen Chen#### Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

__
TR15-100
| 16th June 2015
__

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran#### Succinct Encodings of Graph Isomorphism

__
TR15-101
| 15th June 2015
__

Patrick Scharpfenecker#### On the structure of Solution-Graphs for Boolean Formulas

Revisions: 2

__
TR15-102
| 22nd June 2015
__

Mario Szegedy#### An $O(n^{0.4732})$ upper bound on the complexity of the GKS communication game

__
TR15-104
| 13th May 2015
__

Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont#### Streaming Property Testing of Visibly Pushdown Languages

Revisions: 2

__
TR15-105
| 21st June 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Towards a Characterization of Approximation Resistance for Symmetric CSPs

__
TR15-106
| 22nd June 2015
__

Itay Berman, Iftach Haitner, Aris Tentes#### Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

__
TR15-107
| 21st June 2015
__

Sagnik Mukhopadhyay, Swagato Sanyal#### Towards Better Separation between Deterministic and Randomized Query Complexity

__
TR15-108
| 30th June 2015
__

Shalev Ben-David#### A Super-Grover Separation Between Randomized and Quantum Query Complexities

__
TR15-109
| 1st July 2015
__

Mrinal Kumar, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth-5 circuits over finite fields

__
TR15-110
| 8th July 2015
__

Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf#### High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

Revisions: 1

__
TR15-111
| 8th July 2015
__

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky#### Low Distortion Embedding from Edit to Hamming Distance using Coupling

Revisions: 1

__
TR15-112
| 16th July 2015
__

Ruiwen Chen, Rahul Santhanam#### Improved Algorithms for Sparse MAX-SAT and MAX-$k$-CSP

__
TR15-113
| 9th July 2015
__

Amit Chakrabarti, Tony Wirth#### Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

__
TR15-114
| 18th July 2015
__

Avishay Tal#### #SAT Algorithms from Shrinkage

__
TR15-115
| 20th July 2015
__

Ilya Volkovich#### A Guide to Learning Arithmetic Circuits

__
TR15-116
| 21st July 2015
__

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky#### Efficient Low-Redundancy Codes for Correcting Multiple Deletions

__
TR15-117
| 21st July 2015
__

Boris Bukh, Venkatesan Guruswami#### An improved bound on the fraction of correctable deletions

Revisions: 1

__
TR15-118
| 23rd July 2015
__

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan#### The shifted partial derivative complexity of Elementary Symmetric Polynomials

__
TR15-119
| 23rd July 2015
__

Eshan Chattopadhyay, David Zuckerman#### Explicit Two-Source Extractors and Resilient Functions

Revisions: 4

__
TR15-120
| 12th July 2015
__

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi#### Understanding PPA-Completeness

Revisions: 1

__
TR15-121
| 25th July 2015
__

Xin Li#### Extractors for Affine Sources with Polylogarithmic Entropy

__
TR15-122
| 29th July 2015
__

Shiteng Chen, Periklis Papakonstantinou#### Correlation lower bounds from correlation upper bounds

__
TR15-123
| 31st July 2015
__

Xi Chen, Igor Carboni Oliveira, Rocco Servedio#### Addition is exponentially harder than counting for shallow monotone circuits

__
TR15-124
| 3rd August 2015
__

Vikraman Arvind, Pushkar Joglekar, Raja S#### Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

__
TR15-125
| 5th August 2015
__

Xin Li#### Improved Constructions of Two-Source Extractors

Revisions: 2

__
TR15-126
| 27th July 2015
__

Jacob Steinhardt, Gregory Valiant, Stefan Wager#### Memory, Communication, and Statistical Queries

Revisions: 1

__
TR15-127
| 7th August 2015
__

Stasys Jukna, Georg Schnitger#### On the Optimality of Bellman--Ford--Moore Shortest Path Algorithm

Revisions: 1

__
TR15-128
| 10th August 2015
__

Roee David, Elazar Goldenberg, Robert Krauthgamer#### Local Reconstruction of Low-Rank Matrices and Subspaces

Revisions: 2

__
TR15-129
| 7th August 2015
__

Alex Samorodnitsky#### On the entropy of a noisy function

Revisions: 1

__
TR15-130
| 11th August 2015
__

Ronald de Haan#### An Overview of Non-Uniform Parameterized Complexity

__
TR15-131
| 10th August 2015
__

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson#### Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions

__
TR15-132
| 13th August 2015
__

Daniel Reichman, Igor Shinkar#### On Percolation and NP-Hardness

Revisions: 2

__
TR15-133
| 12th August 2015
__

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew#### Lower bounds: from circuits to QBF proof systems

__
TR15-134
| 19th August 2015
__

Fu Li, Iddo Tzameret, Zhengyu Wang#### Characterizing Propositional Proofs as Non-Commutative Formulas

__
TR15-135
| 19th August 2015
__

Arnab Bhattacharyya, Palash Dey#### Fishing out Winners from Vote Streams

Revisions: 1

__
TR15-136
| 28th July 2015
__

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama#### A Satisfiability Algorithm for Depth-2 Circuits with a Symmetric Gate at the Top and AND Gates at the Bottom

__
TR15-137
| 22nd August 2015
__

Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito#### On the Role of Shared Randomness in Simultaneous Communication

__
TR15-138
| 25th August 2015
__

Michal Koucky#### Nonuniform catalytic space and the direct sum for space

Revisions: 1

__
TR15-139
| 25th August 2015
__

Eli Ben-Sasson, Gal Maor#### Lower bound for communication complexity with no public randomness

__
TR15-140
| 26th August 2015
__

Adam Case, Jack H. Lutz, Donald Stull#### Reachability Problems for Continuous Chemical Reaction Networks

__
TR15-141
| 26th August 2015
__

Pushkar Joglekar, Aravind N.R.#### On the expressive power of read-once determinants

__
TR15-142
| 28th August 2015
__

Srikanth Srinivasan#### A Compression Algorithm for $AC^0[\oplus]$ circuits using Certifying Polynomials

__
TR15-143
| 31st August 2015
__

Benjamin Rossman#### The Average Sensitivity of Bounded-Depth Formulas

__
TR15-144
| 1st September 2015
__

Raghu Meka#### Explicit resilient functions matching Ajtai-Linial

Revisions: 1

__
TR15-145
| 5th September 2015
__

Eric Allender, Asa Goodwillie#### Arithmetic circuit classes over Zm

__
TR15-146
| 7th September 2015
__

Elette Boyle, Moni Naor#### Is There an Oblivious RAM Lower Bound?

Revisions: 1

__
TR15-147
| 8th September 2015
__

Alexander A. Sherstov#### The Power of Asymmetry in Constant-Depth Circuits

__
TR15-148
| 9th September 2015
__

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

__
TR15-149
| 8th September 2015
__

Mohammad Hajiabadi, Bruce Kapron#### Gambling, Computational Information, and Encryption Security

__
TR15-150
| 13th September 2015
__

Gaurav Sinha#### Reconstruction of $\Sigma\Pi\Sigma(2)$ Circuits over Reals

Revisions: 3

__
TR15-151
| 14th September 2015
__

Eshan Chattopadhyay, David Zuckerman#### New Extractors for Interleaved Sources

Revisions: 1

__
TR15-152
| 16th September 2015
__

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla#### Are Short Proofs Narrow? QBF Resolution is not Simple.

__
TR15-153
| 21st September 2015
__

Tim Roughgarden#### Computing Equilibria: A Computational Complexity Perspective

__
TR15-154
| 22nd September 2015
__

Neeraj Kayal, Vineet Nair, Chandan Saha#### Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

__
TR15-155
| 22nd September 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Nearly Optimal NP-Hardness of Unique Coverage

__
TR15-156
| 21st September 2015
__

Tim Roughgarden#### Communication Complexity (for Algorithm Designers)

__
TR15-157
| 1st September 2015
__

Thomas O'Neil#### Representation-Independent Fixed Parameter Tractability for Vertex Cover and Weighted Monotone Satisfiability

__
TR15-158
| 27th September 2015
__

Ofer Grossman, Dana Moshkovitz#### Amplification and Derandomization Without Slowdown

__
TR15-159
| 28th September 2015
__

Juraj Hromkovic#### Why the Concept of Computational Complexity is Hard for Verifiable Mathematics

__
TR15-160
| 30th September 2015
__

Clement Canonne#### Are Few Bins Enough: Testing Histogram Distributions

Revisions: 1

__
TR15-161
| 24th September 2015
__

Chaoping Xing, chen yuan#### A new class of rank-metric codes and their list decoding beyond the unique decoding radius

__
TR15-162
| 9th October 2015
__

Eric Allender, Joshua Grochow, Cris Moore#### Graph Isomorphism and Circuit Size

Revisions: 1

__
TR15-163
| 11th October 2015
__

James Aisenberg, Maria Luisa Bonet, Sam Buss#### 2-D Tucker is PPA complete

__
TR15-164
| 13th October 2015
__

Pavel Hrubes, Amir Yehudayoff#### On isoperimetric profiles and computational complexity

__
TR15-165
| 14th October 2015
__

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson#### Towards Optimal Deterministic Coding for Interactive Communication

Revisions: 1

__
TR15-166
| 17th October 2015
__

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov#### A better-than-$3n$ lower bound for the circuit complexity of an explicit function

Revisions: 1

__
TR15-167
| 15th October 2015
__

Mika Göös, T.S. Jayram#### A Composition Theorem for Conical Juntas

__
TR15-168
| 18th October 2015
__

Gillat Kol#### Interactive Compression for Product Distributions

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR15-170
| 26th October 2015
__

Alexander Golovnev, Alexander Kulikov#### Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds

__
TR15-171
| 28th October 2015
__

Joshua Grochow#### Monotone projection lower bounds from extended formulation lower bounds

Revisions: 2
,
Comments: 1

__
TR15-172
| 3rd November 2015
__

Benny Applebaum, Shachar Lovett#### Algebraic Attacks against Random Local Functions and Their Countermeasures

Revisions: 1

__
TR15-173
| 29th October 2015
__

Martin Schwarz#### An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

__
TR15-174
| 18th October 2015
__

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Complexity of distributions and average-case hardness

__
TR15-175
| 5th November 2015
__

Scott Aaronson, Shalev Ben-David, Robin Kothari#### Separations in query complexity using cheat sheets

__
TR15-176
| 6th November 2015
__

Vikraman Arvind, Raja S#### Some Lower Bound Results for Set-Multilinear Arithmetic Computations

Revisions: 1

__
TR15-177
| 9th November 2015
__

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

__
TR15-178
| 10th November 2015
__

Eshan Chattopadhyay, Xin Li#### Extractors for Sumset Sources

__
TR15-179
| 10th November 2015
__

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett#### Affine-malleable Extractors, Spectrum Doubling, and Application to Privacy Amplification

__
TR15-180
| 4th November 2015
__

Bo Tang, Jiapeng Zhang#### Barriers to Black-Box Constructions of Traitor Tracing Systems

__
TR15-181
| 13th November 2015
__

Neeraj Kayal, Chandan Saha, Sébastien Tavenas#### On the size of homogeneous and of depth four formulas with low individual degree

__
TR15-182
| 13th November 2015
__

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

__
TR15-183
| 16th November 2015
__

Gil Cohen#### Non-Malleable Extractors - New Tools and Improved Constructions

__
TR15-184
| 21st November 2015
__

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk#### Identity Testing and Lower Bounds for Read-$k$ Oblivious Algebraic Branching Programs

__
TR15-185
| 24th November 2015
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for constant query affine-invariant LCCs and LTCs

__
TR15-186
| 24th November 2015
__

Benny Applebaum, Pavel Raykov#### On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings

__
TR15-187
| 24th November 2015
__

Nir Bitansky, Vinod Vaikuntanathan#### A Note on Perfect Correctness by Derandomization

Revisions: 1

__
TR15-188
| 24th November 2015
__

Daniel Kane, Ryan Williams#### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

__
TR15-189
| 25th November 2015
__

Shay Moran, Cyrus Rashtchian#### Shattered Sets and the Hilbert Function

Revisions: 1

__
TR15-190
| 2nd November 2015
__

Esther Ezra, Shachar Lovett#### On the Beck-Fiala Conjecture for Random Set Systems

__
TR15-191
| 26th November 2015
__

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan#### Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

__
TR15-192
| 26th November 2015
__

Ruiwen Chen, Rahul Santhanam#### Satisfiability on Mixed Instances

__
TR15-193
| 26th November 2015
__

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket#### On the hardness of learning sparse parities

__
TR15-194
| 30th November 2015
__

Mrinal Kumar, Shubhangi Saraf#### Arithmetic circuits with locally low algebraic rank

Revisions: 1

__
TR15-195
| 3rd December 2015
__

Robin Kothari#### Nearly optimal separations between communication (or query) complexity and partitions

__
TR15-196
| 4th December 2015
__

Andris Ambainis#### Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Revisions: 1

__
TR15-197
| 7th December 2015
__

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Constant-rate coding for multiparty interactive communication is impossible

__
TR15-198
| 30th November 2015
__

Shuichi Hirahara, Osamu Watanabe#### Limits of Minimum Circuit Size Problem as Oracle

Revisions: 1

__
TR15-199
| 7th December 2015
__

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan#### Relaxed partition bound is quadratically tight for product distributions

__
TR15-200
| 4th December 2015
__

Andris Ambainis#### Almost quadratic gap between partition complexity and query/communication complexity

Revisions: 1

__
TR15-201
| 10th December 2015
__

C Ramya, Raghavendra Rao B V#### Limitations of sum of products of Read-Once Polynomials

Revisions: 1

__
TR15-202
| 11th December 2015
__

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah#### Building above read-once polynomials: identity testing and hardness of representation

__
TR15-203
| 13th December 2015
__

Scott Aaronson, Shalev Ben-David#### Sculpting Quantum Speedups

__
TR15-204
| 14th December 2015
__

Meena Mahajan, Anuj Tawari#### Sums of read-once formulas: How many summands suffice?

Revisions: 2

__
TR15-205
| 15th December 2015
__

Emanuele Viola#### Quadratic maps are hard to sample

__
TR15-206
| 15th December 2015
__

Benny Applebaum, Pavel Raykov#### From Private Simultaneous Messages to Zero-Information Arthur-Merlin Protocols and Back

__
TR15-207
| 23rd December 2015
__

Ofer Grossman#### Finding Primitive Roots Pseudo-Deterministically

__
TR15-208
| 26th December 2015
__

Shafi Goldwasser, Ofer Grossman#### Perfect Bipartite Matching in Pseudo-Deterministic $RNC$

Revisions: 2

__
TR15-209
| 29th December 2015
__

Eli Ben-Sasson, Gal Maor#### On the information leakage of public-output protocols

Mario Szegedy

Nir Bitansky, Omer Paneth, Alon Rosen

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and injective one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which ... more >>>

Mark Braverman, Rotem Oshman

Set disjointness is one of the most fundamental problems in communication complexity. In the multi-party number-in-hand version of set disjointness, $k$ players receive private inputs $X_1,\ldots,X_k\subseteq \{1,\ldots,n\}$, and their goal is to determine whether or not $\bigcap_{i = 1}^k X_i = \emptyset$. In this paper we prove a tight lower ... more >>>

Oded Goldreich, Emanuele Viola, Avi Wigderson

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>>

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\ldots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following.

Although $\mathbb{F}\langle x_1,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in ... more >>>

Chin Ho Lee, Emanuele Viola

We exhibit $\epsilon$-biased distributions $D$

on $n$ bits and functions $f\colon \{0,1\}^n

\to \{0,1\}$ such that the xor of two independent

copies ($D+D$) does not fool $f$, for any of the

following choices:

1. $\epsilon = 2^{-\Omega(n)}$ and $f$ is in P/poly;

2. $\epsilon = 2^{-\Omega(n/\log n)}$ and $f$ is ... more >>>

Nader Bshouty

We develop a new notion called {\it $(1-\epsilon)$-tester for a

set $M$ of functions} $f:A\to C$. A $(1-\epsilon)$-tester

for $M$ maps each element $a\in A$ to a finite number of

elements $B_a=\{b_1,\ldots,b_t\}\subset B$ in a smaller

sub-domain $B\subset A$ where for every $f\in M$ if

$f(a)\not=0$ then $f(b)\not=0$ for at ...
more >>>

Jonah Brown-Cohen, Prasad Raghavendra

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP $\Lambda$ is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to ... more >>>

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

The study of monotonicity and negation complexity for Boolean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be ... more >>>

Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

In the first part of this work, we introduce a new type of pseudo-random function for which ``aggregate queries'' over exponential-sized sets can be efficiently answered. An example of an aggregate query may be the product of all function values belonging to an exponential-sized interval, or the sum of all ... more >>>

Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel

This paper takes a fresh look at security notions for steganography --

the art of encoding secret messages into unsuspicious covertexts

such that an adversary cannot distinguish the resulting stegotexts from original covertexts.

Stegosystems that fulfill the security notion used so far, however, are quite inefficient.

This ...
more >>>

Subhash Khot, Dor Minzer, Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we

give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function

$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from

being monotone ...
more >>>

Mika Göös

We prove an $\omega(\log n)$ lower bound on the conondeterministic communication complexity of the Clique vs. Independent Set problem introduced by Yannakakis (STOC 1988, JCSS 1991). As a corollary, this implies superpolynomial lower bounds for the Alon--Saks--Seymour conjecture in graph theory. Our approach is to first exhibit a query complexity ... more >>>

Subhash Khot, Igor Shinkar

In the $Gap-clique(k, \frac{k}{2})$ problem, the input is an $n$-vertex graph $G$, and the goal is to decide whether $G$ contains a clique of size $k$ or contains no clique of size $\frac{k}{2}$. It is an open question in the study of fixed parameterized tractability whether the $Gap-clique(k, \frac{k}{2})$ problem ... more >>>

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

the presence of random noise. Given an $n$-party protocol that takes $R$

rounds assuming noiseless communication, the goal is to find a coding

scheme that takes $R'$ rounds and computes the same function with high

probability even when the ...
more >>>

Neeraj Kayal, Chandan Saha

In a multi-$k$-ic depth three circuit every variable appears in at most $k$ of the linear polynomials in every product gate of the circuit. This model is a natural generalization of multilinear depth three circuits that allows the formal degree of the circuit to exceed the number of underlying variables ... more >>>

Diptarka Chakraborty, Raghunath Tewari

Given a graph $G$ and two vertices $s$ and $t$ in it, {\em graph reachability} is the problem of checking whether there exists a path from $s$ to $t$ in $G$. We show that reachability in directed layered planar graphs can be decided in polynomial time and $O(n^\epsilon)$ space, for ... more >>>

Bruno Bauwens, Marius Zimand

A $c$-short program for a string $x$ is a description of $x$ of length at most $C(x) + c$, where $C(x)$ is the Kolmogorov complexity of $x$. We show that there exists a randomized algorithm that constructs a list of $n$ elements that contains a $O(\log n)$-short program for $x$. ... more >>>

Eric Allender, Ian Mertz

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

Nisan (STOC 1991) exhibited a polynomial which is computable by linear sized non-commutative circuits but requires exponential sized non-commutative algebraic branching programs. Nisan's hard polynomial is in fact computable by linear sized skew circuits (skew circuits are circuits where every multiplication gate has the property that all but one of ... more >>>

Mark Braverman, Jon Schneider

The information complexity of a function $f$ is the minimum amount of information Alice and Bob need to exchange to compute the function $f$. In this paper we provide an algorithm for approximating the information complexity of an arbitrary function $f$ to within any additive error $\alpha>0$, thus resolving an ... more >>>

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and

for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ...
more >>>

Siyao Guo, Ilan Komargodski

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>

Benny Applebaum

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that ... more >>>

Stanislav Zak

Abstract. The old intuitive question "what does the machine think" at

different stages of its computation is examined. Our paper is based on

the formal de nitions and results which are collected in the branching

program theory around the intuitive question "what does the program

know about the contents of ...
more >>>

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>>

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

Color refinement is a classical technique used to show that two given graphs $G$ and $H$

are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph $G$ amenable to color refinement if the color-refinement procedure succeeds in distinguishing $G$ from any non-isomorphic ...
more >>>

Alexander Razborov

We exhibit an unusually strong trade-off between resolution proof width and tree-like proof size. Namely, we show that for any parameter $k=k(n)$ there are unsatisfiable $k$-CNFs that possess refutations of width $O(k)$, but such that any tree-like refutation of width $n^{1-\epsilon}/k$ must necessarily have {\em double} exponential size $\exp(n^{\Omega(k)})$. Conceptually, ... more >>>

Xin Li

We continue the study of constructing explicit extractors for independent

general weak random sources. The ultimate goal is to give a construction that matches what is given by the probabilistic method --- an extractor for two independent $n$-bit weak random sources with min-entropy as small as $\log n+O(1)$. Previously, the ...
more >>>

Sunil K S, Balagopal Komarath, Jayalal Sarma

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

David Gajser

We discuss the following family of problems, parameterized by integers $C\geq 2$ and $D\geq 1$: Does a given one-tape non-deterministic $q$-state Turing machine make at most $Cn+D$ steps on all computations on all inputs of length $n$, for all $n$?

Assuming a fixed tape and input alphabet, we show that ... more >>>

Arnab Bhattacharyya, Palash Dey

Predicting the winner of an election is a favorite problem both for news media pundits and computational social choice theorists. Since it is often infeasible to elicit the preferences of all the voters in a typical prediction scenario, a common algorithm used for winner prediction is to run the election ... more >>>

Gil Cohen

We introduce and construct a pseudorandom object which we call a local correlation breaker (LCB). Informally speaking, an LCB is a function that gets as input a sequence of $r$ (arbitrarily correlated) random variables and an independent weak-source. The output of the LCB is a sequence of $r$ random variables ... more >>>

Anup Rao, Makrand Sinha

We study the complexity of parallelizing streaming algorithms (or equivalently, branching programs). If $M(f)$ denotes the minimum average memory required to compute a function $f(x_1,x_2, \dots, x_n)$ how much memory is required to compute $f$ on $k$ independent streams that arrive in parallel? We show that when the inputs (updates) ... more >>>

Shay Moran, Amir Yehudayoff

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.

In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ...
more >>>

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{2/3})$ lower bounds on ... more >>>

Ilya Volkovich

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.

Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).

In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.

That is, beyond an exponentiation gate. As ...
more >>>

Alan Guo, Elad Haramaty, Madhu Sudan

A local tester for a code probabilistically looks at a given word at a small set of coordinates and based on this local view accepts codewords with probability one while rejecting words far from the code with constant probabilility. A local tester for a code is said to be ``robust'' ... more >>>

Timothy Gowers, Emanuele Viola

Alice receives a tuple $(a_1,\ldots,a_t)$ of $t$ elements

from the group $G = \text{SL}(2,q)$. Bob similarly

receives a tuple $(b_1,\ldots,b_t)$. They are promised

that the interleaved product $\prod_{i \le t} a_i b_i$

equals to either $g$ and $h$, for two fixed elements $g,h

\in G$. Their task is to decide ...
more >>>

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

A one-way function is $d$-local if each of its outputs depends on at most $d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was shown that, under relatively mild assumptions, there exist $4$-local one-way functions (OWFs). This result is not far from optimal as it is not hard ... more >>>

Talya Eden, Amit Levi, Dana Ron

We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in two models: Exact counting algorithms, which require reading the entire graph, and streaming algorithms, where the edges are given in a stream and the memory is limited. In this work ... more >>>

Swastik Kopparty, Mrinal Kumar, Michael Saks

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

Kamil Khadiev

In this paper was explored well known model $k$-OBDD. There are proven width based hierarchy of classes of boolean functions which computed by $k$-OBDD. The proof of hierarchy is based on sufficient condition of Boolean function's non representation as $k$-OBDD and complexity properties of Boolean

function SAF. This function is ...
more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on ... more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple ... more >>>

Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, Guang Yang

A circuit $C$ \emph{compresses} a function $f:\{0,1\}^n\rightarrow \{0,1\}^m$ if given an input $x\in \{0,1\}^n$ the circuit $C$ can shrink $x$ to a shorter $\ell$-bit string $x'$ such that later, a computationally-unbounded solver $D$ will be able to compute $f(x)$ based on $x'$. In this paper we study the existence of ... more >>>

Partha Mukhopadhyay

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of

depth-4 circuits. Such circuits compute polynomials of the following type:

$

C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},

$

where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the ...
more >>>

Massimo Lauria, Jakob Nordström

We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size n^{Omega(d)} for values of d = d(n) from constant all the way up to n^{delta} for some universal constant delta. This shows that ... more >>>

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model

where agent's valuations are unknown to the central planner, and therefore communication is required to determine an

efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ...
more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We study the relationship between communication and information in 2-party communication protocols when the information is asymmetric. If $I^A$ denotes the number of bits of information revealed by the first party, $I^B$ denotes the information revealed by the second party, and $C$ is the number of bits of communication in ... more >>>

Sanjam Garg, Steve Lu, Rafail Ostrovsky

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

Anup Rao, Makrand Sinha

We give an example of a boolean function whose information complexity is exponentially

smaller than its communication complexity. Our result simplifies recent work of Ganor, Kol and

Raz (FOCS'14, STOC'15).

Peng Cui

In this paper, the author puts forward a variation of Feige's Hypothesis, which claims that it is hard on average refuting Unbalanced Max 3-XOR under biased assignments on a natural distribution. Under this hypothesis, the author strengthens the previous known hardness for approximating Minimum Unique Game, $5/4-\epsilon$, by proving that ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

In sharp contrast to classical proof complexity we are currently short of lower bound techniques for QBF proof systems. In this paper we establish the feasible interpolation technique for all resolution-based QBF systems, whether modelling CDCL or expansion-based solving. This both provides the first general lower bound method for QBF ... more >>>

Omri Weinstein

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is ... more >>>

Benny Applebaum, Jonathan Avron, Christina Brzuska

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a ... more >>>

Sangxia Huang

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with ... more >>>

Clement Canonne

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, ... more >>>

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

Benjamin Rossman, Rocco Servedio, Li-Yang Tan

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every $d \geq 2$, there is an explicit $n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula, which is such that any depth-$(d-1)$ ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post's lattice, a central result in mathematical ... more >>>

Pavel Hrubes

For a boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$, let $\hat{f}$ be the unique multilinear polynomial such that $f(x)=\hat{f}(x)$ holds for every $x\in \{0,1\}^n$. We show that, assuming $\hbox{VP}\not=\hbox{VNP}$, there exists a polynomial-time computable $f$ such that $\hat{f}$ requires super-polynomial arithmetic circuits. In fact, this $f$ can be taken as a monotone 2-CNF, ... more >>>

Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant ... more >>>

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

A recent result of Moshkovitz~\cite{Moshkovitz14} presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in \cite{Moshkovitz14} to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel ... more >>>

Himanshu Tyagi, Shaileshh Venkatakrishnan , Pramod Viswanath, Shun Watanabe

A simulation of an interactive protocol entails the use of an interactive communication to produce the output of the protocol to within a fixed statistical distance $\epsilon$. Recent works in the TCS community have propagated that the information complexity of the protocol plays a central role in characterizing the minimum ... more >>>

Mrinal Kumar, Shubhangi Saraf

We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$

such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables.

Roei Tell

For a set $\Pi$ in a metric space and $\delta>0$, denote by $\mathcal{F}_\delta(\Pi)$ the set of elements that are $\delta$-far from $\Pi$. In property testing, a $\delta$-tester for $\Pi$ is required to accept inputs from $\Pi$ and reject inputs from $\mathcal{F}_\delta(\Pi)$. A natural dual problem is the problem of $\delta$-testing ... more >>>

Neeraj Kayal, Chandan Saha

We prove an exponential lower bound for expressing a polynomial as a sum of product of low arity polynomials. Specifically, we show that for the iterated matrix multiplication polynomial, $IMM_{d, n}$ (corresponding to the product of $d$ matrices of size $n \times n$ each), any expression of the form

more >>>

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

Eshan Chattopadhyay, Vipul Goyal, Xin Li

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

Mahdi Cheraghchi, Piotr Indyk

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

Arnab Bhattacharyya, Abhishek Bhowmick

Higher-order Fourier analysis, developed over prime fields, has been recently used in different areas of computer science, including list decoding, algorithmic decomposition and testing. We extend the tools of higher-order Fourier analysis to analyze functions over general fields. Using these new tools, we revisit the results in the above areas.

... more >>>Mladen Mikša, Jakob Nordström

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>>

Oded Goldreich, Avishay Tal

We prove that random $n$-by-$n$ Toeplitz (alternatively Hankel) matrices over $GF(2)$ have rigidity $\Omega(\frac{n^3}{r^2\log n})$ for rank $r \ge \sqrt{n}$, with high probability. This improves, for $r = o(n/\log n \log\log n)$, over the $\Omega(\frac{n^2}{r} \cdot\log(\frac{n}{r}))$ bound that is known for many explicit matrices.

Our result implies that the explicit ... more >>>

Noam Ta-Shma

We give a new simple proof for the Isolation Lemma, with slightly better parameters, that also gives non-trivial results even when the weight domain $m$ is smaller than the number of variables $n$.

more >>>Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

Omri Weinstein, David Woodruff

We study $k$-party set disjointness in the simultaneous message-passing model, and show that even if each element $i\in[n]$ is guaranteed to either belong to all $k$ parties or to at most $O(1)$ parties in expectation (and to at most $O(\log n)$ parties with high probability), then $\Omega(n \min(\log 1/\delta, \log ... more >>>

Or Ordentlich, Ofer Shayevitz, Omri Weinstein

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... more >>>

Irit Dinur, Prahladh Harsha, Guy Kindler

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

Jop Briet

We show that any $q$-query locally decodable code (LDC) gives a copy of $\ell_1^k$ with small distortion in the Banach space of $q$-linear forms on $\ell_{p_1}^N\times\cdots\times\ell_{p_q}^N$, provided $1/p_1 + \cdots + 1/p_q \leq 1$ and where $k$, $N$, and the distortion are simple functions of the code parameters. We exhibit ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

Eldar Fischer, Oded Lachish, Yadu Vadusev

We show here that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query ... more >>>

Alexander Kozachinsky

In this paper we study interactive ``one-shot'' analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable $X$, Bob receives a value of another random variable $Y$ that is jointly distributed with $X$. Alice's goal is to transmit $X$ to Bob (with some error probability $\varepsilon$). ... more >>>

Joshua Brody, Mario Sanchez

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs dependent random graphs. Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. ... more >>>

Yael Tauman Kalai, Ilan Komargodski

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

Aviad Rubinstein

We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions.

As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete ... more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ivan Bjerre Damgard, Yuval Ishai, Noga Ron-Zewi

Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of inverting noisy linear encodings. These schemes are limited in that they either require the underlying field to grow with the security parameter, ... more >>>

Gil Cohen

In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $2\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>>

Abhishek Bhowmick, Shachar Lovett

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

Marek Karpinski

We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>>

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized

query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree

of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. ...
more >>>

Ruiwen Chen

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

Patrick Scharpfenecker

In this work we extend the study of solution graphs and prove that for boolean formulas in a class called CPSS, all connected components are partial cubes of small dimension, a statement which was proved only for some cases in [Schwerdtfeger 2013]. In contrast, we show that general Schaefer formulas ... more >>>

Mario Szegedy

We give an $5\cdot n^{\log_{30}5}$ upper bund on the complexity of the communication game introduced by G. Gilmer, M. Kouck\'y and M. Saks \cite{saks} to study the Sensitivity Conjecture \cite{linial}, improving on their

$\sqrt{999\over 1000}\sqrt{n}$ bound. We also determine the exact complexity of the game up to $n\le 9$.

more >>>

Nathanaël François, Frederic Magniez, Olivier Serre, Michel de Rougemont

In the context of language recognition, we demonstrate the superiority of streaming property testers against streaming algorithms and property testers, when they are not combined. Initiated by Feigenbaum et al, a streaming property tester is a streaming algorithm recognizing a language under the property testing approximation: it must distinguish inputs ... more >>>

Venkatesan Guruswami, Euiwoong Lee

A Boolean constraint satisfaction problem (CSP) is called approximation resistant if independently setting variables to $1$ with some probability $\alpha$ achieves the best possible approximation ratio for the fraction of constraints satisfied. We study approximation resistance of a natural subclass of CSPs that we call Symmetric Constraint Satisfaction Problems (SCSPs), ... more >>>

Itay Berman, Iftach Haitner, Aris Tentes

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>>

Sagnik Mukhopadhyay, Swagato Sanyal

We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$

and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$. This refutes the conjecture made by

Saks and Wigderson that for any Boolean ...
more >>>

Shalev Ben-David

We construct a total Boolean function $f$ satisfying

$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing

conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions.

Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions,

we improve this to $R(f)=\tilde{\Omega}(Q(f)^3)$.

Our construction is motivated by the Göös-Pitassi-Watson function

but does not ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi

In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in N\}$ of polynomials in $VNP$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, ... more >>>

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

An error correcting code is said to be \emph{locally testable} if

there is a test that checks whether a given string is a codeword,

or rather far from the code, by reading only a small number of symbols

of the string. Locally testable codes (LTCs) are both interesting

in their ...
more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings $x,y$ lying in the Boolean hypercube. The edit distance between $x$ and $y$ is defined as the minimum number of character insertion, deletion, and bit flips needed for converting $x$ into $y$. ...
more >>>

Ruiwen Chen, Rahul Santhanam

We give improved deterministic algorithms solving sparse instances of MAX-SAT and MAX-$k$-CSP. For instances with $n$ variables and $cn$ clauses (constraints), we give algorithms running in time $\poly(n)\cdot 2^{n(1-\mu)}$ for

\begin{itemize}

\item $\mu = \Omega(\frac{1}{c} )$ and polynomial space solving MAX-SAT and MAX-$k$-SAT,

\item $\mu = \Omega(\frac{1}{\sqrt{c}} )$ and ...
more >>>

Amit Chakrabarti, Tony Wirth

Set cover, over a universe of size $n$, may be modelled as a

data-streaming problem, where the $m$ sets that comprise the instance

are to be read one by one. A semi-streaming algorithm is allowed only

$O(n \text{ poly}\{\log n, \log m\})$ space to process this ...
more >>>

Avishay Tal

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>

Ilya Volkovich

An \emph{arithmetic circuit} is a directed acyclic graph in which the operations are $\{+,\times\}$.

In this paper, we exhibit several connections between learning algorithms for arithmetic circuits and other problems.

In particular, we show that:

\begin{enumerate}

\item Efficient learning algorithms for arithmetic circuit classes imply explicit exponential lower bounds.

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

Boris Bukh, Venkatesan Guruswami

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

Hervé Fournier, Nutan Limaye, Meena Mahajan, Srikanth Srinivasan

We continue the study of the shifted partial derivative measure, introduced by Kayal (ECCC 2012), which has been used to prove many strong depth-4 circuit lower bounds starting from the work of Kayal, and that of Gupta et al. (CCC 2013).

We show a strong lower bound on the dimension ... more >>>

Eshan Chattopadhyay, David Zuckerman

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ... more >>>

Xiaotie Deng, Zhe Feng, Zhengyang Liu, Qi Qi

The search complexity classes {\bf PPA} and {\bf PPAD} were proposed by Papadimitriou twenty years ago for characterizing the computational difficulties of many interesting natural search problems. While many members in the complete class of {\bf PPAD}, {\bf PPAD}-completeness, are established in the past twenty years, the understanding of the ... more >>>

Xin Li

We give the first explicit construction of deterministic extractors for affine sources over $F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>

Shiteng Chen, Periklis Papakonstantinou

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

Xi Chen, Igor Carboni Oliveira, Rocco Servedio

Let $U_{k,N}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $a^{(1)} + \cdots + a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a monotone unweighted threshold gate, i.e., the Boolean function which takes ... more >>>

Vikraman Arvind, Pushkar Joglekar, Raja S

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and

$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some

striking connections to classical formal language theory. Our main

results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>

Xin Li

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$.

... more >>>Jacob Steinhardt, Gregory Valiant, Stefan Wager

If a concept class can be represented with a certain amount of memory, can it be efficiently learned with the same amount of memory? What concepts can be efficiently learned by algorithms that extract only a few bits of information from each example? We introduce a formal framework for studying ... more >>>

Stasys Jukna, Georg Schnitger

We prove a general lower bound on the size of branching programs over any semiring of zero characteristic, including the (min,+) semiring. Using it, we show that the classical dynamic programming algorithm of Bellman, Ford and Moore for the shortest s-t path problem is optimal, if only Min and Sum ... more >>>

Roee David, Elazar Goldenberg, Robert Krauthgamer

We study the problem of \emph{reconstructing a low-rank matrix}, where the input is an $n\times m$ matrix $M$ over a field $\mathbb{F}$ and the goal is to reconstruct a (near-optimal) matrix $M'$ that is low-rank and close to $M$ under some distance function $\Delta$.

Furthermore, the reconstruction must be local, ...
more >>>

Alex Samorodnitsky

Let $f$ be a nonnegative function on $\{0,1\}^n$. We upper bound the entropy of the image of $f$ under the noise operator with noise parameter $\epsilon$ by the average entropy of conditional expectations of $f$, given sets of roughly $(1-2\epsilon)^2 \cdot n$ variables.

As an application, we show that for ... more >>>

Ronald de Haan

We consider several non-uniform variants of parameterized complexity classes that have been considered in the literature. We do so in a homogenous notation, allowing a clear comparison of the various variants. Additionally, we consider some novel (non-uniform) parameterized complexity classes that come up in the framework of parameterized knowledge compilation. ... more >>>

Parikshit Gopalan, Noam Nisan, Rocco Servedio, Kunal Talwar, Avi Wigderson

A natural measure of smoothness of a Boolean function is its sensitivity (the largest number of Hamming neighbors of a point which differ from it in function value). The structure of smooth or equivalently low-sensitivity functions is still a mystery. A well-known conjecture states that every such Boolean function can ... more >>>

Daniel Reichman, Igor Shinkar

We consider the robustness of computational hardness of problems

whose input is obtained by applying independent random deletions to worst-case instances.

For some classical NP-hard problems on graphs, such as Coloring, Vertex-Cover, and Hamiltonicity, we examine the complexity of these problems when edges (or vertices) of an arbitrary

graph are ...
more >>>

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

A general and long-standing belief in the proof complexity community asserts that there is a close connection between progress in lower bounds for Boolean circuits and progress in proof size lower bounds for strong propositional proof systems. Although there are famous examples where a transfer from ideas and techniques from ... more >>>

Fu Li, Iddo Tzameret, Zhengyu Wang

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

Arnab Bhattacharyya, Palash Dey

We investigate the problem of winner determination from computational social choice theory in the data stream model. Specifically, we consider the task of summarizing an arbitrarily ordered stream of $n$ votes on $m$ candidates into a small space data structure so as to be able to obtain the winner determined ... more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

In this paper, we present a moderately exponential time algorithm for the circuit satisfiability problem of

depth-2 unbounded-fan-in circuits with an arbitrary symmetric gate at the top and AND gates at the bottom.

As a special case, we obtain an algorithm for the maximum satisfiability problem that runs in ...
more >>>

Mohammad Bavarian, Dmitry Gavinsky, Tsuyoshi Ito

Two parties wish to carry out certain distributed computational tasks, and they are given access to a source of correlated random bits.

It allows the parties to act in a correlated manner, which can be quite useful.

But what happens if the shared randomness is not perfect?

In this work, ... more >>>

Michal Koucky

This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has ... more >>>

Eli Ben-Sasson, Gal Maor

We give a self contained proof of a logarithmic lower bound on the communication complexity of any non redundant function, given that there is no access to shared randomness. This bound was first stated in Yao's seminal paper [STOC 1979], but no full proof appears in the literature.

Our proof ... more >>>

Adam Case, Jack H. Lutz, Donald Stull

Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced a new model of chemical kinetics, rate-independent continuous CRNs ... more >>>

Pushkar Joglekar, Aravind N.R.

We introduce and study the notion of read-$k$ projections of the determinant: a polynomial $f \in \mathbb{F}[x_1, \ldots, x_n]$ is called a {\it read-$k$ projection of determinant} if $f=det(M)$, where entries of matrix $M$ are either field elements or variables such that each variable appears at most $k$ times in ... more >>>

Srikanth Srinivasan

A recent work of Chen, Kabanets, Kolokolova, Shaltiel and Zuckerman (CCC 2014, Computational Complexity 2015) introduced the Compression problem for a class $\mathcal{C}$ of circuits, defined as follows. Given as input the truth table of a Boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ that has a small (say size $s$) circuit from ... more >>>

Benjamin Rossman

We show that unbounded fan-in boolean formulas of depth $d+1$ and size $s$ have average sensitivity $O(\frac{1}{d}\log s)^d$. In particular, this gives a tight $2^{\Omega(d(n^{1/d}-1))}$ lower bound on the size of depth $d+1$ formulas computing the PARITY function. These results strengthen the corresponding $2^{\Omega(n^{1/d})}$ and $O(\log s)^d$ bounds for circuits ... more >>>

Raghu Meka

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... more >>>

Eric Allender, Asa Goodwillie

We continue the study of the complexity classes VP(Zm) and LambdaP(Zm) which was initiated in [AGM15]. We distinguish between “strict” and “lax” versions of these classes and prove some new equalities and inclusions between these arithmetic circuit classes and various subclasses of ACC^1.

more >>>Elette Boyle, Moni Naor

An Oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (JACM 1996), is a (probabilistic) RAM that hides its access pattern, i.e. for every input the observed locations accessed are similarly distributed. Great progress has been made in recent years in minimizing the overhead of ORAM constructions, with the goal of ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. Introduced

in the seminal work of Minsky and Papert (1969), this notion is central to

some of the strongest algorithmic and complexity-theoretic results for

more >>>

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>

Mohammad Hajiabadi, Bruce Kapron

We revisit the question, originally posed by Yao (1982), of whether encryption security may be characterized using computational information. Yao provided an affirmative answer, using a compression-based notion of computational information to give a characterization equivalent to the standard computational notion of semantic security. We give two other equivalent characterizations. ... more >>>

Gaurav Sinha

Reconstruction of arithmertic circuits has been heavily studied in the past few years and has connections to proving lower bounds and deterministic identity testing. In this paper we present a polynomial time randomized algorithm for reconstructing $\Sigma\Pi\Sigma(2)$ circuits over $\R$, i.e. depth$-3$ circuits with fan-in $2$ at the top addition ... more >>>

Eshan Chattopadhyay, David Zuckerman

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,

explicit extractors for $2$-interleaved sources on $\{ ...
more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

The groundbreaking paper `Short proofs are narrow - resolution made simple' by Ben-Sasson and Wigderson (J. ACM 2001) introduces what is today arguably the main technique to obtain resolution lower bounds: to show a lower bound for the width of proofs. Another important measure for resolution is space, and in ... more >>>

Tim Roughgarden

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

... more >>>Neeraj Kayal, Vineet Nair, Chandan Saha

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following:

1. There exists an explicit $n$-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

Tim Roughgarden

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at

Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

Thomas O'Neil

A symmetric representation for a set of objects requires the same amount of space for the set as for its complement. Complexity classifications that are based on the length of the input can depend on whether the representation is symmetric. In this article we describe a symmetric representation scheme for ... more >>>

Ofer Grossman, Dana Moshkovitz

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>

Juraj Hromkovic

Mathematics was developed as a strong research instrument with fully verifiable argumentations. We call any formal theory based on syntactic rules that enables to algorithmically verify for any given text whether it is a proof or not algorithmically verifiable mathematics (AV-mathematics for short). We say that a decision problem L ... more >>>

Clement Canonne

A probability distribution over an ordered universe $[n]=\{1,\dots,n\}$ is said to be a $k$-histogram if it can be represented as a piecewise-constant function over at most $k$ contiguous intervals. We study the following question: given samples from an arbitrary distribution $D$ over $[n]$, one must decide whether $D$ is a ... more >>>

Chaoping Xing, chen yuan

Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond $(1-R)/2$ (where $R$ is the rate of code) if ratio ... more >>>

Eric Allender, Joshua Grochow, Cris Moore

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>

James Aisenberg, Maria Luisa Bonet, Sam Buss

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for $k$-D Tucker for all $k\ge 2$. This corrects a claim in the literature that the Tucker search problem is in PPAD.

more >>>Pavel Hrubes, Amir Yehudayoff

The isoperimetric profile of a graph is a function that measures, for an integer $k$, the size of the smallest edge boundary over all sets of vertices of size $k$. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, ... more >>>

Ran Gelles, Bernhard Haeupler, Gillat Kol, Noga Ron-Zewi, Avi Wigderson

We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.

For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and ... more >>>

Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Kulikov

We consider Boolean circuits over the full binary basis. We prove a $(3+\frac{1}{86})n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate ... more >>>

Mika Göös, T.S. Jayram

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

$\bullet~$ $\textbf{AND-OR trees}$: We show a near-optimal $\tilde{\Omega}(n^{0.753...})$ randomised communication lower bound ... more >>>

Gillat Kol

We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol ... more >>>

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

more >>>Alexander Golovnev, Alexander Kulikov

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An $(n,k,s)$-quadratic disperser is a function on $n$ variables that is not constant on any subset of $\mathbb{F}_2^n$ of size at least $s$ ... more >>>

Joshua Grochow

In this short note, we show that the permanent is not complete for non-negative polynomials in $VNP_{\mathbb{R}}$ under monotone p-projections. In particular, we show that Hamilton Cycle polynomial and the cut polynomials are not monotone p-projections of the permanent. To prove this we introduce a new connection between monotone projections ... more >>>

Benny Applebaum, Shachar Lovett

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, y_m)$ using a local mapping, i.e., each $y_i$ should depend on at most $d=O(1)$ bits of $x$. In the polynomial regime of $m=n^s$, $s>1$, the only known solution, ... more >>>

Martin Schwarz

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>>

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>

Scott Aaronson, Shalev Ben-David, Robin Kothari

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>>

Vikraman Arvind, Raja S

In this paper, we study the structure of set-multilinear arithmetic

circuits and set-multilinear branching programs with the aim of

showing lower bound results. We define some natural restrictions of

these models for which we are able to show lower bound results. Some

of our results extend existing lower bounds, while ...
more >>>

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Eshan Chattopadhyay, Xin Li

We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give ... more >>>

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

The study of seeded randomness extractors is a major line of research in theoretical computer science. The goal is to construct deterministic algorithms which can take a ``weak" random source $X$ with min-entropy $k$ and a uniformly random seed $Y$ of length $d$, and outputs a string of length close ... more >>>

Bo Tang, Jiapeng Zhang

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

Let $r \geq 1$ be an integer. Let us call a polynomial $f(x_1, x_2,\ldots, x_N) \in \mathbb{F}[\mathbf{x}]$ as a multi-$r$-ic polynomial if the degree of $f$ with respect to any variable is at most $r$ (this generalizes the notion of multilinear polynomials). We investigate arithmetic circuits in which the output ... more >>>

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

Gil Cohen

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

Matthew Anderson, Michael Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Read-$k$ oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs).

In this work, we give an exponential lower bound of $\exp(n/k^{O(k)})$ on the width of any read-$k$ oblivious ABP computing some explicit multilinear polynomial $f$ that is computed by a ...
more >>>

Arnab Bhattacharyya, Sivakanth Gopi

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is ... more >>>

Benny Applebaum, Pavel Raykov

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS ... more >>>

Nir Bitansky, Vinod Vaikuntanathan

In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions ...
more >>>

Daniel Kane, Ryan Williams

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for ... more >>>

Shay Moran, Cyrus Rashtchian

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... more >>>

Esther Ezra, Shachar Lovett

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We ... more >>>

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most

n^{1+\epsilon_d} ...
more >>>

Ruiwen Chen, Rahul Santhanam

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts ... more >>>

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While ... more >>>

Mrinal Kumar, Shubhangi Saraf

In recent years there has been a flurry of activity proving lower bounds for

homogeneous depth-4 arithmetic circuits [GKKS13, FLMS14, KLSS14, KS14c], which has brought us very close to statements that are known to imply VP $\neq$ VNP. It is a big question to go beyond homogeneity, and in ...
more >>>

Robin Kothari

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

Andris Ambainis

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials.

Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'<1/2$.

This result holds for two ...
more >>>

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our ... more >>>

Shuichi Hirahara, Osamu Watanabe

The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP $\neq$ EXP, which is a ... more >>>

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Let $f : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ be a 2-party function. For every product distribution $\mu$ on $\{0,1\}^n \times \{0,1\}^n$, we show that $${{CC}}^\mu_{0.49}(f) = O\left(\left(\log {{rprt}}_{1/4}(f) \cdot \log \log {{rprt}}_{1/4}(f)\right)^2\right),$$ where ${{CC}^\mu_\varepsilon(f)$ is the distributional communication complexity with error at most $\varepsilon$ under the distribution $\mu$ and ... more >>>

Andris Ambainis

We show nearly quadratic separations between two pairs of complexity measures:

1. We show that there is a Boolean function $f$ with $D(f)=\Omega((D^{sc}(f))^{2-o(1)})$ where $D(f)$ is the deterministic query complexity of $f$ and $D^{sc}$ is the subcube partition complexity of $f$;

2. As a consequence, we obtain that there is ...
more >>>

C Ramya, Raghavendra Rao B V

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.

We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable ...
more >>>

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Polynomial Identity Testing (PIT) algorithms have focused on

polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted

formulas. Read-once polynomials (ROPs) are computed by read-once

formulas (ROFs) and are the simplest of read-restricted polynomials.

Building structures above these, we show the following:

\begin{enumerate}

\item A deterministic polynomial-time non-black-box ...
more >>>

Scott Aaronson, Shalev Ben-David

Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>>

Meena Mahajan, Anuj Tawari

An arithmetic read-once formula (ROF) is a formula (circuit of fan-out

1) over

$+, \times$ where each variable labels at most one leaf.

Every multilinear polynomial can be expressed as the sum of ROFs.

In this work, we prove, for certain multilinear polynomials,

a tight lower bound ...
more >>>

Emanuele Viola

This note proves the existence of a quadratic GF(2) map

$p : \{0,1\}^n \to \{0,1\}$ such that no constant-depth circuit

of size $\poly(n)$ can sample the distribution $(u,p(u))$

for uniform $u$.

Benny Applebaum, Pavel Raykov

Goos, Pitassi and Watson (ITCS, 2015) have recently introduced the notion of Zero-Information Arthur-Merlin Protocols (ZAM). In this model, which can be viewed as a private version of the standard Arthur-Merlin communication complexity game, Alice and Bob are holding a pair of inputs $x$ and $y$ respectively, and Merlin, the ... more >>>

Ofer Grossman

Pseudo-deterministic algorithms are randomized search algorithms which output unique solutions (i.e., with high probability they output the same solution on each execution). We present a pseudo-deterministic algorithm that, given a prime $p,$ finds a primitive root modulo $p$ in time $\exp(O(\sqrt{\log p \log \log p}))$. This improves upon the previous ... more >>>

Shafi Goldwasser, Ofer Grossman

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

Eli Ben-Sasson, Gal Maor

In this paper three complexity measures are studied: (i) internal information, (ii) external information, and (iii) a measure called here "output information". Internal information (i) measures the counter-party privacy-loss inherent in a communication protocol. Similarly, the output information (iii) measures the reduction in input-privacy that is inherent when the output ... more >>>