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

**L**

__
TR17-033
| 19th February 2017
__

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

Revisions: 2

__
TR04-002
| 8th January 2004
__

Troy Lee, Dieter van Melkebeek, Harry Buhrman#### Language Compression and Pseudorandom Generators

__
TR05-152
| 9th December 2005
__

Oded Lachish, Ilan Newman#### Languages that are Recognized by Simple Counter Automata are not necessarily Testable

__
TR04-014
| 26th November 2003
__

Chris Pollett#### Languages to diagonalize against advice classes

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR12-052
| 27th April 2012
__

Mohammad Mahmoody, David Xiao#### Languages with Efficient Zero-Knowledge PCPs are in SZK

__
TR19-068
| 27th April 2019
__

Shuo Pang#### LARGE CLIQUE IS HARD ON AVERAGE FOR RESOLUTION

__
TR12-042
| 17th April 2012
__

Chris Beck, Russell Impagliazzo, Shachar Lovett#### Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits

__
TR11-066
| 25th April 2011
__

Venkatesan Guruswami, Ali Kemal Sinop#### Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives

Revisions: 1

__
TR12-089
| 7th July 2012
__

Meena Boppana#### Lattice Variant of the Sensitivity Conjecture

__
TR06-147
| 27th November 2006
__

Chris Peikert, Alon Rosen#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

__
TR04-113
| 19th November 2004
__

Mårten Trolin#### Lattices with Many Cycles Are Dense

__
TR19-122
| 13th September 2019
__

Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters#### LDPC Codes Achieve List-Decoding Capacity

__
TR14-129
| 10th October 2014
__

Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski#### Leakage-resilient non-malleable codes

Revisions: 1

__
TR18-200
| 29th November 2018
__

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

__
TR10-074
| 20th April 2010
__

Parikshit Gopalan, Rocco Servedio#### Learning and Lower Bounds for AC$^0$ with Threshold Gates

__
TR14-144
| 30th October 2014
__

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan#### Learning circuits with few negations

__
TR11-115
| 8th August 2011
__

Varun Kanade, Thomas Steinke#### Learning Hurdles for Sleeping Experts

__
TR05-088
| 3rd August 2005
__

Jan Arpe#### Learning Juntas in the Presence of Noise

__
TR96-008
| 22nd January 1996
__

F. Bergadano, N.H. Bshouty, Stefano Varricchio#### Learning Multivariate Polynomials from Substitution and Equivalence Queries

__
TR00-069
| 14th July 2000
__

Peter Auer#### Learning Nested Differences in the Presence of Malicious Noise

__
TR00-055
| 14th July 2000
__

Peter Auer, Stephen Kwek, Manfred K. Warmuth#### Learning of Depth Two Neural Networks with Constant Fan-in at the Hidden Nodes

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR10-066
| 14th April 2010
__

Sanjeev Arora, Rong Ge#### Learning Parities with Structured Noise

Revisions: 1

__
TR98-060
| 8th October 1998
__

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan#### Learning polynomials with queries -- The highly noisy case.

__
TR07-129
| 25th October 2007
__

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan#### Learning Random Monotone DNF

__
TR17-046
| 8th March 2017
__

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

__
TR10-075
| 22nd April 2010
__

Ben Reichardt#### Least span program witness size equals the general adversary lower bound on quantum query complexity

__
TR09-062
| 28th July 2009
__

Daniele Venturi#### Lecture Notes on Algorithmic Number Theory

__
TR06-077
| 12th June 2006
__

Maria Lopez-Valdes#### Lempel-Ziv Dimension for Lempel-Ziv Compression

__
TR05-055
| 19th May 2005
__

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye#### Leontief Economies Encode Nonzero Sum Two-Player Games

__
TR11-168
| 9th December 2011
__

Joshua Grochow#### Lie algebra conjugacy

__
TR11-097
| 7th July 2011
__

Thomas Watson#### Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

Revisions: 1

__
TR17-165
| 3rd November 2017
__

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

__
TR16-048
| 11th March 2016
__

Olaf Beyersdorff, Leroy Chew, Renate Schmidt, Martin Suda#### Lifting QBF Resolution Calculi to DQBF

__
TR17-054
| 22nd March 2017
__

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

Revisions: 4

__
TR18-175
| 23rd October 2018
__

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

Revisions: 2

__
TR19-186
| 31st December 2019
__

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende#### Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity

Revisions: 2

__
TR10-123
| 4th August 2010
__

Eli Ben-Sasson#### Limitation on the rate of families of locally testable codes

Revisions: 1

__
TR08-007
| 6th February 2008
__

Dan Gutfreund, Salil Vadhan#### Limitations of Hardness vs. Randomness under Uniform Reductions

__
TR12-041
| 17th April 2012
__

Stasys Jukna#### Limitations of Incremental Dynamic Programs

Revisions: 1

__
TR16-017
| 24th December 2015
__

Georgios Stamoulis#### Limitations of Linear Programming Techniques for Bounded Color Matchings

__
TR12-075
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Limitations of Local Filters of Lipschitz and Monotone Functions

__
TR11-125
| 16th September 2011
__

Andrew Drucker#### Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

Revisions: 1
,
Comments: 1

__
TR04-026
| 17th February 2004
__

Scott Aaronson#### Limitations of Quantum Advice and One-Way Communication

__
TR15-201
| 10th December 2015
__

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

Revisions: 1

__
TR14-067
| 4th May 2014
__

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang#### Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

__
TR13-055
| 5th April 2013
__

David Gamarnik, Madhu Sudan#### Limits of local algorithms over sparse random graphs

__
TR15-198
| 30th November 2015
__

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

Revisions: 1

__
TR12-156
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### Limits of provable security for homomorphic encryption

Revisions: 1

__
TR12-065
| 16th May 2012
__

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran#### Limits of Random Oracles in Secure Computation

Revisions: 2

__
TR11-031
| 8th March 2011
__

Sam Buss, Ryan Williams#### Limits on Alternation-Trading Proofs for Time-Space Lower Bounds

__
TR17-060
| 9th April 2017
__

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

Revisions: 1

__
TR10-139
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Limits on the Computational Power of Random Strings

Revisions: 1

__
TR06-148
| 4th December 2006
__

Chris Peikert#### Limits on the Hardness of Lattice Problems in $\ell_p$ Norms

Revisions: 1

__
TR10-108
| 9th July 2010
__

Eli Ben-Sasson, Madhu Sudan#### Limits on the rate of locally testable affine-invariant codes

__
TR09-068
| 1st September 2009
__

Dave Buchfuhrer, Chris Umans#### Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms

__
TR09-013
| 4th February 2009
__

Atri Rudra#### Limits to List Decoding Random Codes

__
TR96-005
| 9th January 1996
__

Hans-Joerg Burtschick, Heribert Vollmer#### Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

__
TR05-042
| 15th April 2005
__

Lance Fortnow, Adam Klivans#### Linear Advice for Randomized Logarithmic Space

Revisions: 1

__
TR01-074
| 12th October 2001
__

Joshua Buresh-Oppenheim, David Mitchell#### Linear and Negative Resolution are Weaker than Resolution

Comments: 1

__
TR07-052
| 7th May 2007
__

Li Chen, Bin Fu#### Linear and Sublinear Time Algorithms for the Basis of Abelian Groups

Revisions: 2

__
TR14-141
| 24th October 2014
__

Shachar Lovett#### Linear codes cannot approximate the network capacity within any constant factor

__
TR99-025
| 2nd July 1999
__

Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan#### Linear Consistency Testing

__
TR05-100
| 30th August 2005
__

David Zuckerman#### Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

__
TR15-017
| 20th January 2015
__

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

__
TR16-182
| 14th November 2016
__

Rohit Gurjar, Thomas Thierauf#### Linear Matroid Intersection is in quasi-NC

__
TR07-033
| 14th February 2007
__

Michael Navon, Alex Samorodnitsky#### Linear programming bounds for codes via a covering argument

__
TR17-086
| 9th May 2017
__

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

Revisions: 1

__
TR16-174
| 7th November 2016
__

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev#### Linear Sketching over $\mathbb F_2$

Revisions: 5
,
Comments: 2

__
TR11-048
| 10th April 2011
__

Arkadev Chattopadhyay, Shachar Lovett#### Linear systems over abelian groups

__
TR09-084
| 24th September 2009
__

Arkadev Chattopadhyay, Avi Wigderson#### Linear systems over composite moduli

__
TR08-101
| 20th November 2008
__

Marek Karpinski, Warren Schudy#### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

__
TR11-058
| 15th April 2011
__

Michael Viderman#### Linear time decoding of regular expander codes

Revisions: 1

__
TR04-016
| 3rd March 2004
__

Michael Alekhnovich, Eli Ben-Sasson#### Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

__
TR12-073
| 11th June 2012
__

