A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

**S**

__
TR07-030
| 29th March 2007
__

Kai-Min Chung, Omer Reingold, Salil Vadhan#### S-T Connectivity on Digraphs with a Known Stationary Distribution

__
TR15-037
| 20th February 2015
__

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

__
TR17-133
| 7th September 2017
__

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

__
TR03-037
| 30th April 2003
__

Ziv Bar-Yossef#### Sampling Lower Bounds via Information Theory

__
TR12-135
| 26th October 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf#### Sampling-based proofs of almost-periodicity results and algorithmic applications

Revisions: 2

__
TR15-099
| 12th June 2015
__

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

__
TR10-038
| 10th March 2010
__

Dieter van Melkebeek, Holger Dell#### Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Revisions: 1

__
TR15-192
| 26th November 2015
__

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

__
TR04-029
| 7th April 2004
__

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo#### Scaled dimension and the Kolmogorov complexity of Turing hard sets

__
TR06-047
| 11th February 2006
__

Maria Lopez-Valdes#### Scaled Dimension of Individual Strings

__
TR08-043
| 12th April 2008
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Schemes for Deterministic Polynomial Factoring

__
TR15-203
| 13th December 2015
__

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

__
TR97-044
| 26th September 1997
__

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum#### Searching constant width mazes captures the AC^0 hierarchy

__
TR04-076
| 17th September 2004
__

Oliver Giel, Ingo Wegener#### Searching Randomly for Maximum Matchings

__
TR11-082
| 20th May 2011
__

Miklos Ajtai#### Secure Computation with Information Leaking to an Adversary

__
TR15-010
| 19th January 2015
__

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

__
TR98-033
| 12th June 1998
__

C.P. Schnorr#### Security of Allmost ALL Discrete Log Bits

__
TR00-041
| 19th May 2000
__

Igor E. Shparlinski#### Security of Polynomial Transformations of the Diffie--Hellman Key

__
TR00-040
| 19th May 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### Security of the Most Significant Bits of the Shamir Message Passing Scheme

__
TR07-103
| 28th September 2007
__

Emanuele Viola#### Selected Results in Additive Combinatorics: An Exposition

__
TR95-031
| 25th June 1995
__

Dorit Dor, Uri Zwick#### Selecting the median

__
TR04-085
| 3rd October 2004
__

Erez Petrank, Guy Rothblum#### Selection from Structured Data Sets

__
TR14-090
| 11th July 2014
__

Justin Thaler#### Semi-Streaming Algorithms for Annotated Graph Streams

Revisions: 2

__
TR95-011
| 15th February 1995
__

Roman Bacik, Sanjeev Mahajan#### Semidefinite Programming and its Applications to NP Problems

__
TR14-126
| 9th October 2014
__

Debasis Mandal, A. Pavan, Rajeswari Venugopalan#### Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis

__
TR11-134
| 9th October 2011
__

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff#### Separating multilinear branching programs and formulas

__
TR08-014
| 26th February 2008
__

Matei David#### Separating NOF communication complexity classes RP and NP

__
TR14-110
| 19th August 2014
__

Uriel Feige, Shlomo Jozeph#### Separation between Estimation and Approximation

__
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

__
TR17-022
| 13th February 2017
__

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

__
TR01-032
| 3rd April 2001
__

A. Pavan, Alan L. Selman#### Separation of NP-completeness Notions

__
TR16-072
| 4th May 2016
__

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha#### Separations in communication complexity using cheat sheets and information complexity

__
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-175
| 5th November 2015
__

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

__
TR10-136
| 26th August 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie#### Separations of Matroid Freeness Properties

Revisions: 1

__
TR05-140
| 30th November 2005
__

Xi Chen, Xiaotie Deng#### Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

__
TR17-068
| 20th April 2017
__

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

__
TR03-012
| 21st January 2003
__

Edward Hirsch, Arist Kojevnikov#### Several notes on the power of Gomory-Chvatal cuts

__
TR17-164
| 3rd November 2017
__

Scott Aaronson#### Shadow Tomography of Quantum States

__
TR13-044
| 25th March 2013
__

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang#### Shared Randomness and Quantum Communication in the Multi-Party Model

__
TR17-132
| 7th September 2017
__

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

__
TR96-011
| 29th January 1996
__

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith#### Sharply Bounded Alternation within P

__
TR15-189
| 25th November 2015
__

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

Revisions: 1

__
TR13-003
| 2nd January 2013
__

Eric Miles, Emanuele Viola#### Shielding circuits with groups

Revisions: 2

__
TR16-046
| 23rd March 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck

Revisions: 2

__
TR13-007
| 8th January 2013
__

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand#### Short lists with short programs in short time

Revisions: 1

__
TR05-014
| 30th January 2005
__

Oded Goldreich#### Short Locally Testable Codes and Proofs (Survey)

__
TR14-017
| 9th February 2014
__

Eli Ben-Sasson, Emanuele Viola#### Short PCPs with projection queries

__
TR99-022
| 14th June 1999
__

Eli Ben-Sasson, Avi Wigderson#### Short Proofs are Narrow - Resolution made Simple

__
TR11-174
| 30th December 2011
__

Pavel Hrubes, Iddo Tzameret#### Short Proofs for the Determinant Identities

Revisions: 1

__
TR09-002
| 23rd November 2008
__

Eli Ben-Sasson, Jakob Nordström#### Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

__
TR14-048
| 10th April 2014
__

Avishay Tal#### Shrinkage of De Morgan Formulae from Quantum Query Complexity

Revisions: 1

__
TR14-135
| 23rd October 2014
__

Noga Alon, Shay Moran, Amir Yehudayoff#### Sign rank, VC dimension and spectral gaps

Revisions: 2

__
TR09-063
| 29th July 2009
__

Matt DeVos, Ariel Gabizon#### Simple Affine Extractors using Dimension Expansion

Revisions: 2

__
TR17-018
| 6th February 2017
__

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

Revisions: 3

__
TR05-071
| 29th June 2005
__

Marius Zimand#### Simple extractors via constructions of cryptographic pseudo-random generators

__
TR04-060
| 22nd July 2004
__

Eli Ben-Sasson, Madhu Sudan#### Simple PCPs with Poly-log Rate and Query Complexity

__
TR04-071
| 11th August 2004
__

Marcus Schaefer, Stephen A. Fenner#### Simplicity and Strong Reductions

__
TR00-004
| 14th January 2000
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### Simplified derandomization of BPP using a hitting set generator.

__
TR14-060
| 21st April 2014
__

Anup Rao, Amir Yehudayoff#### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

__
TR15-057
| 13th April 2015
__

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

Revisions: 3

__
TR04-089
| 26th October 2004
__

Ingo Wegener#### Simulated Annealing Beats Metropolis in Combinatorial Optimization

__
TR00-067
| 13th July 2000
__

Peter Auer, Philip M. Long#### Simulating Access to Hidden Information while Learning

__
TR05-006
| 28th December 2004
__

Edward Hirsch, Sergey I. Nikolenko#### Simulating Cutting Plane proofs with restricted degree of falsity by Resolution

Comments: 1

__
TR10-037
| 8th March 2010
__

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

__
TR14-119
| 15th September 2014
__

Mark Braverman, Jieming Mao#### Simulating Noisy Channel Interaction

__
TR13-154
| 29th October 2013
__

Martin Schwarz, Maarten Van den Nest#### Simulating Quantum Circuits with Sparse Output Distributions

__
TR17-170
| 6th November 2017
__

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

__
TR14-098
| 30th July 2014
__

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva#### Simultaneous Approximation of Constraint Satisfaction Problems

__
TR12-164
| 17th November 2012
__

Rafail Ostrovsky, Ivan Visconti#### Simultaneous Resettability from Collision Resistance

__
TR03-074
| 24th June 2003
__

Vince Grolmusz#### Sixtors and Mod 6 Computations

__
TR14-077
| 2nd June 2014
__

Andris Ambainis, Jevgenijs Vihrovs#### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma

Revisions: 2

__
TR17-137
| 11th September 2017
__

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

__
TR14-183
| 25th December 2014
__

Nikhil Balaji, Andreas Krebs, Nutan Limaye#### Skew Circuits of Small Width

__
TR12-178
| 18th December 2012
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Sliding Windows With Limited Storage

Revisions: 1

__
TR17-091
| 17th May 2017
__

Andrej Bogdanov#### Small bias requires large formulas

__
TR03-069
| 13th August 2003
__

Elmar Böhler, Christian Glaßer, Daniel Meister#### Small Bounded-Error Computations and Completeness

__
TR13-102
| 17th July 2013
__

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Small Depth Proof Systems

__
TR16-095
| 7th June 2016
__

Arkadev Chattopadhyay, Nikhil Mande#### Small Error Versus Unbounded Error Protocols in the NOF Model

Revisions: 1
,
Comments: 1

__
TR17-035
| 23rd February 2017
__

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

__
TR00-061
| 14th August 2000
__

Prahladh Harsha, Madhu Sudan#### Small PCPs with low query complexity

__
TR97-053
| 10th November 1997
__

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim#### Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

__
TR14-095
| 24th July 2014
__

Mark Braverman, Ankit Garg#### Small value parallel repetition for general games

Revisions: 1

__
TR13-034
| 2nd March 2013
__

Louay Bazzi, Nagi Nahas#### Small-bias is not enough to hit read-once CNF

__
TR17-156
| 15th October 2017
__

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

__
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

__
TR07-039
| 27th March 2007
__

Bodo Manthey, Till Tantau#### Smoothed Analysis of Binary Search Trees and Quicksort Under Additive Noise

Revisions: 1

__
TR05-063
| 24th June 2005
__

Bodo Manthey, Rüdiger Reischuk#### Smoothed Analysis of the Height of Binary Search Trees

Revisions: 2

__
TR08-036
| 14th March 2008
__

Venkatesan Guruswami, Atri Rudra#### Soft decoding, dual BCH codes, and better list-decodable eps-biased codes

__
TR16-024
| 22nd February 2016
__

Patrick Scharpfenecker, Jacobo Toran#### Solution-Graphs of Boolean Formulas and Isomorphism

__
TR04-008
| 27th November 2003
__

Vikraman Arvind, Jacobo Toran#### Solvable Group Isomorphism is (almost) in NP\cap coNP

__
TR08-089
| 28th September 2008
__

Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay#### SOLVENCY GAMES

__
TR14-096
| 29th July 2014
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran#### Solving Linear Equations Parameterized by Hamming Weight

__
TR04-043
| 20th May 2004
__

Luca Trevisan#### Some Applications of Coding Theory in Computational Complexity

__
TR95-044
| 18th September 1995
__

Carsten Damm, Stasys Jukna, Jiri Sgall#### Some Bounds on Multiparty Communication Complexity of Pointer Jumping

__
TR12-048
| 25th April 2012
__

Alan Guo, Madhu Sudan#### Some closure features of locally testable affine-invariant properties

__
TR18-052
| 16th March 2018
__

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

__
TR16-038
| 15th March 2016
__

Meena Mahajan, Nitin Saurabh#### Some Complete and Intermediate Polynomials in Algebraic Complexity Theory

Revisions: 2

__
TR00-024
| 16th May 2000
__

Amihood Amir, Richard Beigel, William Gasarch#### Some Connections between Bounded Query Classes and Non-Uniform Complexity

__
TR12-018
| 24th February 2012
__

Joerg Flum, Moritz Müller#### Some definitorial suggestions for parameterized proof complexity

__
TR04-075
| 21st July 2004
__

Michael Schmitt#### Some dichotomy theorems for neural learning problems

__
TR01-096
| 21st November 2001
__

Jörg Rothe#### Some Facets of Complexity Theory and Cryptography: A Five-Lectures Tutorial

Revisions: 1

__
TR15-005
| 5th January 2015
__

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

Revisions: 1

__
TR15-176
| 6th November 2015
__

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

Revisions: 1

__
TR17-002
| 6th January 2017
__

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

__
TR13-082
| 6th June 2013
__

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish#### Some properties are not even partially testable

__
TR99-006
| 10th March 1999
__

Jin-Yi Cai#### Some Recent Progress on the Complexity of Lattice Problems

__
TR06-048
| 9th April 2006
__

Jin-Yi Cai, Vinay Choudhary#### Some Results on Matchgates and Holographic Algorithms

__
TR97-043
| 25th September 1997
__

Bruno Codenotti, Pavel Pudlak, Giovanni Resta#### Some structural properties of low rank matrices related to computational complexity

Revisions: 1
,
Comments: 1

__
TR08-055
| 19th May 2008
__

Ryan O'Donnell#### Some Topics in Analysis of Boolean Functions

__
TR16-141
| 11th September 2016
__

Ryan O'Donnell#### SOS is not obviously automatizable, even approximately

Revisions: 1

__
TR07-127
| 22nd November 2007
__

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish#### Sound 3-query PCPPs are Long

__
TR12-132
| 21st October 2012
__

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen#### Space Complexity in Polynomial Calculus

__
TR99-040
| 20th October 1999
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Space Complexity in Propositional Calculus

__
TR10-079
| 28th April 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam#### Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

__
TR01-031
| 5th April 2001
__

Eli Ben-Sasson, Nicola Galesi#### Space Complexity of Random Formulae in Resolution

__
TR14-008
| 20th January 2014
__

Vinodchandran Variyam#### Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.

__
TR06-103
| 5th July 2006
__

Oded Lachish, Ilan Newman, Asaf Shapira#### Space Complexity vs. Query Complexity

__
TR02-021
| 11th April 2002
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Space Efficient Algorithms for Directed Series-Parallel Graphs

__
TR07-134
| 14th December 2007
__

Jeff Kinne, Dieter van Melkebeek#### Space Hierarchy Results for Randomized and Other Semantic Models

Revisions: 1

__
TR14-146
| 6th November 2014
__

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan#### Space proof complexity for random $3$-CNFs via a $(2-\epsilon)$-Hall's Theorem

__
TR13-064
| 22nd April 2013
__

Anat Ganor, Ran Raz#### Space Pseudorandom Generators by Communication Complexity Lower Bounds

Revisions: 1

__
TR10-154
| 8th October 2010
__

Derrick Stolee, Vinodchandran Variyam#### Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs

__
TR14-180
| 22nd December 2014
__

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah#### Space-Efficient Approximations for Subset Sum

__
TR10-110
| 14th July 2010
__

Ben Reichardt#### Span programs and quantum query algorithms

__
TR12-049
| 27th April 2012
__

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan#### Sparse affine-invariant linear codes are locally testable

__
TR12-097
| 26th July 2012
__

Andrej Bogdanov, Siyao Guo#### Sparse extractor families for all the entropy

__
TR96-014
| 14th February 1996
__

Mitsunori Ogihara#### Sparse Hard Sets for P Yields Space-Efficient Algorithms

__
TR07-060
| 11th July 2007
__

Tali Kaufman, Madhu Sudan#### Sparse Random Linear Codes are Locally Decodable and Testable

__
TR10-163
| 3rd November 2010
__

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin#### Sparse Selfreducible Sets and Nonuniform Lower Bounds

__
TR98-027
| 15th April 1998
__

Vikraman Arvind, Jacobo Toran#### Sparse sets, approximable sets, and parallel queries to NP

__
TR18-044
| 5th March 2018
__

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

__
TR10-029
| 3rd March 2010
__

Alexandra Kolla#### Spectral Algorithms for Unique Games

__
TR05-029
| 2nd March 2005
__

Frank Neumann, Marco Laumanns#### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization

Revisions: 1

__
TR06-083
| 16th May 2006
__

Nils Hebbinghaus, Benjamin Doerr, Frank Neumann#### Speeding up Evolutionary Algorithms by Restricted Mutation Operators

__
TR09-056
| 20th June 2009
__

Hunter Monroe#### Speedup for Natural Problems and coNP?=NP

Revisions: 2

__
TR16-049
| 28th March 2016
__

Cynthia Dwork, Moni Naor, Guy Rothblum#### Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

__
TR17-151
| 8th October 2017
__

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

__
TR96-049
| 9th September 1996
__

Per Enflo, Meera Sitharam#### Stable basis families and complexity lower bounds

__
TR07-101
| 10th September 2007
__

Patrick Briest, Martin Hoefer, Piotr Krysta#### Stackelberg Network Pricing Games

Revisions: 1

__
TR12-064
| 10th May 2012
__

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao#### Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

__
TR16-177
| 11th November 2016
__

Ilias Diakonikolas, Daniel Kane, Alistair Stewart#### Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures

Revisions: 1

__
TR06-075
| 19th June 2006
__

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan#### Statistical Zero-Knowledge Arguments for NP from Any One-Way Function

__
TR04-115
| 1st December 2004
__

Iftach Haitner, Ronen Shaltiel#### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions

__
TR17-043
| 3rd March 2017
__

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

__
TR11-080
| 11th May 2011
__

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo#### Storage Enforcement with Kolmogorov Complexity and List Decoding

__
TR10-094
| 17th May 2010
__