Venkatesan Guruswami, Carol Wang#### Linear-algebraic list decoding for variants of Reed-Solomon codes

__
TR14-015
| 24th January 2014
__

Jack H. Lutz, Neil Lutz#### Lines Missing Every Random Point

Revisions: 1

__
TR14-007
| 17th January 2014
__

Mark Braverman, Klim Efremenko#### List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise

__
TR11-165
| 8th December 2011
__

Elena Grigorescu, Chris Peikert#### List Decoding Barnes-Wall Lattices

Revisions: 2

__
TR14-087
| 12th July 2014
__

Abhishek Bhowmick, Shachar Lovett#### List decoding Reed-Muller codes over small fields

Revisions: 1

__
TR12-146
| 7th November 2012
__

Venkatesan Guruswami, Chaoping Xing#### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

__
TR08-105
| 26th November 2008
__

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra#### List Decoding Tensor Products and Interleaved Codes

__
TR03-042
| 15th May 2003
__

Luca Trevisan#### List Decoding Using the XOR Lemma

__
TR18-136
| 1st August 2018
__

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

__
TR02-024
| 24th April 2002
__

Piotr Indyk#### List-decoding in Linear Time

__
TR12-044
| 22nd April 2012
__

Swastik Kopparty#### List-Decoding Multiplicity Codes

__
TR11-020
| 20th December 2010
__

Yijia Chen, Joerg Flum#### Listings and logics

__
TR15-038
| 11th March 2015
__

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

Revisions: 1

__
TR18-141
| 6th August 2018
__

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

Revisions: 1

__
TR17-138
| 17th September 2017
__

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

Revisions: 1

__
TR16-129
| 16th August 2016
__

Emanuele Viola, Avi Wigderson#### Local Expanders

Revisions: 1

__
TR07-108
| 27th October 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Local Global Tradeoffs in Metric Embeddings

__
TR10-047
| 23rd March 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### Local list decoding with a constant number of queries

Revisions: 1

__
TR17-104
| 13th June 2017
__

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

Revisions: 1

__
TR09-115
| 13th November 2009
__

Swastik Kopparty, Shubhangi Saraf#### Local list-decoding and testing of random linear codes from high-error

__
TR16-163
| 25th October 2016
__

Matthew Hastings#### Local Maxima and Improved Exact Algorithm for MAX-2-SAT

__
TR19-127
| 19th September 2019
__

Noga Ron-Zewi, Ron Rothblum#### Local Proofs Approaching the Witness Length

__
TR15-128
| 10th August 2015
__

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

Revisions: 2

__
TR13-099
| 6th July 2013
__

Hamidreza Jahanjou, Eric Miles, Emanuele Viola#### Local reductions

Revisions: 3

__
TR17-126
| 7th August 2017
__

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

__
TR16-125
| 31st July 2016
__

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu#### Local Testing for Membership in Lattices

__
TR11-158
| 25th November 2011
__

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin#### Locality from Circuit Lower Bounds

__
TR13-098
| 28th June 2013
__

Benny Applebaum, Yoni Moses#### Locally Computable UOWHF with Linear Shrinkage

__
TR03-046
| 11th June 2003
__

Philippe Moser#### Locally Computed Baire's Categories on Small Complexity Classes

__
TR04-051
| 10th June 2004
__

Zdenek Dvorák, Daniel Král, Ondrej Pangrác#### Locally consistent constraint satisfaction problems

__
TR14-107
| 10th August 2014
__

Or Meir#### Locally Correctable and Testable Codes Approaching the Singleton Bound

Revisions: 2

__
TR07-040
| 12th April 2007
__

Kiran Kedlaya, Sergey Yekhanin#### Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers

__
TR05-044
| 6th April 2005
__

Zeev Dvir, Amir Shpilka#### Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

__
TR13-115
| 27th August 2013
__

Daniele Micciancio#### Locally Dense Codes

__
TR03-050
| 16th June 2003
__

Daniel Král#### Locally satisfiable formulas

__
TR16-122
| 11th August 2016
__

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf#### Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound

__
TR09-128
| 29th November 2009
__

Gillat Kol, Ran Raz#### Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist

__
TR13-114
| 24th August 2013
__

Parikshit Gopalan, Salil Vadhan, Yuan Zhou#### Locally Testable Codes and Cayley Graphs

Revisions: 1

__
TR02-050
| 5th August 2002
__

Oded Goldreich, Madhu Sudan#### Locally Testable Codes and PCPs of Almost-Linear Length

__
TR09-126
| 26th November 2009
__

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman#### Locally Testable Codes Require Redundant Testers

Revisions: 3

__
TR19-117
| 4th September 2019
__

Silas Richelson, Sourya Roy#### Locally Testable Non-Malleable Codes

__
TR10-130
| 18th August 2010
__

Tali Kaufman, Michael Viderman#### Locally Testable vs. Locally Decodable Codes

Revisions: 1

__
TR19-149
| 4th November 2019
__

Dean Doron, Pooya Hatami, William Hoza#### Log-Seed Pseudorandom Generators via Iterated Restrictions

__
TR01-013
| 2nd February 2001
__

Michal Koucky#### Log-space Constructible Universal Traversal Sequences for Cycles of Length $O(n^{4.03})$

__
TR07-091
| 10th September 2007
__

Martin Grohe#### Logic, Graphs, and Algorithms

__
TR16-154
| 21st September 2016
__

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor#### Logical Induction

__
TR01-088
| 29th October 2001
__

Alexander Shen, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity

__
TR01-089
| 29th October 2001
__

Andrej Muchnik, Nikolay Vereshchagin#### Logical operations and Kolmogorov complexity. II

__
TR03-077
| 4th September 2003
__

Till Tantau#### Logspace Optimisation Problems and their Approximation Properties

__
TR09-050
| 28th May 2009
__

Jan Kyncl, Tomas Vyskocil#### Logspace reduction of directed reachability for bounded genus graphs to the planar case

__
TR10-062
| 7th April 2010
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Logspace Versions of the Theorems of Bodlaender and Courcelle

__
TR96-060
| 19th November 1996
__

Bernd Borchert, Frank Stephan#### Looking for an Analogue of Rice's Theorem in Complexity Theory

__
TR18-017
| 26th January 2018
__

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

__
TR07-080
| 7th August 2007
__

Chris Peikert, Brent Waters#### Lossy Trapdoor Functions and Their Applications

__
TR09-127
| 25th November 2009
__

Brett Hemenway, Rafail Ostrovsky#### Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems

Revisions: 2

__
TR17-180
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Low degree almost Boolean functions are sparse juntas

__
TR15-111
| 8th July 2015
__

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

Revisions: 1

__
TR10-004
| 6th January 2010
__

Eli Ben-Sasson, Michael Viderman#### Low Rate Is Insufficient for Local Testability

Revisions: 3

__
TR11-095
| 22nd June 2011
__

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie#### Low uniform versions of NC1

Revisions: 1

__
TR17-008
| 14th January 2017
__

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

__
TR06-054
| 16th April 2006
__

Alex Samorodnitsky#### Low-degree tests at large distances

__
TR13-177
| 10th December 2013
__

Eric Allender, Nikhil Balaji, Samir Datta#### Low-depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs

Revisions: 1

__
TR06-125
| 20th September 2006
__

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto#### Low-Depth Witnesses are Easy to Find

__
TR07-069
| 29th July 2007
__

Ronen Shaltiel, Chris Umans#### Low-end uniform hardness vs. randomness tradeoffs for AM

__
TR16-106
| 15th July 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Low-error two-source extractors for polynomial min-entropy

Revisions: 1

__
TR16-084
| 23rd May 2016
__

Shalev Ben-David#### Low-Sensitivity Functions from Unambiguous Certificates

__
TR15-139
| 25th August 2015
__

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

__
TR18-053
| 19th March 2018
__

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

__
TR16-153
| 28th September 2016
__

Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah#### Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials

Revisions: 3

__
TR12-007
| 28th January 2012
__

Ruiwen Chen, Valentine Kabanets#### Lower Bounds against Weakly Uniform Circuits

Revisions: 1

__
TR10-022
| 23rd February 2010
__

Vitaly Feldman, Homin Lee, Rocco Servedio#### Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas

__
TR17-077
| 30th April 2017
__

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

__
TR08-006
| 18th January 2008
__

Ran Raz, Amir Yehudayoff#### Lower Bounds and Separations for Constant Depth Multilinear Circuits

__
TR98-036
| 11th June 1998
__

Vince Grolmusz, Gábor Tardos#### Lower Bounds for (MOD p -- MOD m) Circuits

__
TR19-128
| 24th September 2019
__

Anna Gal, Robert Robere#### Lower Bounds for (Non-monotone) Comparator Circuits

__
TR16-189
| 21st November 2016
__

Arnab Bhattacharyya, Sivakanth Gopi#### Lower bounds for 2-query LCCs over large alphabet