Ajesh Babu, Nutan Limaye, Girish Varma#### Streaming algorithms for some problems in log-space.

__
TR12-183
| 25th December 2012
__

András Salamon#### Streaming bounds from difference ramification

Revisions: 1
,
Comments: 1

__
TR16-150
| 23rd September 2016
__

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez#### Streaming Communication Protocols

__
TR12-128
| 21st September 2012
__

Nathanaël François, Frederic Magniez#### Streaming Complexity of Checking Priority Queues

Revisions: 1

__
TR11-105
| 22nd July 2011
__

Graham Cormode, Michael Mitzenmacher, Justin Thaler#### Streaming Graph Computations with a Helpful Advisor

Revisions: 1

__
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-058
| 1st April 2015
__

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

__
TR02-026
| 7th April 2002
__

Boaz Barak, Yehuda Lindell#### Strict Polynomial-time in Simulation and Extraction

Revisions: 2

__
TR08-035
| 18th February 2008
__

James I. Lathrop, Jack H. Lutz, Scott M. Summers#### Strict Self-Assembly of Discrete Sierpinski Triangles

__
TR09-095
| 25th September 2009
__

Swapnoneel Roy#### STRIP EXCHANGING IS HARD

Revisions: 1

__
TR06-112
| 22nd August 2006
__

Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang#### Strip Packing vs. Bin Packing

__
TR11-040
| 22nd March 2011
__

Alexander A. Sherstov#### Strong Direct Product Theorems for Quantum Communication and Query Complexity

__
TR16-002
| 18th January 2016
__

Ryan Williams#### Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation

__
TR16-111
| 20th July 2016
__

Amit Chakrabarti, Sagar Kale#### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

__
TR09-023
| 12th March 2009
__

Akinori Kawachi, Osamu Watanabe#### Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems

__
TR14-043
| 2nd April 2014
__

Venkatesan Guruswami, Euiwoong Lee#### Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs

__
TR14-025
| 25th February 2014
__

Oded Goldreich, Tom Gur, Ilan Komargodski#### Strong Locally Testable Codes with Relaxed Local Decoders

__
TR13-022
| 5th February 2013
__

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

Revisions: 1

__
TR12-168
| 26th November 2012
__

Michael Viderman#### Strong LTCs with inverse polylogarithmic rate and soundness

__
TR11-135
| 9th October 2011
__

Maurice Jansen, Rahul Santhanam#### Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes

__
TR10-030
| 18th February 2010
__

Airat Khasianov#### Stronger Lower Bounds on Quantum OBDD for the Hidden Subgroup Problem

Revisions: 2

__
TR16-188
| 21st November 2016
__

Toniann Pitassi, Robert Robere#### Strongly Exponential Lower Bounds for Monotone Computation

__
TR04-057
| 16th May 2004
__

Monica del Pilar Canales Chacon, Michael Johannes Vielhaber#### Structural and Computational Complexity of Isometries and their Shift Commutators

__
TR08-073
| 4th August 2008
__

Dmitry Itsykson#### Structural complexity of AvgBPP

__
TR96-066
| 21st November 1996
__

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan#### Structure in Approximation Classes

__
TR16-044
| 21st March 2016
__

Kaave Hosseini, Shachar Lovett#### Structure of protocols for XOR functions

Revisions: 1

__
TR07-008
| 27th November 2006
__

Philipp Weis, Neil Immerman#### Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words

__
TR13-182
| 20th December 2013
__

Boaz Barak#### Structure vs Combinatorics in Computational Complexity

__
TR16-091
| 3rd June 2016
__

Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan#### Structure vs Hardness through the Obfuscation Lens

Revisions: 3

__
TR96-048
| 12th September 1996
__

Eric Allender, Klaus-Joern Lange#### StUSPACE(log n) is Contained in DSPACE((log^2 n)/loglog n)

__
TR05-086
| 14th August 2005
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

__
TR07-026
| 21st November 2006
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size

__
TR14-088
| 13th July 2014
__

Swagato Sanyal#### Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity

Revisions: 1
,
Comments: 1

__
TR14-157
| 27th November 2014
__

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk#### Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

__
TR05-125
| 2nd November 2005
__

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith#### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

__
TR11-013
| 3rd February 2011
__

Ronitt Rubinfeld, Asaf Shapira#### Sublinear Time Algorithms

__
TR11-090
| 2nd June 2011
__

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee#### Submodular Functions Are Noise Stable

Revisions: 2

__
TR09-129
| 30th November 2009
__

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

__
TR17-064
| 20th April 2017
__

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

__
TR11-139
| 26th October 2011
__

Zeev Dvir, Shachar Lovett#### Subspace Evasive Sets

__
TR14-037
| 21st March 2014
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Succinct and explicit circuits for sorting and connectivity

__
TR96-006
| 24th January 1996
__

Bernd Borchert, Antoni Lozano#### Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

__
TR15-100
| 16th June 2015
__

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

__
TR17-007
| 19th January 2017
__

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

__
TR12-086
| 4th July 2012
__

Shlomi Dolev, Nova Fandina, Dan Gutfreund#### Succinct Permanent is NEXP-hard with Many Hard Instances

__
TR95-048
| 5th October 1995
__

Helmut Veith#### Succinct Representation and Leaf Languages

__
TR09-043
| 18th May 2009
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### Succinct Representation of Codes with Applications to Testing

__
TR16-079
| 2nd May 2016
__

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli#### Sum-of-squares hierarchy lower bounds for symmetric formulations

__
TR14-059
| 21st April 2014
__

Boaz Barak, David Steurer#### Sum-of-squares proofs and the quest toward optimal algorithms

Revisions: 2

__
TR15-071
| 23rd April 2015
__

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

__
TR15-204
| 14th December 2015
__

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

Revisions: 2

__
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

__
TR00-025
| 20th May 2000
__

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee#### Super-linear time-space tradeoff lower bounds for randomized computation

__
TR14-097
| 31st July 2014
__

Oded Goldreich, Liav Teichner#### Super-Perfect Zero-Knowledge Proofs

Revisions: 1

__
TR13-167
| 28th November 2013
__

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma#### Super-polylogarithmic hypergraph coloring hardness via low-degree long codes

__
TR16-203
| 21st December 2016
__

Christoph Berkholz, Jakob Nordström#### Supercritical Space-Width Trade-offs for Resolution

__
TR13-002
| 31st December 2012
__

Venkatesan Guruswami, Krzysztof Onak#### Superlinear lower bounds for multipass graph processing

Revisions: 3

__
TR00-010
| 12th January 2000
__

Amitabha Roy, Christopher Wilson#### Supermodels and Closed Sets

__
TR13-181
| 20th December 2013
__

Mrinal Kumar, Shubhangi Saraf#### Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits

__
TR05-072
| 11th July 2005
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

__
TR12-139
| 2nd November 2012
__

Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Sylvester-Gallai type theorems for approximate collinearity

__
TR07-024
| 5th March 2007
__

Laszlo Egri, Benoit Larose, Pascal Tesson#### Symmetric Datalog and Constraint Satisfaction Problems in Logspace

__
TR10-199
| 14th December 2010
__

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan#### Symmetric LDPC codes are not necessarily locally testable

__
TR94-003
| 12th December 1994
__

Noam Nisan, Amnon Ta-Shma#### Symmetric Logspace is Closed Under Complement

__
TR03-047
| 22nd June 2003
__

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton#### Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

__
TR94-015
| 12th December 1994
__

Miklos Ajtai#### Symmetric Systems of Linear Equations modulo $p$

__
TR06-091
| 29th May 2006
__

Felix Brandt, Felix Fischer, Markus Holzer#### Symmetries and the Complexity of Pure Nash Equilibrium

__
TR10-070
| 17th April 2010
__

Eric Allender, Klaus-Joern Lange#### Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

__
TR10-191
| 9th December 2010
__

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland#### Symmetry-assisted adversaries for quantum state generation

__
TR12-122
| 17th September 2012
__

Giorgio Ausiello, Francesco Cristiano, Luigi Laura#### Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete

__
TR95-045
| 4th September 1995
__

Moni Naor, Omer Reingold#### Synthesizers and Their Application to the Parallel Construction of Pseudo-random Functions

__
TR01-030
| 25th April 2001
__

Jin-Yi Cai#### S_2^p \subseteq ZPP^{NP}

Kai-Min Chung, Omer Reingold, Salil Vadhan

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... 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 >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

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

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for ... 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 >>>

Dieter van Melkebeek, Holger Dell

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... 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 >>>

John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo

Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.

more >>>Maria Lopez-Valdes

We define a new discrete version of scaled dimension and we find

connections between the scaled dimension of a string and its Kolmogorov

complexity and predictability. We give a new characterization

of constructive scaled dimension by Kolmogorov complexity, and prove

a new result about scaled dimension and prediction.

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

In this work we relate the deterministic

complexity of factoring polynomials (over

finite

fields) to certain combinatorial objects we

call

m-schemes. We extend the known conditional

deterministic subexponential time polynomial

factoring algorithm for finite fields to get an

underlying m-scheme. We demonstrate ...
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 >>>

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

We show that searching a width k maze is complete for \Pi_k, i.e., for

the k'th level of the AC^0 hierarchy. Equivalently, st-connectivity

for width k grid graphs is complete for \Pi_k. As an application,

we show that there is a data structure solving dynamic st-connectivity

for constant ...
more >>>

Oliver Giel, Ingo Wegener

Many real-world optimization problems in, e.g., engineering

or biology have the property that not much is known about

the function to be optimized. This excludes the application

of problem-specific algorithms. Simple randomized search

heuristics are then used with surprisingly good results. In

order to understand the working principles behind such

more >>>

Miklos Ajtai

Assume that Alice is running a program $P$ on a RAM, and an adversary

Bob would like to get some information about the input or output of the

program. At each time, during the execution of $P$, Bob is able to see

the addresses of the memory cells involved in ...
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 >>>

C.P. Schnorr

Let G be a finite cyclic group with generator \alpha and with

an encoding so that multiplication is computable in polynomial time. We

study the security of bits of the discrete log x when given \exp_{\alpha}(x),

assuming that the exponentiation function \exp_{\alpha}(x) = \alpha^x is one-way.

...
more >>>

Igor E. Shparlinski

D. Boneh and R. Venkatesan have recently proposed an approach to proving

that a reasonably small portions of most significant bits of the

Diffie--Hellman key modulo a prime are as secure the the whole key. Some

further improvements and generalizations have been obtained by

I. M. Gonzales Vasco ...
more >>>

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

algorithm for recovering a ``hidden'' element $\alpha$ of a

finite field $\F_p$ of $p$ elements from rather short

strings of the most significant bits of the remainder

mo\-du\-lo $p$ of $\alpha t$ for several values of $t$ selected uniformly

at random ...
more >>>

Emanuele Viola

We give a self-contained exposition of selected results in additive

combinatorics over the group {0,1}^n. In particular, we prove the

celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94 and '98) and

the

Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result

by Samorodnitsky ('07) that linear transformations are efficiently ...
more >>>

Dorit Dor, Uri Zwick

Improving a long standing result of Sch\"{o}nhage, Paterson

and Pippenger we show that the MEDIAN of a set containing n

elements can always be found using at most 2.95n comparisons.

This is the full version of the paper. An extended abstract

version ...
more >>>

Erez Petrank, Guy Rothblum

A large body of work studies the complexity of selecting the

$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.

the select$(j)$ operation). In this work, we study the

complexity of select in data that is partially structured by

an initial preprocessing stage and in a data structure ...
more >>>

Justin Thaler

Considerable effort has been devoted to the development of streaming algorithms for analyzing massive graphs. Unfortunately, many results have been negative, establishing that a wide variety of problems require $\Omega(n^2)$ space to solve. One of the few bright spots has been the development of semi-streaming algorithms for a handful of ... more >>>

Roman Bacik, Sanjeev Mahajan

The graph homomorphism problem is a canonical $NP$-complete problem.

It generalizes various other well-studied problems such as graph

coloring and finding cliques. To get a better insight into a

combinatorial problem, one often studies relaxations of the problem.

We define fractional homomorphisms and pseudo-homomorphisms ...
more >>>

Debasis Mandal, A. Pavan, Rajeswari Venugopalan

We show that there is a language that is Turing complete for NP but not many-one complete for NP, under a {\em worst-case} hardness hypothesis. Our hypothesis asserts the existence of a non-deterministic, double-exponential time machine that runs in time $O(2^{2^{n^c}})$ (for some $c > 1$) accepting $\Sigma^*$ whose accepting ... more >>>

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>>

Matei David

We provide a non-explicit separation of the number-on-forehead communication complexity classes RP and NP when the number of players is up to \delta log(n) for any \delta<1. Recent lower bounds on Set-Disjointness [LS08,CA08] provide an explicit separation between these classes when the number of players is only up to o(loglog(n)).

... more >>>Uriel Feige, Shlomo Jozeph

We show (under standard assumptions) that there are NP optimization problems for which estimation is easier than approximation. Namely, one can estimate the value of the optimal solution within a ratio of $\rho$, but it is difficult to find a solution whose value is within $\rho$ of optimal.

As an ...
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 >>>

Benjamin Rossman, Srikanth Srinivasan

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

A. Pavan, Alan L. Selman

We use hypotheses of structural complexity theory to separate various

NP-completeness notions. In particular, we introduce an hypothesis from which we describe a set in NP that is Turing complete but not truth-table complete. We provide fairly thorough analyses of the hypotheses that we introduce. Unlike previous approaches, we ...
more >>>

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
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 >>>

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

Arnab Bhattacharyya, Elena Grigorescu, Jakob Nordström, Ning Xie

Properties of Boolean functions on the hypercube that are invariant

with respect to linear transformations of the domain are among some of

the most well-studied properties in the context of property testing.

In this paper, we study a particular natural class of linear-invariant

properties, called matroid freeness properties. These properties ...
more >>>

Xi Chen, Xiaotie Deng

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

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

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

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

Edward Hirsch, Arist Kojevnikov

We prove that the Cutting Plane proof system based on

Gomory-Chvatal cuts polynomially simulates the

lift-and-project system with integer coefficients

written in unary. The restriction on coefficients can be

omitted when using Krajicek's cut-free Gentzen-style extension

of both systems. We also prove that Tseitin tautologies

have short proofs in ...
more >>>

Scott Aaronson

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

Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

We study shared randomness in the context of multi-party number-in-hand communication protocols in the simultaneous message passing model. We show that with three or more players, shared randomness exhibits new interesting properties that have no direct analogues in the two-party case.

First, we demonstrate a hierarchy of modes of shared ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

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

Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

We define the sharply bounded hierarchy, SBHQL, a hierarchy of

classes within P, using quasilinear-time computation and

quantification over values of length log n. It generalizes the

limited nondeterminism hierarchy introduced by Buss and Goldsmith,

while retaining the invariance properties. The new hierarchy has

several alternative characterizations.

We define ... 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 >>>

Eric Miles, Emanuele Viola

We show how to efficiently compile any given circuit $C$

into a leakage-resistant circuit $\widehat{C}$ such that any

function on the wires of $\widehat{C}$ that leaks information

during a computation $\widehat{C}(x)$ yields advantage in

computing the product of $|\widehat{C}|^{\Omega(1)}$ elements

of the alternating group $A_u$. In combination with new

compression ...
more >>>

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

Oded Goldreich

We survey known results regarding locally testable codes

and locally testable proofs (known as PCPs),

with emphasis on the length of these constructs.

Locally testability refers to approximately testing

large objects based on a very small number of probes,

each retrieving a single bit in the ...
more >>>

Eli Ben-Sasson, Emanuele Viola

We construct a PCP for NTIME(2$^n$) with constant

soundness, $2^n \poly(n)$ proof length, and $\poly(n)$

queries where the verifier's computation is simple: the

queries are a projection of the input randomness, and the

computation on the prover's answers is a 3CNF. The

previous upper bound for these two computations was

more >>>

Eli Ben-Sasson, Avi Wigderson

The width of a Resolution proof is defined to be the maximal number of

literals in any clause of the proof. In this paper we relate proof width

to proof length (=size), in both general Resolution, and its tree-like

variant. The following consequences of these relations reveal width as ...
more >>>

Pavel Hrubes, Iddo Tzameret

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>

Eli Ben-Sasson, Jakob Nordström

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>

Avishay Tal

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is $2$. Namely, we show that for any Boolean function $f: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size ... more >>>

Noga Alon, Shay Moran, Amir Yehudayoff

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

Matt DeVos, Ariel Gabizon

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ...
more >>>

Oded Goldreich, Guy Rothblum

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

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

Specifically, such ...
more >>>

Marius Zimand

Trevisan has shown that constructions of pseudo-random generators from

hard functions (the Nisan-Wigderson approach) also produce extractors.

We show that constructions of pseudo-random generators from one-way permutations

(the Blum-Micali-Yao approach) can be used for building extractors as well.

Using this new technique we build extractors that ...
more >>>