__
TR16-107
| 17th July 2016
__

Nathanael Fijalkow#### Lower Bounds for Alternating Online Space Complexity

Revisions: 1

__
TR14-026
| 27th February 2014
__

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf#### Lower Bounds for Approximate LDCs

__
TR17-185
| 28th November 2017
__

Makrand Sinha#### Lower Bounds for Approximating the Matching Polytope

__
TR18-180
| 3rd November 2018
__

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

__
TR08-032
| 18th March 2008
__

Dmitriy Cherukhin#### Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates

__
TR03-004
| 24th December 2002
__

Eli Ben-Sasson, Prahladh Harsha#### Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

__
TR18-154
| 7th September 2018
__

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

__
TR06-079
| 12th June 2006
__

Kristoffer Arnsfelt Hansen#### Lower Bounds for Circuits with Few Modular Gates using Exponential Sums

__
TR95-027
| 30th May 1995
__

Frederic Green#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

__
TR15-012
| 24th January 2015
__

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

__
TR15-185
| 24th November 2015
__

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

__
TR18-186
| 6th November 2018
__

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

Revisions: 1

__
TR13-100
| 15th July 2013
__

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan#### Lower bounds for depth $4$ formulas computing iterated matrix multiplication

__
TR13-068
| 3rd May 2013
__

Mrinal Kumar, Shubhangi Saraf#### Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin

__
TR14-089
| 16th July 2014
__

Neeraj Kayal, Chandan Saha#### Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin

Revisions: 1

__
TR10-120
| 27th July 2010
__

Noa Eidelstein, Alex Samorodnitsky#### Lower bounds for designs in symmetric spaces

__
TR18-181
| 30th October 2018
__

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

__
TR13-116
| 29th August 2013
__

Albert Atserias, Moritz Müller, Sergi Oliva#### Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle

__
TR16-165
| 30th October 2016
__

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Lower Bounds for Elimination via Weak Regularity

__
TR07-137
| 6th November 2007
__

Yijia Chen, Jörg Flum, Moritz Müller#### Lower Bounds for Kernelizations

__
TR19-007
| 17th January 2019
__

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh#### Lower Bounds for Linear Decision Lists

__
TR01-080
| 14th November 2001
__

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan#### Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval

Revisions: 3

__
TR99-019
| 7th June 1999
__

Detlef Sieling#### Lower Bounds for Linear Transformed OBDDs and FBDDs

__
TR03-057
| 21st July 2003
__

Scott Aaronson#### Lower Bounds for Local Search by Quantum Arguments

__
TR05-053
| 4th May 2005
__

Paul Beame, Nathan Segerlind#### Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity

__
TR19-047
| 2nd April 2019
__

Mrinal Kumar, Ben Lee Volk#### Lower Bounds for Matrix Factorization

__
TR01-060
| 23rd August 2001
__

Amir Shpilka#### Lower bounds for matrix product

__
TR00-029
| 30th April 2000
__

Ran Raz, Amir Shpilka#### Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates

Revisions: 1

__
TR14-169
| 9th December 2014
__

Stasys Jukna#### Lower Bounds for Monotone Counting Circuits

__
TR97-032
| 11th July 1997
__

Jan Johannsen#### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes

__
TR95-001
| 1st January 1995
__

Amos Beimel, Anna Gal, Michael S. Paterson#### Lower Bounds for Monotone Span Programs

__
TR07-014
| 23rd January 2007
__

Amit Chakrabarti#### Lower Bounds for Multi-Player Pointer Jumping

__
TR12-141
| 22nd October 2012
__

Dmitry Itsykson, Dmitry Sokolov#### Lower bounds for myopic DPLL algorithms with a cut heuristic

__
TR04-083
| 8th September 2004
__

Boaz Barak, Yehuda Lindell, Salil Vadhan#### Lower Bounds for Non-Black-Box Zero Knowledge

__
TR00-042
| 21st June 2000
__

Lars Engebretsen#### Lower Bounds for non-Boolean Constraint Satisfaction

Revisions: 1

__
TR15-022
| 9th February 2015
__

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

Revisions: 1

__
TR01-020
| 20th February 2001
__

N. S. Narayanaswamy, C.E. Veni Madhavan#### Lower Bounds for OBDDs and Nisan's pseudorandom generator

__
TR19-055
| 9th April 2019
__

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo#### Lower Bounds for Oblivious Near-Neighbor Search

__
TR13-083
| 7th June 2013
__

Miklos Ajtai#### Lower Bounds for RAMs and Quantifier Elimination

__
TR15-073
| 25th April 2015
__

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

__
TR02-064
| 14th November 2002
__

Andrej Bogdanov, Luca Trevisan#### Lower Bounds for Testing Bipartiteness in Dense Graphs

__
TR13-036
| 13th March 2013
__

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev#### Lower Bounds for Testing Properties of Functions on Hypergrid Domains

Revisions: 1

__
TR09-066
| 13th August 2009
__

Arnab Bhattacharyya, Ning Xie#### Lower Bounds for Testing Triangle-freeness in Boolean Functions

__
TR14-150
| 10th November 2014
__

Justin Thaler#### Lower Bounds for the Approximate Degree of Block-Composed Functions

Revisions: 3

__
TR14-139
| 31st October 2014
__

Hong Van Le#### Lower bounds for the circuit size of partially homogeneous polynomials

Revisions: 1

__
TR94-019
| 12th December 1994
__

#### Lower Bounds for the Computational Power of Networks of Spiking

__
TR95-034
| 30th June 1995
__

Christoph Meinel, Stephan Waack#### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

__
TR97-042
| 22nd September 1997
__

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall#### Lower Bounds for the Polynomial Calculus and the Groebner Basis Algorithm

__
TR03-068
| 30th July 2003
__

Matthias Homeister#### Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs

__
TR18-094
| 2nd May 2018
__

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

__
TR14-080
| 11th June 2014
__

Stasys Jukna#### Lower Bounds for Tropical Circuits and Dynamic Programs

Revisions: 1

__
TR10-085
| 20th May 2010
__

Eli Ben-Sasson, Jan Johannsen#### Lower bounds for width-restricted clause learning on small width formulas

__
TR19-026
| 28th February 2019
__

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff#### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Revisions: 1

__
TR16-050
| 31st March 2016
__

Roei Tell#### Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

Revisions: 1

__
TR12-038
| 6th April 2012
__

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao#### Lower bounds on information complexity via zero-communication protocols and applications

__
TR12-108
| 4th September 2012
__

Arkadev Chattopadhyay, Rahul Santhanam#### Lower Bounds on Interactive Compressibility by Constant-Depth Circuits

__
TR00-002
| 23rd December 1999
__

Michael Schmitt#### Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks

__
TR04-120
| 22nd November 2004
__

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis#### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a

__
TR00-022
| 2nd May 2000
__

Rosario Gennaro, Luca Trevisan#### Lower bounds on the efficiency of generic cryptographic constructions

__
TR11-016
| 7th February 2011
__

Sergei Artemenko, Ronen Shaltiel#### Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

Revisions: 1

__
TR09-010
| 29th January 2009
__

Nikos Leonardos, Michael Saks#### Lower bounds on the randomized communication complexity of read-once functions

__
TR17-190
| 6th November 2017
__

Anirbit Mukherjee, Amitabh Basu#### Lower bounds over Boolean inputs for deep neural networks with ReLU gates.

__
TR98-015
| 16th January 1998
__

Valentin E. Brimkov, Stefan S. Dantchev#### Lower Bounds, "Pseudopolynomial" and Approximation Algorithms for the Knapsack Problem with Real Coefficients

__
TR15-133
| 12th August 2015
__

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

Daniel Kane, Shachar Lovett, Sankeerth Rao

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

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

Troy Lee, Dieter van Melkebeek, Harry Buhrman

The language compression problem asks for succinct descriptions of

the strings in a language A such that the strings can be efficiently

recovered from their description when given a membership oracle for

A. We study randomized and nondeterministic decompression schemes

and investigate how close we can get to the information ...
more >>>

Oded Lachish, Ilan Newman

Combinatorial property testing deals with the following relaxation of

decision problems: Given a fixed property and an input $f$, one wants