Eli Ben-Sasson, Madhu Sudan

We give constructions of PCPs of length n*polylog(n) (with respect

to circuits of size n) that can be verified by making polylog(n)

queries to bits of the proof. These PCPs are not only shorter than

previous ones, but also simpler. Our (only) building blocks are

Reed-Solomon codes and the bivariate ...
more >>>

Marcus Schaefer, Stephen A. Fenner

A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

A hitting-set generator is a deterministic

algorithm which generates a set of strings that intersects

every dense set recognizable by a small circuit.

A polynomial time hitting-set generator readily implies $RP=P$.

Andreev \etal\/ (ICALP'96, and JACM 1998)

showed that if polynomial-time hitting-set

generator in fact implies ...
more >>>

Anup Rao, Amir Yehudayoff

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof

showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

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

Ingo Wegener

The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

Peter Auer, Philip M. Long

We introduce a new technique which enables a learner without access to

hidden information to learn nearly as well as a learner with access to

hidden information. We apply our technique to solve an open problem

of Maass and Turan, showing that for any concept class F the least ...
more >>>

Edward Hirsch, Sergey I. Nikolenko

Goerdt (1991) considered a weakened version of the Cutting Plane proof system with a restriction on the degree of falsity of intermediate inequalities. (The degree of falsity of an inequality written in the form $\sum a_ix_i+\sum b_i(1-x_i)\ge c,\ a_i,b_i\ge0$ is its constant term $c$.) He proved a superpolynomial lower bound ... more >>>

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a

distribution $X$ on binary strings of length $n$ is a

$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$

to any string of length $n$. For every $\delta>0$ we construct the

following poly($n$)-time ...
more >>>

Mark Braverman, Jieming Mao

We show that $T$ rounds of interaction over the binary symmetric channel $BSC_{1/2-\epsilon}$ with feedback can be simulated with $O(\epsilon^2 T)$ rounds of interaction over a noiseless channel. We also introduce a more general "energy cost'' model of interaction over a noisy channel. We show energy cost to be equivalent ... more >>>

Martin Schwarz, Maarten Van den Nest

We show that several quantum circuit families can be simulated efficiently classically if it is promised that their output distribution is approximately sparse i.e. the distribution is close to one where only a polynomially small, a priori unknown subset of the measurement probabilities are nonzero. Classical simulations are thereby obtained ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

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

Amey Bhangale, Swastik Kopparty, Sushant Sachdeva

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context.

Our main result is that ... more >>>

Rafail Ostrovsky, Ivan Visconti

In FOCS 2001, Barak, Goldreich, Goldwasser and Lindell conjectured that the existence of ZAPs, introduced by Dwork and Naor in FOCS 2000, could lead to the design of a zero-knowledge proof system that is secure against both resetting provers and resetting verifiers. Their conjecture has been proven true by Deng, ... more >>>

Vince Grolmusz

We consider the following phenomenon: with just one multiplication

we can compute (3u+2v)(3x+2y)= 3ux+4vy mod 6, while computing the same polynomial modulo 5 needs 2 multiplications. We generalize this observation and we define some vectors, called sixtors, with remarkable zero-divisor properties. Using sixtors, we also generalize our earlier result ...
more >>>

Andris Ambainis, Jevgenijs Vihrovs

We study the structure of sets $S\subseteq\{0, 1\}^n$ with small sensitivity. The well-known Simon's lemma says that any $S\subseteq\{0, 1\}^n$ of sensitivity $s$ must be of size at least $2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde

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

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

Nikhil Balaji, Andreas Krebs, Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs -- polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC1. On the other hand it is known that width-3 PBPs ... more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

We consider time-space tradeoffs for exactly computing frequency

moments and order statistics over sliding windows.

Given an input of length $2n-1$, the task is to output the function of

each window of length $n$, giving $n$ outputs in total.

Computations over sliding windows are related to direct sum problems

except ...
more >>>

Andrej Bogdanov

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

Elmar Böhler, Christian Glaßer, Daniel Meister

SBP is a probabilistic promise class located

between MA and AM \cap BPPpath. The first

part of the paper studies the question of whether

SBP has many-one complete sets. We relate

this question to the existence of uniform

enumerations. We construct an oracle relative to

which SBP and AM do ...
more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

A proof system for a language $L$ is a function $f$ such that Range$(f)$ is exactly $L$. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by ... more >>>

Arkadev Chattopadhyay, Nikhil Mande

We show that a simple function has small unbounded error communication complexity in the $k$-party number-on-forehead (NOF) model but every probabilistic protocol that solves it with sub-exponential advantage over random guessing has cost essentially $\Omega\left(\frac{\sqrt{n}}{4^k}\right)$ bits. Such a separation was first shown for $k=2$ independently by Buhrman et al. ['07] ... more >>>

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

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

Prahladh Harsha, Madhu Sudan

Most known constructions of probabilistically checkable proofs (PCPs)

either blow up the proof size by a large polynomial, or have a high

(though constant) query complexity. In this paper we give a

transformation with slightly-super-cubic blowup in proof size, with a

low query complexity. Specifically, the verifier probes the proof ...
more >>>

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

We show the following Reduction Lemma: any

$\epsilon$-biased sample space with respect to (Boolean) linear

tests is also $2\epsilon$-biased with respect to

any system of independent linear tests. Combining this result with

the previous constructions of $\epsilon$-biased sample space with

respect to linear tests, we obtain the first efficient

more >>>

Mark Braverman, Ankit Garg

We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. We use information theoretic techniques in our proof. Our proofs also extend to the high value regime (value close to 1) ... more >>>

Louay Bazzi, Nagi Nahas

Small-bias probability spaces have wide applications in pseudorandomness which naturally leads to the study of their limitations. Constructing a polynomial complexity hitting set for read-once CNF formulas is a basic open problem in pseudorandomness. We show in this paper that this goal is not achievable using small-bias spaces. Namely, we ... more >>>

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

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

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

Bodo Manthey, Till Tantau

Binary search trees are a fundamental data structure and their height

plays a key role in the analysis of divide-and-conquer algorithms like

quicksort. Their worst-case height is linear; their average height,

whose exact value is one of the best-studied problems in average-case

complexity, is logarithmic. We analyze their smoothed height ...
more >>>

Bodo Manthey, Rüdiger Reischuk

Binary search trees are one of the most fundamental data structures. While the

height of such a tree may be linear in the worst case, the average height with

respect to the uniform distribution is only logarithmic. The exact value is one

of the best studied problems in average case ...
more >>>

Venkatesan Guruswami, Atri Rudra

We construct binary linear codes that are efficiently list-decodable

up to a fraction $(1/2-\eps)$ of errors. The codes encode $k$ bits

into $n = {\rm poly}(k/\eps)$ bits and are constructible and

list-decodable in time polynomial in $k$ and $1/\eps$ (in

particular, in our results $\eps$ need ...
more >>>

Patrick Scharpfenecker, Jacobo Toran

The solution graph of a Boolean formula on n variables is the subgraph of the hypercube Hn induced by the satisfying assignments of the formula. The structure of solution graphs has been the object of much research in recent years since it is important for the performance of SAT-solving procedures ... more >>>

Vikraman Arvind, Jacobo Toran

The Group Isomorphism problem consists in deciding whether two input

groups $G_1$ and $G_2$ given by their multiplication tables are

isomorphic. We first give a 2-round Arthur-Merlin protocol for the

Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$

of size $n$, Arthur uses ...
more >>>

Noam Berger, Kapur Nevin, Schulman Leonard, Vazirani Vijay

Abstract. We study the decision theory of a maximally risk-averse investor | one whose objec-

tive, in the face of stochastic uncertainties, is to minimize the probability of ever going broke. With

a view to developing the mathematical basics of such a theory, we start with a very simple model

more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:

1. Does $Ax=b$ have a solution of weight at most $t$?

2. Does $Ax=b$ have a solution of weight exactly $t$?

3. Does $Ax=b$ have a ...
more >>>

Luca Trevisan

Error-correcting codes and related combinatorial constructs

play an important role in several recent (and old) results

in computational complexity theory. In this paper we survey

results on locally-testable and locally-decodable error-correcting

codes, and their applications to complexity theory and to

cryptography.

Locally decodable codes are error-correcting codes ... more >>>

Carsten Damm, Stasys Jukna, Jiri Sgall

We introduce the model of conservative one-way multiparty complexity

and prove lower and upper bounds on the complexity of pointer jumping.

The pointer jumping function takes as its input a directed layered

graph with a starting node and layers of nodes, and a single edge ...
more >>>

Alan Guo, Madhu Sudan

We prove that the class of locally testable affine-invariant properties is closed under sums, intersections and "lifts". The sum and intersection are two natural operations on linear spaces of functions, where the sum of two properties is simply their sum as a vector space. The "lift" is a less natural ... more >>>

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

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

Meena Mahajan, Nitin Saurabh

We provide a list of new natural VNP-intermediate polynomial

families, based on basic (combinatorial) NP-complete problems that

are complete under \emph{parsimonious} reductions. Over finite

fields, these families are in VNP, and under the plausible

hypothesis $\text{Mod}_pP \not\subseteq P/\text{poly}$, are neither VNP-hard (even under

oracle-circuit reductions) nor in VP. Prior to ...
more >>>

Amihood Amir, Richard Beigel, William Gasarch

Let A(x) be the characteristic function of A. Consider the function

F_k^A(x_1,...,x_k) = A(x_1)...A(x_k). We show that if F_k^A can be

computed with fewer than k queries to some set X, then A can be

computed by polynomial size circuits. A generalization of this result

has applications to bounded query ...
more >>>

Joerg Flum, Moritz Müller

We introduce a (new) notion of parameterized proof system. For parameterized versions of standard proof systems such as Extended Frege and Substitution Frege we compare their complexity with respect to parameterized simulations.

more >>>Michael Schmitt

The computational complexity of learning from binary examples is

investigated for linear threshold neurons. We introduce

combinatorial measures that create classes of infinitely many

learning problems with sample restrictions. We analyze how the

complexity of these problems depends on the values for the measures.

...
more >>>

Jörg Rothe

In this tutorial, selected topics of cryptology and of

computational complexity theory are presented. We give a brief overview

of the history and the foundations of classical cryptography, and then

move on to modern public-key cryptography. Particular attention is

paid to cryptographic protocols and the problem of constructing ...
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 >>>

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

Frantisek Duris

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

Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

For a property $P$ and a sub-property $P'$, we say that $P$ is $P'$-partially testable with $q$ queries if there exists an algorithm that distinguishes, with high probability, inputs in $P'$ from inputs $\epsilon$-far from $P$ by using $q$ queries. There are natural properties that require many queries to test, ... more >>>

Jin-Yi Cai

We survey some recent developments in the study of

the complexity of lattice problems. After a discussion of some

problems on lattices which can be algorithmically solved

efficiently, our main focus is the recent progress on complexity

results of intractability. We will discuss Ajtai's worst-case/

average-case connections, NP-hardness and non-NP-hardness,

more >>>

Jin-Yi Cai, Vinay Choudhary

We establish a 1-1 correspondence between Valiant's

character theory of matchgate/matchcircuit

and his signature theory of planar-matchgate/matchgrid,

thus unifying the two theories in expressibility.

Previously we had established a complete characterization

of general matchgates, in terms of a set of

useful Grassmann-Pl{\"u}cker identities.

With this correspondence,

we give a corresponding ...
more >>>

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

We consider the conjecture stating that a matrix with rank

$o(n)$ and ones on the main diagonal must contain nonzero

entries on a $2\times 2$ submatrix with one entry on the main

diagonal. We show that a slightly stronger conjecture implies

that ...
more >>>

Ryan O'Donnell

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding ... more >>>

Ryan O'Donnell

Suppose we want to minimize a polynomial $p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints $q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include $x_i^2 \leq 1$ for all $1 \leq i \leq ... more >>>

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

We initiate the study of the tradeoff between the {\em length} of a

probabilistically checkable proof of proximity (PCPP) and the

maximal {\em soundness} that can be guaranteed by a $3$-query

verifier with oracle access to the proof. Our main observation is

that a verifier limited to querying a short ...
more >>>

Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen

During the last decade, an active line of research in proof complexity has been to study space complexity and time-space trade-offs for proofs. Besides being a natural complexity measure of intrinsic interest, space is also an important issue in SAT solving, and so research has mostly focused on weak systems ... more >>>

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson

We study space complexity in the framework of

propositional proofs. We consider a natural model analogous to

Turing machines with a read-only input tape, and such

popular propositional proof systems as Resolution, Polynomial

Calculus and Frege systems. We propose two different space measures,

corresponding to the maximal number of bits, ...
more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari, Vinodchandran Variyam

We investigate the space complexity of certain perfect matching

problems over bipartite graphs embedded on surfaces of constant genus

(orientable or non-orientable). We show that the problems of deciding

whether such graphs have (1) a perfect matching or not and (2) a

unique perfect matching or not, are in the ...
more >>>

Eli Ben-Sasson, Nicola Galesi

We study the space complexity of refuting unsatisfiable random $k$-CNFs in

the Resolution proof system. We prove that for any large enough $\Delta$,

with high probability a random $k$-CNF over $n$ variables and $\Delta n$

clauses requires resolution clause space of

$\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$,

for any $0<\epsilon<1/2$. For constant $\Delta$, ...
more >>>

Vinodchandran Variyam

The graph reachability problem, the computational task of deciding whether there is a path between two given nodes in a graph is the canonical problem for studying space bounded computations. Three central open questions regarding the space complexity of the reachability problem over directed graphs are: (1) improving Savitch's $O(\log^2 ... more >>>

Oded Lachish, Ilan Newman, Asaf Shapira

Combinatorial property testing deals with the following relaxation

of decision problems: Given a fixed property and an input $x$, one

wants to decide whether $x$ satisfies the property or is ``far''

from satisfying it. The main focus of property testing is in

identifying large families of properties that can be ...
more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

The subclass of directed series-parallel graphs plays an important role in

computer science. Whether a given graph is series-parallel is a

well studied problem in algorithmic graph theory, for which fast sequential and

parallel algorithms have been developed in a sequence of papers.

Also methods are known to solve ...
more >>>

Jeff Kinne, Dieter van Melkebeek

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following.

Let <i>s</i>(<i>n</i>) ... more >>>

Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan

We investigate the space complexity of refuting $3$-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of $3$-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>

Anat Ganor, Ran Raz

In 1989, Babai, Nisan and Szegedy [BNS92] gave a construction of a pseudorandom generator for logspace, based on lower bounds for multiparty communication complexity. The seed length of their pseudorandom generator was $2^{\Theta(\sqrt n)}\,\,\,$, because the best lower bounds for multiparty communication complexity are relatively weak. Subsequently, pseudorandom generators for ... more >>>

Derrick Stolee, Vinodchandran Variyam

We consider the reachability problem for a certain class of directed acyclic graphs embedded on surfaces. Let ${\cal G}(m,g)$ be the class of directed acyclic graphs with $m = m(n)$ source vertices embedded on a surface (orientable or non-orientable) of genus $g = g(n)$. We give a log-space reduction that ... more >>>

Anna Gal, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

SUBSET SUM is a well known NP-complete problem:

given $t \in Z^{+}$ and a set $S$ of $m$ positive integers, output YES if and only if there is a subset $S^\prime \subseteq S$ such that the sum of all numbers in $S^\prime$ equals $t$. The problem and its search ...
more >>>

Ben Reichardt

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower ... more >>>

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field ${\mathbb{F}}_q$ and an extension field ${\mathbb{F}}_{q^n}$, a property is a set of functions mapping ${\mathbb{F}}_{q^n}$ to ${\mathbb{F}}_q$. The property is said to be affine-invariant if it ... more >>>

Andrej Bogdanov, Siyao Guo

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of ... more >>>

Mitsunori Ogihara

In 1978, Hartmanis conjectured that there exist no sparse complete sets

for P under logspace many-one reductions. In this paper, in support of

the conjecture, it is shown that if P has sparse hard sets under logspace

many-one reductions, then P is included in DPSPACE[log^2 n].

Tali Kaufman, Madhu Sudan

We show that random sparse binary linear codes are locally testable and locally decodable (under any linear encoding) with constant queries (with probability tending to one). By sparse, we mean that the code should have only polynomially many codewords. Our results are the first to show that local decodability and ... more >>>

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in $EXP^{NP}$, or even ... more >>>

Vikraman Arvind, Jacobo Toran

We relate the existence of disjunctive hard sets for NP to

other well studied hypotheses in complexity theory showing

that if an NP-complete set or a coNP-complete set is

polynomial-time disjunctively reducible

to a sparse set then FP$^{\rm NP}_{||}$ = FP$^{\rm NP[log]}$. Using

a similar argument we obtain also that ...
more >>>

Alessandro Chiesa, Michael Forbes, Tom Gur, Nicholas Spooner

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

Alexandra Kolla

We present a new algorithm for Unique Games which is based on purely {\em spectral} techniques, in contrast to previous

work in the area, which relies heavily on semidefinite programming (SDP). Given a highly satisfiable instance of Unique Games, our algorithm is able to recover a good assignment.

The approximation ...
more >>>

Frank Neumann, Marco Laumanns

We give faster approximation algorithms for the

generalization of two NP-hard spanning tree problems. First,

we investigate the problem of minimizing the degree of

minimum spanning forests. The task is to compute for each

number of connected components a minimum spanning forest

whose degree is as small as possible. Fischer

more >>>

Nils Hebbinghaus, Benjamin Doerr, Frank Neumann

We investigate the effect of restricting the mutation operator in

evolutionary algorithms with respect to the runtime behavior.

Considering the Eulerian cycle problem we present runtime bounds on

evolutionary algorithms with a restricted operator that are much

smaller than the best upper bounds for the ...
more >>>

Hunter Monroe

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a ... more >>>

Cynthia Dwork, Moni Naor, Guy Rothblum

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

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

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

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

Per Enflo, Meera Sitharam

--

Scalar product estimates have so far been used in

proving several unweighted threshold lower bounds.

We show that if a basis set of Boolean functions satisfies

certain weak stability conditions, then

scalar product estimates

yield lower bounds for the size of weighted thresholds

of these basis functions.

Stable ...
more >>>

Patrick Briest, Martin Hoefer, Piotr Krysta

We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>>

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

Ilias Diakonikolas, Daniel Kane, Alistair Stewart

We prove the first {\em Statistical Query lower bounds} for two fundamental high-dimensional learning problems involving Gaussian distributions: (1) learning Gaussian mixture models (GMMs), and (2) robust (agnostic) learning of a single unknown mean Gaussian. In particular, we show a {\em super-polynomial gap} between the (information-theoretic) sample complexity and the ... more >>>

Minh-Huyen Nguyen, Shien Jin Ong, Salil Vadhan

We show that every language in NP has a *statistical* zero-knowledge

argument system under the (minimal) complexity assumption that

one-way functions exist. In such protocols, even a computationally

unbounded verifier cannot learn anything other than the fact that the

assertion being proven is true, whereas a polynomial-time prover

cannot convince ...
more >>>

Iftach Haitner, Ronen Shaltiel

A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another

polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any

additional information but the validity of the claim.

Naor ... more >>>

Alexey Milovanov, Nikolay Vereshchagin

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

mohammad iftekhar husain, steve ko, Atri Rudra, steve uurtamo

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>

Ajesh Babu, Nutan Limaye, Girish Varma

In this paper, we give streaming algorithms for some problems which are known to be in deterministic log-space, when the number of passes made on the input is unbounded. If the input data is massive,

the conventional deterministic log-space algorithms may not run efficiently. We study the complexity of the ...
more >>>

András Salamon

In graph streaming a graph with $n$ vertices and $m$ edges is presented as a read-once stream of edges. We obtain an $\Omega(n \log n)$ lower bound on the space required to decide graph connectivity. This improves the known bounds of $\Omega(n)$ for undirected and $\Omega(m)$ for sparse directed graphs. ... more >>>

Lucas Boczkowski, Iordanis Kerenidis, Frederic Magniez

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents ... more >>>

Nathanaël François, Frederic Magniez

This work is in the line of designing efficient checkers for testing the reliability of some massive data structures. Given a sequential access to the insert/extract operations on such a structure, one would like to decide, a posteriori only, if it corresponds to the evolution of a reliable structure. In ... more >>>

Graham Cormode, Michael Mitzenmacher, Justin Thaler

Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a ... 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 >>>

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

Boaz Barak, Yehuda Lindell

The notion of efficient computation is usually identified in cryptography and complexity with probabilistic polynomial time. However, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge-extractors to run in time which is only polynomial {\em on the average} (i.e., ... more >>>

James I. Lathrop, Jack H. Lutz, Scott M. Summers

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004). Precisely speaking, the above self-assemblies tile completely ... more >>>

Swapnoneel Roy

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the ... more >>>

Xin Han, Kazuo Iwama, Deshi Ye, Guochuan Zhang

In this paper

we establish a general algorithmic framework between bin packing

and strip packing, with which we achieve the same asymptotic

bounds by applying bin packing algorithms to strip packing. More

precisely we obtain the following results: (1) Any offline bin

packing algorithm can be applied to strip packing ...
more >>>

Alexander A. Sherstov

A strong direct product theorem (SDPT) states that solving $n$ instances of a problem requires $\Omega(n)$ times the resources for a single instance, even to achieve success probability $2^{-\Omega(n)}.$ We prove that quantum communication complexity obeys an SDPT whenever the communication lower bound for a single instance is proved by ... more >>>

Ryan Williams

We present an efficient proof system for Multipoint Arithmetic Circuit Evaluation: for every arithmetic circuit $C(x_1,\ldots,x_n)$ of size $s$ and degree $d$ over a field ${\mathbb F}$, and any inputs $a_1,\ldots,a_K \in {\mathbb F}^n$,

$\bullet$ the Prover sends the Verifier the values $C(a_1), \ldots, C(a_K) \in {\mathbb F}$ and ...
more >>>

Amit Chakrabarti, Sagar Kale

We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a ...
more >>>

Akinori Kawachi, Osamu Watanabe

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

Venkatesan Guruswami, Euiwoong Lee

Consider a $K$-uniform hypergraph $H = (V,E)$. A coloring $c : V \rightarrow \{1, 2, \dots, k \}$ with $k$ colors is rainbow if every hyperedge $e$ contains at least one vertex from each color, and is called perfectly balanced when each color appears the same number of times. A ... more >>>

Oded Goldreich, Tom Gur, Ilan Komargodski

Locally testable codes (LTCs) are error-correcting codes

that admit very efficient codeword tests. An LTC is said to

be strong if it has a proximity-oblivious tester;

that is, a tester that makes only a constant number of queries

and reject non-codewords with probability that depends solely

on their distance from ...
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 >>>

Michael Viderman

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

Maurice Jansen, Rahul Santhanam

We associate to each Boolean language complexity class $\mathcal{C}$ the algebraic class $a\cdot\mathcal{C}$ consisting of families of polynomials $\{f_n\}$ for which the evaluation problem over the integers is in $\mathcal{C}$. We prove the following lower bound and randomness-to-hardness results:

1. If polynomial identity testing (PIT) is in $NSUBEXP$ then $a\cdot ... more >>>

Airat Khasianov

We consider the \emph{Hidden Subgroup} in the context of quantum \emph{Ordered Binary Decision Diagrams}.

We show several lower bounds for this function.

In this paper we also consider a slightly more general definition of the

hidden subgroup problem (in contrast to that in \cite{khashsp1}). It turns out that ...
more >>>

Toniann Pitassi, Robert Robere

For a universal constant $\alpha > 0$, we prove size lower bounds of $2^{\alpha N}$ for computing an explicit monotone function in NP in the following models of computation: monotone formulas, monotone switching networks, monotone span programs, and monotone comparator circuits, where $N$ is the number of variables of the ... more >>>

Monica del Pilar Canales Chacon, Michael Johannes Vielhaber

{\bf Abstract}

Isometries on formal power series over the finite field $\ff_2$

or on $2$--adic integers can be

computed by invertible transducers on inputs from $\{0,1\}^\infty$.

We consider the structural complexity of an isometry $f$,

measured as {\it tree complexity} $T(f,h)$, $h$ the tree height

[H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, ...
more >>>

Dmitry Itsykson

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>

Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan

The study of the approximability properties of NP-hard

optimization problems has recently made great advances mainly due

to the results obtained in the field of proof checking. In a

recent breakthrough the APX-completeness of several important

optimization problems is proved, thus reconciling `two distinct

views of ...
more >>>

Kaave Hosseini, Shachar Lovett

Let $f:\{0,1\}^n \to \{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_\oplus(x,y) = f(x \oplus y)$.

We show that, up to polynomial factors, the deterministic communication complexity of $f_{\oplus}$ is equal to the parity decision tree complexity of $f$.

This relies on a novel technique ...
more >>>

Philipp Weis, Neil Immerman

It is well-known that every first-order property on words is expressible

using at most three variables. The subclass of properties expressible with

only two variables is also quite interesting and well-studied. We prove

precise structure theorems that characterize the exact expressive power of

first-order logic with two variables on words. ...
more >>>

Boaz Barak

Some computational problems seem to have a certain "structure" that is manifested in non-trivial algorithmic properties, while others are more "unstructured" in the sense that they are either "very easy" or "very hard". I survey some of the known results and open questions about this classification and its connections to ... more >>>

Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan

Cryptography relies on the computational hardness of structured problems. While one-way functions, the most basic cryptographic object, do not seem to require much structure, as we advance up the ranks into public-key cryptography and beyond, we seem to require that certain structured problems are hard. For example, factoring, quadratic residuosity, ... more >>>

Eric Allender, Klaus-Joern Lange

We present a deterministic algorithm running in space

O((log^2 n)/loglog n) solving the connectivity problem

on strongly unambiguous graphs. In addition, we present

an O(log n) time-bounded algorithm for this problem

running on a parallel pointer machine.

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

an m-variate polynomial of total degree at most d

over F. The tester is usually given access to an oracle

A providing the supposed restrictions of f to

affine subspaces of ...
more >>>

Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>

Swagato Sanyal

We prove that the Fourier dimension of any Boolean function with

Fourier sparsity $s$ is at most $O\left(s^{2/3}\right)$. Our proof

method yields an improved bound of $\widetilde{O}(\sqrt{s})$

assuming a conjecture of Tsang~\etal~\cite{tsang}, that for every

Boolean function of sparsity $s$ there is an affine subspace of

more >>>

Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith

We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>>

Ronitt Rubinfeld, Asaf Shapira

Sublinear time algorithms represent a new paradigm

in computing, where an algorithm must give some sort

of an answer after inspecting only a very small portion

of the input. We discuss the types of answers that

one can hope to achieve in this setting.

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari, Homin Lee

We show that all non-negative submodular functions have high noise-stability. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to any product distribution on $\{-1,1\}^n$ (for any constant accuracy parameter $\epsilon$ ). Our algorithm also succeeds in the agnostic setting. Previous work on learning submodular ... more >>>

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

more >>>

Venkatesan Guruswami, Chaoping Xing, chen yuan

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

Zeev Dvir, Shachar Lovett

In this work we describe an explicit, simple, construction of large subsets of F^n, where F is a finite field, that have small intersection with every k-dimensional affine subspace. Interest in the explicit construction of such sets, termed subspace-evasive sets, started in the work of Pudlak and Rodl (2004) ... more >>>

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits ... more >>>

Bernd Borchert, Antoni Lozano

This note connects two topics of Complexity Theory: The

topic of succinct circuit representations initiated by

Galperin and Wigderson and the topic of leaf languages

initiated by Bovet, Crescenzi, and Silvestri. It will be

shown for any language that its succinct version is

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

Michael Forbes, Amir Shpilka, Ben Lee Volk

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

Shlomi Dolev, Nova Fandina, Dan Gutfreund

Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue

in theoretical computer science.

In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$

time hard in the worst case (via randomized polynomial time ...
more >>>

Helmut Veith

In this paper, we present stronger results in the theory of succinct

problem representation by boolean circuits, and establish a close

relationship between succinct problems and leaf languages. As

a major tool, we use quantifierfree projection reductions

from descriptive complexity theory.

In particular, we show that the succinct upgrading ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Motivated by questions in property testing, we search for linear

error-correcting codes that have the ``single local orbit'' property:

i.e., they are specified by a single local

constraint and its translations under the symmetry group of the

code. We show that the dual of every ``sparse'' binary code

whose coordinates

more >>>

Adam Kurpisz, Samuli Lepp\"anen, Monaldo Mastrolilli

We introduce a method for proving Sum-of-Squares (SoS)/ Lasserre hierarchy lower bounds when the initial problem formulation exhibits a high degree of symmetry. Our main technical theorem allows us to reduce the study of the positive semidefiniteness to the analysis of ``well-behaved'' univariate polynomial inequalities.

We illustrate the technique on ... more >>>

Boaz Barak, David Steurer

In order to obtain the best-known guarantees, algorithms are traditionally tailored to the particular problem we want to solve. Two recent developments, the Unique Games Conjecture (UGC) and the Sum-of-Squares (SOS) method, surprisingly suggest that this tailoring is not necessary and that a single efficient algorithm could achieve best possible ... 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.

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

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

Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee

We prove the first time-space lower bound tradeoffs for randomized

computation of decision problems. The bounds hold even in the

case that the computation is allowed to have arbitrary probability

of error on a small fraction of inputs. Our techniques are an

extension of those used by Ajtai in his ...
more >>>

Oded Goldreich, Liav Teichner

We initiate a study of super-perfect zero-knowledge proof systems.

Loosely speaking, these are proof systems for which the interaction can be perfectly simulated in strict probabilistic polynomial-time.

In contrast, the standard definition of perfect zero-knowledge only requires that the interaction can be perfectly simulated

by a strict probabilistic polynomial-time that ...
more >>>

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the “short code” of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

In particular, we prove quasi-NP-hardness of the following problems on ... more >>>

Christoph Berkholz, Jakob Nordström

We show that there are CNF formulas which can be refuted in resolution

in both small space and small width, but for which any small-width

proof must have space exceeding by far the linear worst-case upper

bound. This significantly strengthens the space-width trade-offs in

[Ben-Sasson '09]}, and provides one more ...
more >>>

Venkatesan Guruswami, Krzysztof Onak

We prove $n^{1+\Omega(1/p)}/p^{O(1)}$ lower bounds for the space complexity of $p$-pass streaming algorithms solving the following problems on $n$-vertex graphs:

* testing if an undirected graph has a perfect matching (this implies lower bounds for computing a maximum matching or even just the maximum matching size),

* testing if two ... more >>>

Amitabha Roy, Christopher Wilson

A {\em supermodel} is a satisfying assignment of a boolean formula

for which any small alteration, such as a single bit flip, can be

repaired by another small alteration, yielding a nearby

satisfying assignment. We study computational problems associated

with super models and some generalizations thereof. For general

formulas, ...
more >>>

Mrinal Kumar, Shubhangi Saraf

In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree $n$ in $n^2$ variables such that any homogeneous depth 4 arithmetic circuit computing it must have size $n^{\Omega(\log \log n)}$.

Our results extend ... more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We study questions in incidence geometry where the precise position of points is `blurry' (e.g. due to noise, inaccuracy or error). Thus lines are replaced by narrow tubes, and more generally affine subspaces are replaced by their small neighborhood. We show that the presence of a sufficiently large number of ... more >>>

Laszlo Egri, Benoit Larose, Pascal Tesson

We introduce symmetric Datalog, a syntactic restriction of linear

Datalog and show that its expressive power is exactly that of

restricted symmetric monotone Krom SNP. The deep result of

Reingold on the complexity of undirected

connectivity suffices to show that symmetric Datalog queries can be

evaluated in logarithmic space. We ...
more >>>

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check" (LDPC) code for it to be locally testable, but few LDPC ... more >>>

Noam Nisan, Amnon Ta-Shma

We present a Logspace, many-one reduction from the undirected

st-connectivity problem to its complement. This shows that

$SL=co-SL$

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

We study the problem of representing symmetric Boolean functions as symmetric polynomials over Z_m. We show an equivalence between such

representations and simultaneous communication protocols. Computing a function with a polynomial of degree d modulo m=pq is equivalent to a two player protocol where one player is given the first ...
more >>>

Miklos Ajtai

Suppose that $p$ is a prime number $A$ is a finite set

with $n$ elements

and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the

elements of

$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an

$n$ is sufficiently large.) We will ...
more >>>

Felix Brandt, Felix Fischer, Markus Holzer

Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>>

Eric Allender, Klaus-Joern Lange

We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC$^1$ = LogCFL) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.

Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland

We introduce a new quantum adversary method to prove lower bounds on the query complexity of the quantum state generation problem. This problem encompasses both, the computation of partial or total functions and the preparation of target quantum states. There has been hope for quite some time that quantum ... more >>>

Giorgio Ausiello, Francesco Cristiano, Luigi Laura

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>

Moni Naor, Omer Reingold

A pseudo-random function is a fundamental cryptographic primitive

that is essential for encryption, identification and authentication.

We present a new cryptographic primitive called pseudo-random

synthesizer and show how to use it in order to get a

parallel construction of a pseudo-random function.

We show an $NC^1$ implementation of synthesizers ...
more >>>

Jin-Yi Cai

We show that the class ${\rm S}_2^p$ is a subclass of

${{\rm ZPP}^{\rm NP}}$. The proof uses universal hashing, approximate counting

and witness sampling. As a consequence, a collapse first noticed by

Samik Sengupta that the assumption NP has small circuits collapses

PH to ${\rm S}_2^p$

becomes the strongest version ...
more >>>