to decide whether $f$ satisfies the property or is `far' from satisfying

the property.

It has been shown that regular languages are testable,

and that there exist context free ...
more >>>

Chris Pollett

Variants of Kannan's Theorem are given where the circuits of

the original theorem are replaced by arbitrary recursively presentable

classes of languages that use advice strings and satisfy certain mild

conditions. These variants imply that $\DTIME(n^{k'})^{\NE}/n^k$

does not contain $\PTIME^{\NE}$, $\DTIME(2^{n^{k'}})/n^k$ does

not contain $\EXP$, $\SPACE(n^{k'})/n^k$ does not ...
more >>>

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

Mohammad Mahmoody, David Xiao

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages in $NEXP$. Ishai, Mahmoody, and Sahai (TCC '12), motivated by cryptographic applications, ... more >>>

Shuo Pang

We prove resolution lower bounds for $k$-Clique on the Erdos-Renyi random graph $G(n,n^{-{2\xi}\over{k-1}})$ (where $\xi>1$ is constant). First we show for $k=n^{c_0}$, $c_0\in(0,1/3)$, an $\exp({\Omega(n^{(1-\epsilon)c_0})})$ average lower bound on resolution where $\epsilon$ is arbitrary constant.

We then propose the model of $a$-irregular resolution. Extended from regular resolution, this model ... more >>>

Chris Beck, Russell Impagliazzo, Shachar Lovett

There has been considerable interest lately in the complexity of distributions. Recently, Lovett and Viola (CCC 2011) showed that the statistical distance between a uniform distribution over a good code, and any distribution which can be efficiently sampled by a small bounded-depth AC0 circuit, is inverse-polynomially close to one. That ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These ... more >>>

Meena Boppana

The Sensitivity Conjecture, posed in 1994, states that the fundamental measures known as the sensitivity and block sensitivity of a Boolean function $f$, $s(f)$ and $bs(f)$ respectively, are polynomially related. It is known that $bs(f)$ is polynomially related to important measures in computer science including the decision-tree depth, polynomial degree, ... more >>>

Chris Peikert, Alon Rosen

We demonstrate an \emph{average-case} problem which is as hard as

finding $\gamma(n)$-approximate shortest vectors in certain

$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n)

= O(\sqrt{\log n})$. The previously best known factor for any class

of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

Mårten Trolin

We give a method for approximating any $n$-dimensional

lattice with a lattice $\Lambda$ whose factor group

$\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length

with arbitrary precision. We also show that a direct

consequence of this is that the Shortest Vector Problem and the Closest

Vector Problem cannot ...
more >>>

Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>>

Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this ... more >>>

Ashutosh Kumar, Raghu Meka, Amit Sahai

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

Parikshit Gopalan, Rocco Servedio

In 2002 Jackson et al. [JKS02] asked whether AC0 circuits augmented with a threshold gate at the output can be efficiently learned from uniform random examples. We answer this question affirmatively by showing that such circuits have fairly strong Fourier concentration; hence the low-degree algorithm of Linial, Mansour and Nisan ... more >>>

Eric Blais, Clement Canonne, Igor Carboni Oliveira, Rocco Servedio, Li-Yang Tan

Monotone Boolean functions, and the monotone Boolean circuits that compute them, have been intensively studied in complexity theory. In this paper we study the structure of Boolean functions in terms of the minimum number of negations in any circuit computing them, a complexity measure that interpolates between monotone functions and ... more >>>

Varun Kanade, Thomas Steinke

We study the online decision problem where the set of available actions varies over time, also called the sleeping experts problem. We consider the setting where the performance comparison is made with respect to the best ordering of actions in hindsight. In this paper, both the payoff function and the ... more >>>

Jan Arpe

The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>>

F. Bergadano, N.H. Bshouty, Stefano Varricchio

It has been shown in previous recent work that

multiplicity automata are predictable from multiplicity

and equivalence queries. In this paper we generalize

related notions in a matrix representation

and obtain a basis for the solution

of a number of open problems in learnability theory.

Membership queries are generalized ...
more >>>

Peter Auer

We present a PAC-learning algorithm and an on-line learning algorithm

for nested differences of intersection-closed classes. Examples of

intersection-closed classes include axis-parallel rectangles,

monomials, and linear sub-spaces. Our PAC-learning algorithm uses a

pruning technique that we rigorously proof correct. As a result we

show that ...
more >>>

Peter Auer, Stephen Kwek, Manfred K. Warmuth

We present algorithms for learning depth two neural networks where the

hidden nodes are threshold gates with constant fan-in. The transfer

function of the output node might be more general: we have results for

the cases when the threshold function, the logistic function or the

identity function is ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Sanjeev Arora, Rong Ge

In the {\em learning parities with noise} problem ---well-studied in learning theory and cryptography--- we

have access to an oracle that, each time we press a button,

returns a random vector $ a \in \GF(2)^n$ together with a bit $b \in \GF(2)$ that was computed as

$a\cdot u +\eta$, where ...
more >>>

Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

This is a revised version of work which has appeared

in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field

$F$ into $F$,

we consider the task of reconstructing a list of all $n$-variate

degree $d$ polynomials which agree with $f$

more >>>

Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan

We give an algorithm that with high probability properly learns random monotone t(n)-term

DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ...
more >>>

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

Residuality plays an essential role for learning finite automata.

While residual deterministic and nondeterministic

automata have been understood quite well, fundamental

questions concerning alternating automata (AFA) remain open.

Recently, Angluin, Eisenstat, and Fisman have initiated

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

-an extension of ...
more >>>

Ben Reichardt

Span programs form a linear-algebraic model of computation, with span program "size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these ... more >>>

Daniele Venturi

The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves.

Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption ...
more >>>

Maria Lopez-Valdes

This paper describes the Lempel-Ziv dimension (Hausdorff like

dimension inspired in the LZ78 parsing), its fundamental properties

and relation with Hausdorff dimension.

It is shown that in the case of individual infinite sequences, the

Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv

compression ratio.

This fact is used to describe results ... more >>>

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

We give a reduction from any two-player game to a special case of

the Leontief exchange economy, with the property that the Nash equilibria of the game and the

equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain

families of market ...
more >>>

Joshua Grochow

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set $\mathcal{L}$ of matrices such that $A,B \in \mathcal{L}$ implies$AB - BA \in ... more >>>

Thomas Watson

We study the lift-and-project procedures of Lovasz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We ... more >>>

Toniann Pitassi, Robert Robere

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

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

Olaf Beyersdorff, Leroy Chew, Renate Schmidt, Martin Suda

We examine the existing Resolution systems for quantified Boolean formulas (QBF) and answer the question which of these calculi can be lifted to the more powerful Dependency QBFs (DQBF). An interesting picture emerges: While for QBF we have the strict chain of proof systems Q-Resolution < IR-calc < IRM-calc, the ... more >>>

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

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

Bruno Loff, Sagnik Mukhopadhyay

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

Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna de Rezende

We significantly strengthen and generalize the theorem lifting Nullstellensatz degree to monotone span program size by Pitassi and Robere (2018) so that it works for any gadget with high enough rank, in particular, for useful gadgets such as equality and greater-than. We apply our generalized theorem to solve two open ... more >>>

Eli Ben-Sasson

This paper describes recent results which revolve around the question of the rate attainable by families of error correcting codes that are locally testable. Emphasis is placed on motivating the problem of proving upper bounds on the rate of these codes and a number of interesting open questions for future ... more >>>

Dan Gutfreund, Salil Vadhan

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>

Stasys Jukna

We consider so-called ``incremental'' dynamic programming (DP) algorithms, and are interested in the number of subproblems produced by them. The standard DP algorithm for the n-dimensional Knapsack problem is incremental, and produces nK subproblems, where K is the capacity of the knapsack. We show that any incremental algorithm for this ... more >>>

Georgios Stamoulis

Given a weighted graph $G = (V,E,w)$, with weight function $w: E \rightarrow \mathbb{Q^+}$, a \textit{matching} $M$ is a set of pairwise non-adjacent edges. In the optimization setting, one seeks to find a matching of \textit{maximum} weight. In the \textit{multi-criteria} (or \textit{multi-budgeted}) setting, we are also given $\ell$ length functions ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

We study local filters for two properties of functions $f:\B^d\to \mathbb{R}$: the Lipschitz property and monotonicity. A local filter with additive error $a$ is a randomized algorithm that is given black-box access to a function $f$ and a query point $x$ in the domain of $f$. Its output is a ... more >>>

Andrew Drucker

We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show ... more >>>

Scott Aaronson

Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones.

First, we show that BQP/qpoly is contained in ...
more >>>

C Ramya, Raghavendra Rao B V

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

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

Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>

David Gamarnik, Madhu Sudan

Local algorithms on graphs are algorithms that run in parallel on the nodes of a graph to compute some global structural feature of the graph. Such algorithms use only local information available at nodes to determine local aspects of the global structure, while also potentially using some randomness. Recent research ... more >>>

Shuichi Hirahara, Osamu Watanabe

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

Andrej Bogdanov, Chin Ho Lee

We show that public-key bit encryption schemes which support weak homomorphic evaluation of parity or majority cannot be proved message indistinguishable beyond AM intersect coAM via general (adaptive) reductions, and beyond statistical zero-knowledge via reductions of constant query complexity.

Previous works on the limitation of reductions for proving security of ... more >>>

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

The seminal result of Impagliazzo and Rudich (STOC 1989) gave a black-box separation between one-way functions and public-key encryption: informally, a public-key encryption scheme cannot be constructed using one-way functions as the sole source of computational hardness. In addition, this implied a black-box separation between one-way functions and protocols for ... more >>>

Sam Buss, Ryan Williams

This paper characterizes alternation trading based proofs that satisfiability is not in the time and space bounded class $\DTISP(n^c, n^\epsilon)$, for various values $c<2$ and $\epsilon<1$. We characterize exactly what can be proved in the $\epsilon=0$ case with currently known methods, and prove the conjecture of Williams that $c=2\cos(\pi/7)$ is ... more >>>

Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari

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

Eric Allender, Luke Friedman, William Gasarch

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

Chris Peikert

We show that for any $p \geq 2$, lattice problems in the $\ell_p$

norm are subject to all the same limits on hardness as are known

for the $\ell_2$ norm. In particular, for lattices of dimension

$n$:

* Approximating the shortest and closest vector in ... more >>>

Eli Ben-Sasson, Madhu Sudan

A linear code is said to be affine-invariant if the coordinates of the code can be viewed as a vector space and the code is invariant under an affine transformation of the coordinates. A code is said to be locally testable if proximity of a received word

to the code ...
more >>>

Dave Buchfuhrer, Chris Umans

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Atri Rudra

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

Hans-Joerg Burtschick, Heribert Vollmer

We show that examinations of the expressive power of logical formulae

enriched by Lindstroem quantifiers over ordered finite structures

have a well-studied complexity-theoretic counterpart: the leaf

language approach to define complexity classes. Model classes of

formulae with Lindstroem quantifiers are nothing else than leaf

language definable sets. Along the ...
more >>>

Lance Fortnow, Adam Klivans

We show that RL is contained in L/O(n), i.e., any language computable

in randomized logarithmic space can be computed in deterministic

logarithmic space with a linear amount of non-uniform advice. To

prove our result we show how to take an ultra-low space walk on

the Gabber-Galil expander graph.

Joshua Buresh-Oppenheim, David Mitchell

We prove exponential separations between the sizes of

particular refutations in negative, respectively linear, resolution and

general resolution. Only a superpolynomial separation between negative

and general resolution was previously known. Our examples show that there

is no strong relationship between the size and width of refutations in

negative and ...
more >>>

Li Chen, Bin Fu

It is well known that every finite Abelian group $G$ can be

represented as a product of cyclic groups: $G=G_1\times

G_2\times\cdots G_t$, where each $G_i$ is a cyclic group of size

$p^j$ for some prime $p$ and integer $j\ge 1$. If $a_i$ is the

generator of the cyclic group of ...
more >>>

Shachar Lovett

Network coding studies the capacity of networks to carry information, when internal nodes are allowed to actively encode information. It is known that for multi-cast networks, the network coding capacity can be achieved by linear codes. It is also known not to be true for general networks. The best separation ... more >>>

Yonatan Aumann, Johan Hastad, Michael O. Rabin, Madhu Sudan

We extend the notion of linearity testing to the task of checking

linear-consistency of multiple functions. Informally, functions

are ``linear'' if their graphs form straight lines on the plane.

Two such functions are ``consistent'' if the lines have the same

slope. We propose a variant of a test of ...
more >>>

David Zuckerman

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>

Bruno Bauwens, Marius Zimand

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

Rohit Gurjar, Thomas Thierauf

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>

Michael Navon, Alex Samorodnitsky

We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, ... more >>>

C Ramya, Raghavendra Rao B V

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

Elchanan Mossel, Sampath Sampath Kannan, Grigory Yaroslavtsev

We initiate a systematic study of linear sketching over $\mathbb F_2$. For a given Boolean function $f \colon \{0,1\}^n \to \{0,1\}$ a randomized $\mathbb F_2$-sketch is a distribution $\mathcal M$ over $d \times n$ matrices with elements over $\mathbb F_2$ such that $\mathcal Mx$ suffices for computing $f(x)$ with high ... more >>>

Arkadev Chattopadhyay, Shachar Lovett

We consider a system of linear constraints over any finite Abelian group $G$ of the following form: $\ell_i(x_1,\ldots,x_n) \equiv \ell_{i,1}x_1+\cdots+\ell_{i,n}x_n \in A_i$ for $i=1,\ldots,t$ and each $A_i \subset G$, $\ell_{i,j}$ is an element of $G$ and $x_i$'s are Boolean variables. Our main result shows that the subset of the Boolean ... more >>>

Arkadev Chattopadhyay, Avi Wigderson

We study solution sets to systems of generalized linear equations of the following form:

$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,

where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ...
more >>>

Marek Karpinski, Warren Schudy

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

Michael Viderman

Sipser and Spielman (IEEE IT, 1996) showed that any $(c,d)$-regular expander code with expansion parameter $> \frac{3}{4}$ is decodable in \emph{linear time} from a constant fraction of errors. Feldman et al. (IEEE IT, 2007)

proved that expansion parameter $> \frac{2}{3} + \frac{1}{3c}$ is sufficient to correct a constant fraction of ...
more >>>

Michael Alekhnovich, Eli Ben-Sasson

We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time

of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ...
more >>>

Venkatesan Guruswami, Carol Wang

Folded Reed-Solomon codes are an explicit family of codes that achieve the optimal trade-off between rate and list error-correction capability. Specifically, for any $\epsilon > 0$, Guruswami and Rudra presented an $n^{O(1/\epsilon)}$ time algorithm to list decode appropriate folded RS codes of rate $R$ from a fraction $1-R-\epsilon$ of ... more >>>

Jack H. Lutz, Neil Lutz

This paper proves that there is, in every direction in Euclidean space, a line that misses every computably random point. Our proof of this fact shows that a famous set constructed by Besicovitch in 1964 has computable measure 0.

more >>>Mark Braverman, Klim Efremenko

In this paper we extend the notion of list decoding to the setting of interactive communication and study its limits. In particular, we show that any protocol can be encoded, with a constant rate, into a list-decodable protocol which is resilient

to a noise rate of up to $1/2-\varepsilon$, ...
more >>>

Elena Grigorescu, Chris Peikert

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>

Abhishek Bhowmick, Shachar Lovett

The list decoding problem for a code asks for the maximal radius up to which any ball of that radius contains only a constant number of codewords. The list decoding radius is not well understood even for well studied codes, like Reed-Solomon or Reed-Muller codes.

Fix a finite field $\mathbb{F}$. ... more >>>

Venkatesan Guruswami, Chaoping Xing

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra, Prasad Raghavendra

We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes.

1)We show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one ... more >>>

Luca Trevisan

We show that Yao's XOR Lemma, and its essentially equivalent

rephrasing as a Direct Product Lemma, can be

re-interpreted as a way of obtaining error-correcting

codes with good list-decoding algorithms from error-correcting

codes having weak unique-decoding algorithms. To get codes

with good rate and efficient list decoding algorithms

one needs ...
more >>>

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

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

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

Piotr Indyk

Spielman showed that one can construct error-correcting codes capable

of correcting a constant fraction $\delta << 1/2$ of errors,

and that are encodable/decodable in linear time.

Guruswami and Sudan showed that it is possible to correct

more than $50\%$ of errors (and thus exceed the ``half of the ...
more >>>

Swastik Kopparty

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

Yijia Chen, Joerg Flum

There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is ... more >>>

Gil Cohen

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

Sandip Sinha, Omri Weinstein

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

Srikanth Srinivasan, Madhu Sudan

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

polynomials of total degree at most $d$ over

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

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

In this work we explore their local

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

Emanuele Viola, Avi Wigderson

Abstract A map $f:{0,1}^{n}\to {0,1}^{n}$ has locality t if every output bit of f depends only on t input bits. Arora, Steurer, and Wigderson (2009) ask if there exist bounded-degree expander graphs on $2^{n}$ nodes such that the neighbors of a node $x\in {0,1}^{n}$ can be computed by maps of ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

Suppose that every k points in a n point metric space X are D-distortion embeddable into l_1. We give upper and lower bounds on the distortion required to embed the entire space X into l_1. This is a natural mathematical question and is also motivated by the study of relaxations ... more >>>

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma

Recently Efremenko showed locally-decodable codes of sub-exponential

length. That result showed that these codes can handle up to

$\frac{1}{3} $ fraction of errors. In this paper we show that the

same codes can be locally unique-decoded from error rate

$\half-\alpha$ for any $\alpha>0$ and locally list-decoded from

error rate $1-\alpha$ ...
more >>>

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

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

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

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Matthew Hastings

Given a MAX-2-SAT instance, we define a local maximum to be an assignment such that changing any single variable reduces the number of satisfied clauses. We consider the question of the number of local maxima hat an instance of MAX-2-SAT can have. We give upper bounds in both the sparse ... more >>>

Noga Ron-Zewi, Ron Rothblum

Interactive oracle proofs (IOPs) are a hybrid between interactive proofs and PCPs. In an IOP the prover is allowed to interact with a verifier (like in an interactive proof) by sending relatively long messages to the verifier, who in turn is only allowed to query a few of the bits ... more >>>

Roee David, Elazar Goldenberg, Robert Krauthgamer

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

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

Hamidreza Jahanjou, Eric Miles, Emanuele Viola

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT

instance $\phi$ of size $|\phi| = T \cdot \log^{O(1)} T$

such that there is an explicit circuit $C$ that on input

an index $i$ of $\log |\phi|$ bits outputs the $i$th

clause, and each output bit of $C$ depends on ...
more >>>

Swastik Kopparty, Shubhangi Saraf

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

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

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu

Motivated by the structural analogies between point lattices and linear error-correcting codes, and by the mature theory on locally testable codes, we initiate a systematic study of local testing for membership in lattices. Testing membership in lattices is also motivated in practice, by applications to integer programming, error detection in ... more >>>

Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

Benny Applebaum, Yoni Moses

We study the problem of constructing locally computable Universal One-Way Hash Functions (UOWHFs) $H:\{0,1\}^n \rightarrow \{0,1\}^m$. A construction with constant \emph{output locality}, where every bit of the output depends only on a constant number of bits of the input, was established by [Applebaum, Ishai, and Kushilevitz, SICOMP 2006]. However, this ... more >>>

Philippe Moser

We strengthen an earlier notion of

resource-bounded Baire's categories, and define

resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP

and on probabilistic complexity classes such as BPP.

We give an alternative characterization of meager sets via resource-bounded

Banach Mazur games.

We show that the class ...
more >>>

Zdenek Dvorák, Daniel Král, Ondrej Pangrác

An instance of a constraint satisfaction problem is $l$-consistent

if any $l$ constraints of it can be simultaneously satisfied.

For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ...
more >>>

Or Meir

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are codes that admit local algorithms for decoding and testing respectively. The local algorithms are randomized algorithms that make only a small number of queries to their input. LCCs and LTCs are both interesting in their own right, and have important applications in ... more >>>

Kiran Kedlaya, Sergey Yekhanin

A k-query Locally Decodable Code (LDC) encodes an n-bit message x as an N-bit codeword C(x), such that one can probabilistically recover any bit x_i of the message by querying only k bits of the codeword C(x), even after some constant fraction of codeword bits has been corrupted. The major ... more >>>

Zeev Dvir, Amir Shpilka

In this work we study two seemingly unrelated notions. Locally Decodable Codes(LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing ... more >>>

Daniele Micciancio

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>

Daniel Král

A CNF formula is k-satisfiable if each k clauses of it can be satisfied

simultaneously. Let \pi_k be the largest real number such that for each

k-satisfiable formula with variables x_i, there are probabilities p_i

with the following property: If each variable x_i is chosen randomly and

independently to be ...
more >>>

Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf

One of the most important open problems in the theory

of error-correcting codes is to determine the

tradeoff between the rate $R$ and minimum distance $\delta$ of a binary

code. The best known tradeoff is the Gilbert-Varshamov bound,

and says that for every $\delta \in (0, 1/2)$, there are ...
more >>>

Gillat Kol, Ran Raz

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>

Parikshit Gopalan, Salil Vadhan, Yuan Zhou

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ...
more >>>

Oded Goldreich, Madhu Sudan

Locally testable codes are error-correcting codes that admit

very efficient codeword tests. Specifically, using a constant

number of (random) queries, non-codewords are rejected with

probability proportional to their distance from the code.

Locally testable codes are believed to be the combinatorial

core of PCPs. However, the relation is ...
more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Silas Richelson, Sourya Roy

In this work we adapt the notion of non-malleability for codes or Dziembowski, Pietrzak and Wichs (ICS 2010) to locally testable codes. Roughly speaking, a locally testable code is non-malleable if any tampered codeword which passes the local test with good probability is close to a valid codeword which either ... more >>>

Tali Kaufman, Michael Viderman

We study the relation between locally testable and locally decodable codes.

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. Locally decodable codes (LDCs) allow to recover each message entry with ...
more >>>

Dean Doron, Pooya Hatami, William Hoza

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The ``iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>

Michal Koucky

The paper presents a simple construction of polynomial length universal

traversal sequences for cycles. These universal traversal sequences are

log-space (even $NC^1$) constructible and are of length $O(n^{4.03})$. Our

result improves the previously known upper-bound $O(n^{4.76})$ for

log-space constructible universal traversal sequences for cycles.

Martin Grohe

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>>

Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor

We present a computable algorithm that assigns probabilities to every logical statement in a given formal language, and refines those probabilities over time. For instance, if the language is Peano arithmetic, it assigns probabilities to all arithmetical statements, including claims about the twin prime conjecture, the outputs of long-running ... more >>>

Alexander Shen, Nikolay Vereshchagin

We define Kolmogorov complexity of a set of strings as the minimal

Kolmogorov complexity of its element. Consider three logical

operations on sets going back to Kolmogorov

and Kleene:

(A OR B) is the direct sum of A,B,

(A AND B) is the cartesian product of A,B,

more >>>

Andrej Muchnik, Nikolay Vereshchagin

We invistigate what is the minimal length of

a program mapping A to B and at the same time

mapping C to D (where A,B,C,D are binary strings). We prove that

it cannot be expressed

in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C),

..., their ...
more >>>

Till Tantau

This paper introduces logspace optimisation problems as

analogues of the well-studied polynomial-time optimisation

problems. Similarly to them, logspace

optimisation problems can have vastly different approximation

properties, even though the underlying existence and budget problems

have the same computational complexity. Numerous natural problems

are presented that exhibit such a varying ...
more >>>

Jan Kyncl, Tomas Vyskocil

Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G. Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an ... more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

Bodlaender's Theorem states that for every $k$ there is a linear-time algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width-$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula $\phi$ and for

every $k$ there is ...
more >>>

Bernd Borchert, Frank Stephan

Rice's Theorem says that every nontrivial semantic property

of programs is undecidable. It this spirit we show the following:

Every nontrivial absolute (gap, relative) counting property of circuits

is UP-hard with respect to polynomial-time Turing reductions.

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

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

Chris Peikert, Brent Waters

We propose a new general primitive called lossy trapdoor

functions (lossy TDFs), and realize it under a variety of different

number theoretic assumptions, including hardness of the decisional

Diffie-Hellman (DDH) problem and the worst-case hardness of

standard lattice problems.

Using lossy TDFs, we develop a new approach for constructing ... more >>>

Brett Hemenway, Rafail Ostrovsky

In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>

Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky

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

Eli Ben-Sasson, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.

Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).

Kopparty ...
more >>>

Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie

In the setting known as DLOGTIME-uniformity,

the fundamental complexity classes

$AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1$ have several

robust characterizations.

In this paper we refine uniformity further and examine the impact

of these refinements on $NC^1$ and its subclasses.

When applied to the logarithmic circuit depth characterization of $NC^1$,

some refinements leave ...
more >>>

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

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

Alex Samorodnitsky

We define tests of boolean functions which

distinguish between linear (or quadratic) polynomials, and functions

which are very far, in an appropriate sense, from these

polynomials. The tests have optimal or nearly optimal trade-offs

between soundness and the number of queries.

In particular, we show that functions with small ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the

notion of non-random information by computational depth, the

difference between the polynomial-time-bounded Kolmogorov

complexity and traditional Kolmogorov complexity We show how to

find satisfying assignments for formulas that have at least one

assignment of logarithmic depth. The converse holds under a

standard ...
more >>>

Ronen Shaltiel, Chris Umans

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>

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

We construct explicit two-source extractors for $n$ bit sources,

requiring $n^\alpha$ min-entropy and having error $2^{-n^\beta}$,

for some constants $0 < \alpha,\beta < 1$. Previously, constructions

for exponentially small error required either min-entropy

$0.49n$ \cite{Bou05} or three sources \cite{Li15}. The construction

combines somewhere-random condensers based on the Incidence

Theorem \cite{Zuc06,Li11}, ...
more >>>

Shalev Ben-David

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>>

Eli Ben-Sasson, Gal Maor

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

Our proof ... more >>>

Nader Bshouty

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

more >>>Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah

The power symmetric polynomial on $n$ variables of degree $d$ is defined as

$p_d(x_1,\ldots, x_n) = x_{1}^{d}+\dots + x_{n}^{d}$. We study polynomials that are expressible as a sum of powers

of homogenous linear projections of power symmetric polynomials. These form a subclass of polynomials computed by

...
more >>>

Ruiwen Chen, Valentine Kabanets

A family of Boolean circuits $\{C_n\}_{n\geq 0}$ is called \emph{$\gamma(n)$-weakly uniform} if

there is a polynomial-time algorithm for deciding the direct-connection language of every $C_n$,

given \emph{advice} of size $\gamma(n)$. This is a relaxation of the usual notion of uniformity, which allows one

to interpolate between complete uniformity (when $\gamma(n)=0$) ...
more >>>

Vitaly Feldman, Homin Lee, Rocco Servedio

Much work has been done on learning various classes of ``simple'' monotone functions under the uniform distribution. In this paper we give the first unconditional lower bounds for learning problems of this sort by showing that polynomial-time algorithms cannot learn constant-depth monotone Boolean formulas under the uniform distribution in the ... more >>>

Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan

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

Ran Raz, Amir Yehudayoff

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth $d$ ... more >>>

Vince Grolmusz, Gábor Tardos

Modular gates are known to be immune for the random

restriction techniques of Ajtai; Furst, Saxe, Sipser; and Yao and

Hastad. We demonstrate here a random clustering technique which

overcomes this difficulty and is capable to prove generalizations of

several known modular circuit lower bounds of Barrington, Straubing,

Therien; Krause ...
more >>>

Anna Gal, Robert Robere

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and ... more >>>

Arnab Bhattacharyya, Sivakanth Gopi

A locally correctable code (LCC) is an error correcting code that allows correction of any arbitrary coordinate of a corrupted codeword by querying only a few coordinates.

We show that any zero-error $2$-query locally correctable code $\mathcal{C}: \{0,1\}^k \to \Sigma^n$ that can correct a constant fraction of corrupted symbols must ...
more >>>

Nathanael Fijalkow

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,

represented by a machine which scans the input exactly once from left to right.

In this paper, we study alternating machines as introduced by ...
more >>>

Jop Briet, Zeev Dvir, Guangda Hu, Shubhangi Saraf

We study an approximate version of $q$-query LDCs (Locally Decodable Codes) over the real numbers and prove lower bounds on the encoding length of such codes. A $q$-query $(\alpha,\delta)$-approximate LDC is a set $V$ of $n$ points in $\mathbb{R}^d$ so that, for each $i \in [d]$ there are $\Omega(\delta n)$ ... more >>>

Makrand Sinha

We prove that any extended formulation that approximates the matching polytope on $n$-vertex graphs up to a factor of $(1+\varepsilon)$ for any $\frac2n \le \varepsilon \le 1$ must have at least ${n}\choose{{\alpha}/{\varepsilon}}$ defining inequalities where $0<\alpha<1$ is an absolute constant. This is tight as exhibited by the $(1+\varepsilon)$ approximating linear ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann, Olivier Serre

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

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

Dmitriy Cherukhin

We consider bounded depth circuits over an arbitrary field $K$. If the field $K$ is finite, then we allow arbitrary gates $K^n\to K$. For instance, in the case of field $GF(2)$ we allow any Boolean gates. If the field $K$ is infinite, then we allow only polinomials.

For every fixed ... more >>>

Eli Ben-Sasson, Prahladh Harsha

We present a simple proof of the bounded-depth Frege lower bounds of

Pitassi et. al. and Krajicek et. al. for the pigeonhole

principle. Our method uses the interpretation of proofs as two player

games given by Pudlak and Buss. Our lower bound is conceptually

simpler than previous ones, and relies ...
more >>>

Stasys Jukna, Andrzej Lingas

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

Kristoffer Arnsfelt Hansen

We prove that any AC0 circuit augmented with {epsilon log^2 n}

MOD_m gates and with a MAJORITY gate at the output, require size

n^{Omega(log n)} to compute MOD_l, when l has a prime

factor not dividing m and epsilon is sufficiently small. We

also obtain ...
more >>>

Frederic Green

We say an integer polynomial $p$, on Boolean inputs, weakly

$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod

$m$), whenever $f$ is zero. In this paper we prove that if a polynomial

weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$

more >>>

Mika Göös

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

Arnab Bhattacharyya, Sivakanth Gopi

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

Emanuele Viola

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

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

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

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

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

Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth $4$ arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, IMM$_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d \leq n^{1/10}$. This improves the result of Nisan and Wigderson (Computational ... more >>>

Mrinal Kumar, Shubhangi Saraf

We study the class of homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuits, which are depth 4 homogenous circuits with top fanin bounded by $r$. We show that any homogenous $\Sigma\Pi\Sigma\Pi(r)$ circuit computing the permanent of an $n\times n$ matrix must have size at least $\exp\left(n^{\Omega(1/r)}\right)$.

In a recent result, Gupta, Kamath, Kayal and ... more >>>

Neeraj Kayal, Chandan Saha

Shpilka and Wigderson (CCC 1999) had posed the problem of proving exponential lower bounds for (nonhomogeneous) depth three arithmetic circuits with bounded bottom fanin over a field $\mathbb{F}$ of characteristic zero. We resolve this problem by proving a $N^{\Omega(\frac{d}{\tau})}$ lower bound for (nonhomogeneous) depth three arithmetic circuits with bottom fanin ... more >>>

Noa Eidelstein, Alex Samorodnitsky

A design is a finite set of points in a space on which every "simple" functions averages to its global mean. Illustrative examples of simple functions are low-degree polynomials on the Euclidean sphere or on the Hamming cube.

We prove lower bounds on designs in spaces with a large group ... more >>>

Giuseppe Persiano, Kevin Yeo

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

Albert Atserias, Moritz Müller, Sergi Oliva

The relativized weak pigeonhole principle states that if at least $2n$ out of $n^2$ pigeons fly into $n$ holes, then some hole must be doubly occupied. We prove that every DNF-refutation of the CNF encoding of this principle requires size $2^{(\log n)^{3/2-\epsilon}}$ for every $\epsilon > 0$ and every sufficiently ... more >>>

Arkadev Chattopadhyay, Pavel Dvo?ák, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. and later studied by Beimel et al. for its connection to the famous direct sum question. In this problem, let $f:\{0,1\}^n \to \{0,1\}$ be any boolean function. Alice and Bob get $k$ inputs ... more >>>

Yijia Chen, Jörg Flum, Moritz Müller

Among others, refining the methods of [Fortnow and Santhanam, ECCC Report TR07-096] we improve a result of this paper and show for any parameterized problem with a ``linear weak OR'' and with NP-hard underlying classical problem that there is no polynomial reduction from the problem to itself that assigns to ... more >>>

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.

We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This ...
more >>>

Oded Goldreich, Howard Karloff, Leonard Schulman, Luca Trevisan

We prove that if a linear error correcting code

$\C:\{0,1\}^n\to\{0,1\}^m$ is such that a bit of the message can

be probabilistically reconstructed by looking at two entries of a

corrupted codeword, then $m = 2^{\Omega(n)}$. We also present

several extensions of this result.

We show a reduction from the ... more >>>

Detlef Sieling

Linear Transformed Ordered Binary Decision Diagrams (LTOBDDs) have

been suggested as a generalization of OBDDs for the representation and

manipulation of Boolean functions. Instead of variables as in the

case of OBDDs parities of variables may be tested at the nodes of an

LTOBDD. By this extension it is ...
more >>>

Scott Aaronson

The problem of finding a local minimum of a black-box function is central

for understanding local search as well as quantum adiabatic algorithms.

For functions on the Boolean hypercube {0,1}^n, we show a lower bound of

Omega(2^{n/4}/n) on the number of queries needed by a quantum computer to

solve this ...
more >>>

Paul Beame, Nathan Segerlind

We prove that an \omega(log^3 n) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an n^\omega(1) size lower bound for tree-like Lovasz-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an n^\Omega(1) lower bound for the (k+1)-party NOF communication complexity of set-disjointness ... more >>>

Mrinal Kumar, Ben Lee Volk

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of ... more >>>

Amir Shpilka

We prove lower bounds on the number of product gates in bilinear

and quadratic circuits that

compute the product of two $n \times n$ matrices over finite fields.

In particular we obtain the following results:

1. We show that the number of product gates in any bilinear

(or quadratic) ...
more >>>

Ran Raz, Amir Shpilka

We prove super-linear lower bounds for the number of edges

in constant depth circuits with $n$ inputs and up to $n$ outputs.

Our lower bounds are proved for all types of constant depth

circuits, e.g., constant depth arithmetic circuits, constant depth

threshold circuits ...
more >>>

Stasys Jukna

A {+,x}-circuit counts a given multivariate polynomial f, if its values on 0-1 inputs are the same as those of f; on other inputs the circuit may output arbitrary values. Such a circuit counts the number of monomials of evaluated to 1 by a given 0-1 input vector (with multiplicities ... more >>>

Jan Johannsen

Using a notion of real communication complexity recently

introduced by J. Krajicek, we prove a lower bound on the depth of

monotone real circuits and the size of monotone real formulas for

st-connectivity. This implies a super-polynomial speed-up of dag-like

over tree-like Cutting Planes proofs.

Amos Beimel, Anna Gal, Michael S. Paterson

The model of span programs is a linear algebraic model of

computation. Lower bounds for span programs imply lower bounds for

contact schemes, symmetric branching programs and for formula size.

Monotone span programs correspond also to linear secret-sharing schemes.

We present a new technique for proving lower bounds for ...
more >>>

Amit Chakrabarti

We consider the $k$-layer pointer jumping problem in the one-way

multi-party number-on-the-forehead communication model. In this problem,

the input is a layered directed graph with each vertex having outdegree

$1$, shared amongst $k$ players: Player~$i$ knows all layers {\em

except} the $i$th. The players must communicate, in the order

$1,2,\ldots,k$, ...
more >>>

Dmitry Itsykson, Dmitry Sokolov

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are ... more >>>

Boaz Barak, Yehuda Lindell, Salil Vadhan

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:

<ol>

<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ...
more >>>

Lars Engebretsen

We show that the k-CSP problem over a finite Abelian group G

cannot be approximated within |G|^{k-O(sqrt{k})}-epsilon, for

any constant epsilon>0, unless P=NP. This lower bound matches

well with the best known upper bound, |G|^{k-1}, of Serna,

Trevisan and Xhafa. The proof uses a combination of PCP

techniques---most notably a ...
more >>>

Nutan Limaye, Guillaume Malod, Srikanth Srinivasan

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

N. S. Narayanaswamy, C.E. Veni Madhavan

We present a new boolean function for which any Ordered Binary

Decision Diagram (OBDD) computing it has an exponential number

of nodes. This boolean function is obtained from Nisan's

pseudorandom generator to derandomize space bounded randomized

algorithms. Though the relation between hardness and randomness for

computational models is well ...
more >>>

Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo

We prove an $\Omega(d \lg n/ (\lg\lg n)^2)$ lower bound on the dynamic cell-probe complexity of statistically $\mathit{oblivious}$ approximate-near-neighbor search (ANN) over the $d$-dimensional Hamming cube. For the natural setting of $d = \Theta(\log n)$, our result implies an $\tilde{\Omega}(\lg^2 n)$ lower bound, which is a quadratic improvement over the ... more >>>

Miklos Ajtai

For each natural number $d$ we consider a finite structure ${\bf M}_{d}$ whose universe is the set of all $0,1$-sequence of length $n=2^{d}$, each representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace$ in binary form. The operations included in the structure are the four constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>

Neeraj Kayal, Chandan Saha

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

more >>>

Andrej Bogdanov, Luca Trevisan

We consider the problem of testing bipartiteness in the adjacency

matrix model. The best known algorithm, due to Alon and Krivelevich,

distinguishes between bipartite graphs and graphs that are

$\epsilon$-far from bipartite using $O((1/\epsilon^2)polylog(1/epsilon)$

queries. We show that this is optimal for non-adaptive algorithms,

up to the ...
more >>>

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

We introduce strong, and in many cases optimal, lower bounds for the number of queries required to nonadaptively test three fundamental properties of functions $ f : [n]^d \rightarrow \mathbb R$ on the hypergrid: monotonicity, convexity, and the Lipschitz property.

Our lower bounds also apply to the more restricted setting ...
more >>>

Arnab Bhattacharyya, Ning Xie

Let $f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$ be three Boolean functions.

We say a triple $(x,y,x+y)$ is a \emph{triangle} in the function-triple $(f_{1}, f_{2}, f_{3})$ if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$.

$(f_{1}, f_{2}, f_{3})$ is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function-triple

and ...
more >>>

Justin Thaler

We describe a new hardness amplification result for point-wise approximation of Boolean functions by low-degree polynomials. Specifically, for any function $f$ on $N$ bits, define $F(x_1, \dots, x_M) = \text{OMB}(f(x_1), \dots, f(x_M))$ to be the function on $M \cdot N$ bits obtained by block-composing $f$ with a specific DNF known ... more >>>

Hong Van Le

In this paper

we associate to each multivariate polynomial $f$ that is homogeneous relative to a subset of its variables a series of polynomial families $P_\lambda (f)$ of $m$-tuples of homogeneous polynomials of equal degree such that the circuit size of any member in $P_\lambda (f)$ is bounded from above ...
more >>>

We investigate the computational power of a formal model for networks of

spiking neurons. It is shown that simple operations on phase-differences

between spike-trains provide a very powerful computational tool that can

in principle be used to carry out highly complex computations on a small

network of spiking neurons. We ...
more >>>

Christoph Meinel, Stephan Waack

We investigate the probabilistic communication complexity

(more exactly, the majority communication complexity,)

of the graph accessibility problem GAP and

its counting versions MOD_k-GAP, k > 1.

Due to arguments concerning matrix variation ranks

and certain projection reductions, we prove

that, for any partition of the input variables,

more >>>

Russell Impagliazzo, Pavel Pudlak, Jiri Sgall

Razborov~\cite{Razborov96} recently proved that polynomial

calculus proofs of the pigeonhole principle $PHP_n^m$ must have

degree at least $\ceiling{n/2}+1$ over any field. We present a

simplified proof of the same result. The main

idea of our proof is the same as in the original proof

of Razborov: we want to describe ...
more >>>

Matthias Homeister

We prove the first lower bound for restricted read-once parity branching

programs with unlimited parity nondeterminism where for each input the

variables may be tested according to several orderings.

Proving a superpolynomial lower bound for read-once parity branching

programs is still a challenging open problem. The following variant ...
more >>>

Amit Levi, Erik Waingarten

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

Stasys Jukna

Tropical circuits are circuits with Min and Plus, or Max and Plus operations as gates. Their importance stems from their intimate relation to dynamic programming algorithms. The power of tropical circuits lies somewhere between that of monotone boolean circuits and monotone arithmetic circuits. In this paper we present some lower ... more >>>

Eli Ben-Sasson, Jan Johannsen

It has been observed empirically that clause learning does not significantly improve the performance of a SAT solver when restricted

to learning clauses of small width only. This experience is supported by lower bound theorems. It is shown that lower bounds on the runtime of width-restricted clause learning follow from ...
more >>>

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets $S_1,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>>

Roei Tell

We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about $S$ is estimates of the density of $S$ in adaptively chosen subsets of ... more >>>

Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition ... more >>>

Arkadev Chattopadhyay, Rahul Santhanam

We formulate a new connection between instance compressibility \cite{Harnik-Naor10}), where the compressor uses circuits from a class $\C$, and correlation with

circuits in $\C$. We use this connection to prove the first lower bounds

on general probabilistic multi-round instance compression. We show that there

is no

probabilistic multi-round ...
more >>>

Michael Schmitt

We calculate lower bounds on the size of sigmoidal neural networks

that approximate continuous functions. In particular, we show that

for the approximation of polynomials the network size has to grow

as $\Omega((\log k)^{1/4})$ where $k$ is the degree of the polynomials.

This bound is ...
more >>>

Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis

Alice and Bob want to know if two strings of length $n$ are

almost equal. That is, do they differ on at most $a$ bits?

Let $0\le a\le n-1$.

We show that any deterministic protocol, as well as any

error-free quantum protocol ($C^*$ version), for this problem

requires at ...
more >>>

Rosario Gennaro, Luca Trevisan

We present lower bounds on the efficiency of

constructions for Pseudo-Random Generators (PRGs) and

Universal One-Way Hash Functions (UOWHFs) based on

black-box access to one-way permutations. Our lower bounds are tight as

they match the efficiency of known constructions.

A PRG (resp. UOWHF) construction based on black-box access is

a ...
more >>>

Sergei Artemenko, Ronen Shaltiel

Hardness amplification results show that for every function $f$ there exists a function $Amp(f)$ such that the following holds: if every circuit of size $s$ computes $f$ correctly on at most a $1-\delta$ fraction of inputs, then every circuit of size $s'$ computes $Amp(f)$ correctly on at most a $1/2+\eps$ ... more >>>

Nikos Leonardos, Michael Saks

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.

A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>>

Anirbit Mukherjee, Amitabh Basu

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function $x \mapsto \max\{0,x\}$. We try to understand the role of depth in such neural networks by showing size lowerbounds against ... more >>>

Valentin E. Brimkov, Stefan S. Dantchev

In this paper we study the Boolean Knapsack problem (KP$_{{\bf R}}$)

$a^Tx=1$, $x \in \{0,1\}^n$ with real coefficients, in the framework

of the Blum-Shub-Smale real number computational model \cite{BSS}.

We obtain a new lower bound

$\Omega \left( n\log n\right) \cdot f(1/a_{\min})$ for the time

complexity ...
more >>>

Olaf Beyersdorff, Ilario Bonacina, Leroy Chew

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