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

**T**

__
TR14-032
| 8th March 2014
__

Olaf Beyersdorff, Leroy Chew#### Tableau vs. Sequent Calculi for Minimal Entailment

__
TR00-033
| 22nd May 2000
__

Jan Krajicek#### Tautologies from pseudo-random generators

Revisions: 1

__
TR15-025
| 22nd February 2015
__

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

__
TR09-007
| 9th January 2009
__

Eli Ben-Sasson, Michael Viderman#### Tensor Products of Weakly Smooth Codes are Robust

__
TR12-004
| 10th January 2012
__

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima#### Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication

Revisions: 3

__
TR18-086
| 23rd April 2018
__

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

Revisions: 1

__
TR11-010
| 1st February 2011
__

Boris Alexeev, Michael Forbes, Jacob Tsimerman#### Tensor Rank: Some Lower and Upper Bounds

__
TR10-002
| 4th January 2010
__

Ran Raz#### Tensor-Rank and Lower Bounds for Arithmetic Formulas

__
TR12-011
| 7th February 2012
__

Nader Bshouty#### Testers and their Applications

__
TR11-057
| 15th April 2011
__

Madhav Jha, Sofya Raskhodnikova#### Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy

Revisions: 2

__
TR97-010
| 2nd April 1997
__

Marcos Kiwi#### Testing and Weight Distributions of Dual Codes

__
TR12-103
| 16th August 2012
__

Arnab Bhattacharyya, Yuichi Yoshida#### Testing Assignments of Boolean CSPs

__
TR12-031
| 4th April 2012
__

Tom Gur, Omer Tamuz#### Testing Booleanity and the Uncertainty Principle

Revisions: 1

__
TR11-041
| 24th March 2011
__

Dana Ron, Gilad Tsur#### Testing Computability by Width-Two OBDDs

__
TR11-101
| 26th July 2011
__

Angsheng Li, Yicheng Pan, Pan Peng#### Testing Conductance in General Graphs

__
TR06-053
| 6th April 2006
__

Eldar Fischer, Orly Yahalom#### Testing Convexity Properties of Tree Colorings

__
TR20-062
| 29th April 2020
__

Clement Canonne, Karl Wimmer#### Testing Data Binnings

__
TR21-133
| 12th September 2021
__

Oded Goldreich, Dana Ron#### Testing Distributions of Huge Objects

Revisions: 1

__
TR16-086
| 29th May 2016
__

Noga Alon, Klim Efremenko, Benny Sudakov#### Testing Equality in Communication Graphs

Revisions: 1

__
TR14-003
| 10th January 2014
__

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka#### Testing Equivalence of Polynomials under Shifts

Revisions: 2
,
Comments: 1

__
TR07-076
| 25th July 2007
__

Satyen Kale, C. Seshadhri#### Testing Expansion in Bounded Degree Graphs

Revisions: 1

__
TR07-077
| 7th August 2007
__

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan#### Testing for Concise Representations

__
TR19-083
| 4th June 2019
__

Lior Gishboliner, Asaf Shapira#### Testing Graphs against an Unknown Distribution

Revisions: 2

__
TR00-083
| 18th September 2000
__

Eldar Fischer#### Testing graphs for colorability properties

Revisions: 1

__
TR18-171
| 10th October 2018
__

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

Revisions: 1

__
TR07-128
| 10th November 2007
__

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio#### Testing Halfspaces

__
TR07-083
| 23rd August 2007
__

Artur Czumaj, Asaf Shapira, Christian Sohler#### Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs

__
TR17-058
| 7th April 2017
__

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

Revisions: 1

__
TR17-006
| 15th December 2016
__

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

Revisions: 2

__
TR19-102
| 10th August 2019
__

Oded Goldreich#### Testing Isomorphism in the Bounded-Degree Graph Model

Revisions: 1

__
TR16-136
| 31st August 2016
__

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer#### Testing k-Monotonicity

Revisions: 1

__
TR20-107
| 19th July 2020
__

Lior Gishboliner, Asaf Shapira, Henrique Stagni#### Testing linear inequalities of subgraph statistics

__
TR11-005
| 20th January 2011
__

Madhu Sudan#### Testing Linear Properties: Some general themes

Revisions: 1

__
TR08-088
| 13th September 2008
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing Linear-Invariant Non-Linear Properties

Revisions: 1

__
TR10-116
| 21st July 2010
__

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie#### Testing linear-invariant non-linear properties: A short report

__
TR18-067
| 9th April 2018
__

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

Revisions: 1

__
TR12-076
| 12th June 2012
__

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova#### Testing Lipschitz Functions on Hypergrid Domains

__
TR18-196
| 19th November 2018
__

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

__
TR12-001
| 1st January 2012
__

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett#### Testing Low Complexity Affine-Invariant Properties

__
TR10-027
| 28th February 2010
__

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant#### Testing monotonicity of distributions over general partial orders

__
TR19-124
| 28th August 2019
__

Roy Gotlib, Tali Kaufman#### Testing Odd Direct Sums Using High Dimensional Expanders

__
TR11-075
| 6th May 2011
__

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira#### Testing Odd-Cycle-Freeness in Boolean Functions

__
TR10-065
| 13th April 2010
__

Tali Kaufman, Shachar Lovett#### Testing of exponentially large codes, by a new extension to Weil bound for character sums

Revisions: 1

__
TR05-153
| 9th December 2005
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Orientation Properties

__
TR04-092
| 3rd November 2004
__

Oded Lachish, Ilan Newman#### Testing Periodicity

__
TR12-094
| 19th July 2012
__

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva#### Testing Permanent Oracles -- Revisited

__
TR14-021
| 18th February 2014
__

Clement Canonne, Ronitt Rubinfeld#### Testing probability distributions underlying aggregated data

__
TR12-155
| 15th November 2012
__

Clement Canonne, Dana Ron, Rocco Servedio#### Testing probability distributions using conditional samples

Revisions: 1

__
TR10-157
| 24th October 2010
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Properties of Collections of Distributions

Revisions: 1

__
TR07-054
| 25th May 2007
__

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur#### Testing Properties of Constraint-Graphs

__
TR12-055
| 4th May 2012
__

Reut Levi, Dana Ron, Ronitt Rubinfeld#### Testing Similar Means

__
TR07-135
| 26th December 2007
__

Paul Valiant, Paul Valiant#### Testing Symmetric Properties of Distributions

__
TR07-118
| 27th November 2007
__

Asaf Nachmias, Asaf Shapira#### Testing the Expansion of a Graph

__
TR03-076
| 8th September 2003
__

Michael Langberg#### Testing the independence number of hypergraphs

__
TR21-164
| 19th November 2021
__

Scott Aaronson, DeVon Ingram, William Kretschmer#### The Acrobatics of BQP

__
TR11-076
| 7th May 2011
__

Eric Miles, Emanuele Viola#### The Advanced Encryption Standard, Candidate Pseudorandom Functions, and Natural Proofs

Revisions: 1

__
TR13-040
| 11th March 2013
__

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie#### The Algebraic Theory of Parikh Automata

Revisions: 2

__
TR99-043
| 5th November 1999
__

Venkatesan Guruswami#### The Approximability of Set Splitting Problems and Satisfiability Problems with no Mixed Clauses

__
TR12-169
| 22nd November 2012
__

Noga Alon, Santosh Vempala#### The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

__
TR04-079
| 30th August 2004
__

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn#### The Arithmetical Complexity of Dimension and Randomness

__
TR15-143
| 31st August 2015
__

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

__
TR16-181
| 15th November 2016
__

Avishay Tal#### The Bipartite Formula Complexity of Inner-Product is Quadratic

__
TR07-125
| 11th October 2007
__

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka#### The black-box query complexity of polynomial summation

__
TR96-032
| 12th March 1996
__

Manindra Agrawal, Thomas Thierauf#### The Boolean Isomorphism Problem

__
TR20-115
| 1st August 2020
__

Scott Aaronson#### The Busy Beaver Frontier

__
TR16-096
| 14th June 2016
__

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay#### The Chasm at Depth Four, and Tensor Rank : Old results, new insights

Revisions: 2

__
TR17-148
| 6th October 2017
__

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

Revisions: 3

__
TR15-066
| 20th April 2015
__

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

__
TR17-090
| 15th May 2017
__

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

__
TR18-157
| 10th September 2018
__

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

Revisions: 2

__
TR20-139
| 11th September 2020
__

Mark Braverman, Sumegha Garg, David Woodruff#### The Coin Problem with Applications to Data Streams

__
TR11-152
| 12th November 2011
__

Emanuele Viola#### The communication complexity of addition

__
TR06-151
| 10th December 2006
__

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan#### The communication complexity of correlation

__
TR01-019
| 2nd March 2001
__

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet#### The Communication Complexity of Enumeration, Elimination, and Selection

__
TR11-063
| 19th April 2011
__

Alexander A. Sherstov#### The Communication Complexity of Gap Hamming Distance

__
TR15-044
| 2nd April 2015
__

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

Revisions: 1

__
TR15-002
| 2nd January 2015
__

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

__
TR18-033
| 16th February 2018
__

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

Revisions: 2

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR19-053
| 5th April 2019
__

Andrei Krokhin, Jakub Opršal#### The complexity of 3-colouring $H$-colourable graphs

__
TR04-061
| 30th June 2004
__

Scott Aaronson#### The Complexity of Agreement

__
TR21-157
| 2nd November 2021
__

Monika Henzinger, Andrea Lincoln, Barna Saha#### The Complexity of Average-Case Dynamic Subgraph Counting

__
TR05-115
| 27th September 2005
__

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou#### The complexity of computing a Nash equilibrium

__
TR98-022
| 14th April 1998
__

Steffen Reith, Heribert Vollmer#### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

__
TR01-061
| 13th July 2001
__

Mitsunori Ogihara, Seinosuke Toda#### The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs

Revisions: 2

__
TR01-077
| 24th September 2001
__

Andrei Krokhin, Peter Jeavons, Peter Jonsson#### The complexity of constraints on intervals and lengths

__
TR04-020
| 8th March 2004
__

Emanuele Viola#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

__
TR14-016
| 16th January 2014
__

Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz#### The Complexity of Debate Checking

__
TR07-045
| 24th April 2007
__

Heribert Vollmer#### The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

__
TR13-124
| 9th September 2013
__

Thomas Watson#### The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

__
TR06-049
| 9th April 2006
__

Guy Wolfovitz#### The Complexity of Depth-3 Circuits Computing Symmetric Boolean Functions

__
TR14-099
| 7th August 2014
__

Gil Cohen, Igor Shinkar#### The Complexity of DNF of Parities

__
TR12-070
| 26th May 2012
__

Thomas Watson#### The Complexity of Estimating Min-Entropy

Revisions: 1

__
TR10-111
| 14th July 2010
__

Venkatesan Guruswami, Ali Kemal Sinop#### The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number

__
TR19-040
| 19th February 2019
__

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis#### The Complexity of Finding {$S$}-factors in Regular Graphs

__
TR06-149
| 7th December 2006
__

Lance Fortnow, Rakesh Vohra#### The Complexity of Forecast Testing

__
TR06-153
| 19th October 2006
__

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer#### The Complexity of Generalized Satisfiability for Linear Temporal Logic

Revisions: 1

__
TR14-070
| 14th May 2014
__

Vikraman Arvind, Gaurav Rattan#### The Complexity of Geometric Graph Isomorphism

__
TR12-090
| 2nd July 2012
__

Michael Blondin, Andreas Krebs, Pierre McKenzie#### The Complexity of Intersecting Finite Automata Having Few Final States

__
TR08-053
| 27th March 2008
__

Stephen A. Fenner, William Gasarch, Brian Postow#### The complexity of learning SUBSEQ(A)

__
TR08-034
| 19th January 2008
__

Dan Gutfreund, Guy Rothblum#### The Complexity of Local List Decoding

Revisions: 1

__
TR96-024
| 21st March 1996
__

Eric Allender, Robert Beals, Mitsunori Ogihara#### The complexity of matrix rank and feasible systems of linear equations

__
TR95-040
| 26th July 1995
__

Uri Zwick, Michael S. Paterson#### The complexity of mean payoff games on graphs

__
TR00-082
| 17th August 2000
__

Lefteris Kirousis, Phokion G. Kolaitis#### The Complexity of Minimal Satisfiability Problems

Revisions: 2

__
TR99-001
| 4th January 1999
__

Detlef Sieling#### The Complexity of Minimizing FBDDs

Revisions: 1

__
TR18-120
| 21st June 2018
__

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

__
TR06-034
| 9th March 2006
__

Moni Naor, Guy Rothblum#### The Complexity of Online Memory Checking

__
TR07-023
| 26th February 2007
__

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor#### The Complexity of Problems for Quantified Constraints

__
TR13-038
| 13th March 2013
__

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen#### The complexity of proving that a graph is Ramsey

Revisions: 1

__
TR17-065
| 20th April 2017
__

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

__
TR16-109
| 18th July 2016
__

Scott Aaronson#### The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

__
TR08-021
| 3rd March 2008
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Matchings

__
TR09-145
| 20th December 2009
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Network Formation

__
TR04-100
| 23rd November 2004
__

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer#### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

__
TR11-053
| 11th April 2011
__

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek#### The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions

__
TR12-151
| 6th November 2012
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### The Complexity of Somewhat Approximation Resistant Predicates

Revisions: 1

__
TR00-036
| 29th May 2000
__

Carsten Damm, Markus Holzer, Pierre McKenzie#### The Complexity of Tensor Calculus

__
TR21-122
| 24th August 2021
__

Sabyasachi Basu, Akash Kumar, C. Seshadhri#### The complexity of testing all properties of planar graphs, and the role of isomorphism

__
TR10-114
| 17th July 2010
__

Zhixiang Chen, Bin Fu#### The Complexity of Testing Monomials in Multivariate Polynomials

__
TR07-093
| 27th July 2007
__

Andrei A. Bulatov#### The complexity of the counting constraint satisfaction problem

Revisions: 1

__
TR08-011
| 21st November 2007
__

Kazuo Iwama, Suguru Tamaki#### The Complexity of the Hajos Calculus for Planar Graphs

__
TR01-028
| 16th March 2001
__

Thanh Minh Hoang, Thomas Thierauf#### The Complexity of the Minimal Polynomial

__
TR13-016
| 17th January 2013
__

Olaf Beyersdorff#### The Complexity of Theorem Proving in Autoepistemic Logic

Revisions: 1

__
TR14-014
| 28th January 2014
__

Olaf Beyersdorff, Leroy Chew#### The Complexity of Theorem Proving in Circumscription and Minimal Entailment

__
TR14-028
| 27th February 2014
__

Vikraman Arvind, S Raja#### The Complexity of Two Register and Skew Arithmetic Computation

__
TR06-069
| 11th May 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner#### The Complexity of Unions of Disjoint Sets

__
TR14-083
| 19th June 2014
__

Irit Dinur, Shafi Goldwasser, Huijia Lin#### The Computational Benefit of Correlated Instances

__
TR04-055
| 27th May 2004
__

Kousha Etessami, Andreas Lochbihler#### The computational complexity of Evolutionarily Stable Strategies

__
TR10-170
| 11th November 2010
__

Scott Aaronson, Alex Arkhipov#### The Computational Complexity of Linear Optics

__
TR05-052
| 5th May 2005
__

Grant Schoenebeck, Salil Vadhan#### The Computational Complexity of Nash Equilibria in Concisely Represented Games

__
TR97-009
| 12th March 1997
__

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit#### The Computational Complexity of Some Problems of Linear Algebra

__
TR14-013
| 30th January 2014
__

Mark Braverman, Kanika Pasricha#### The computational hardness of pricing compound options

__
TR96-025
| 22nd March 1996
__

Berthold Ruf#### The Computational Power of Spiking Neurons Depends on the Shape of the Postsynaptic Potentials

__
TR01-005
| 27th October 2000
__

Pascal Tesson, Denis Thérien#### The Computing Power of Programs over Finite Monoids

__
TR06-094
| 29th July 2006
__

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou#### The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Revisions: 1

__
TR04-022
| 31st March 2004
__

Nayantara Bhatnagar, Parikshit Gopalan#### The Degree of Threshold Mod 6 and Diophantine Equations

__
TR09-030
| 5th April 2009
__

Shachar Lovett#### The density of weights of Generalized Reed-Muller codes

__
TR14-124
| 7th October 2014
__

Periklis Papakonstantinou#### The Depth Irreducibility Hypothesis

__
TR98-059
| 15th September 1998
__

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer#### The Descriptive Complexity Approach to LOGCFL

__
TR06-035
| 19th January 2006
__

Till Tantau#### The Descriptive Complexity of the Reachability Problem As a Function of Different Graph Parameters

__
TR12-087
| 4th July 2012
__

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

__
TR18-177
| 1st October 2018
__

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

__
TR17-128
| 15th August 2017
__

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

Revisions: 3
,
Comments: 1

__
TR05-148
| 6th December 2005
__

Eric Allender, Samir Datta, Sambuddha Roy#### The Directed Planar Reachability Problem

Revisions: 1

__
TR11-146
| 1st November 2011
__

Bireswar Das, Manjish Pal, Vijay Visavaliya#### The Entropy Influence Conjecture Revisited

__
TR10-128
| 15th August 2010
__

Scott Aaronson#### The Equivalence of Sampling and Searching

Revisions: 1

__
TR19-076
| 24th May 2019
__

Leroy Chew, Judith Clymo#### The Equivalences of Refutational QRAT

__
TR21-125
| 23rd August 2021
__

Zhiyuan Fan, Jiatu Li, Tianqi Yang#### The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

__
TR05-049
| 1st April 2005
__

Joan Boyar, rene peralta#### The Exact Multiplicative Complexity of the Hamming Weight Function

__
TR21-085
| 21st June 2021
__

Ilya Volkovich#### The Final Nail in the Coffin of Statistically-Secure Obfuscator.

__
TR19-009
| 16th January 2019
__

Jiawei Gao, Russell Impagliazzo#### The Fine-Grained Complexity of Strengthenings of First-Order Logic

Revisions: 1

__
TR13-162
| 1st October 2013
__

Janka Chlebíková, Morgan Chopin#### The Firefighter Problem: A Structural Analysis

Revisions: 1

__
TR07-097
| 8th October 2007
__

Miklos Ajtai, Cynthia Dwork#### The First and Fourth Public-Key Cryptosystems with Worst-Case/Average-Case Equivalence.

__
TR16-025
| 26th February 2016
__

Shachar Lovett#### The Fourier structure of low degree polynomials

Revisions: 1

__
TR12-180
| 21st December 2012
__

Chaim Even-Zohar, Shachar Lovett#### The Freiman-Ruzsa Theorem in Finite Fields

__
TR13-161
| 23rd October 2013
__

Jack H. Lutz#### The Frequent Paucity of Trivial Strings

Revisions: 1

__
TR18-182
| 31st October 2018
__

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

Revisions: 1

__
TR02-047
| 3rd August 2002
__

Oded Goldreich#### The GGM Construction does NOT yield Correlation Intractable Function Ensembles.

__
TR99-034
| 30th August 1999
__

Wolfgang Merkle#### The global power of additional queries to p-random oracles.

__
TR96-054
| 2nd November 1996
__

Oded Goldreich#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

Comments: 1

__
TR98-006
| 27th January 1998
__

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano#### The Graph Clustering Problem has a Perfect Zero-Knowledge Proof

__
TR19-016
| 5th February 2019
__

Alexander A. Sherstov#### The hardest halfspace

__
TR18-193
| 14th November 2018
__

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

__
TR16-020
| 8th February 2016
__

Zachary Remscrim#### The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling

__
TR07-095
| 13th July 2007
__

Vikraman Arvind, Partha Mukhopadhyay#### The Ideal Membership Problem and Polynomial Identity Testing

Revisions: 2

__
TR01-104
| 17th December 2001
__

Irit Dinur, Shmuel Safra#### The Importance of Being Biased

__
TR94-014
| 12th December 1994
__

Miklos Ajtai#### The Independence of the modulo p Counting Principles

__
TR11-033
| 8th March 2011
__

Rahul Jain, Shengyu Zhang#### The influence lower bound via query elimination

__
TR07-018
| 1st March 2007
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### The Informational Content of Canonical Disjoint NP-Pairs

__
TR09-098
| 9th October 2009
__

Alexander A. Sherstov#### The intersection of two halfspaces has high threshold degree

Revisions: 1

__
TR12-181
| 20th December 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### The Inverse Shapley Value Problem

__
TR09-053
| 20th May 2009
__

Johannes Köbler, Sebastian Kuhnert#### The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

__
TR07-068
| 24th July 2007
__

Thomas Thierauf, Fabian Wagner#### The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace

__
TR96-040
| 21st May 1996
__

Thomas Thierauf#### The Isomorphismproblem for One-Time-Only Branching Programs

Revisions: 1
,
Comments: 1

__
TR16-199
| 15th December 2016
__

Pavel Hubacek, Moni Naor, Eylon Yogev#### The Journey from NP to TFNP Hardness

__
TR06-070
| 23rd May 2006
__

Ludwig Staiger#### The Kolmogorov complexity of infinite words

__
TR21-181
| 30th December 2021
__

Oded Goldreich#### The KW Games as a Teaser

__
TR15-049
| 3rd April 2015
__

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

Revisions: 1

__
TR18-143
| 16th August 2018
__

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

__
TR06-106
| 18th August 2006
__

Scott Aaronson#### The Learnability of Quantum States

__
TR19-182
| 9th December 2019
__

Zachary Remscrim#### The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem

Revisions: 1

__
TR13-153
| 8th November 2013
__

Mrinal Kumar, Shubhangi Saraf#### The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in

__
TR11-106
| 6th August 2011
__

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan#### The Limits of Two-Party Differential Privacy

__
TR96-063
| 6th November 1996
__

Martin Dietzfelbinger#### The Linear-Array Problem in Communication Complexity Resolved

__
TR08-111
| 14th November 2008
__

Shachar Lovett, Tali Kaufman#### The List-Decoding Size of Reed-Muller Codes

Revisions: 2

__
TR18-176
| 26th October 2018
__

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

__
TR03-073
| 11th June 2003
__

Amin Coja-Oghlan#### The Lovasz number of random graph

__
TR17-084
| 2nd May 2017
__

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

Revisions: 1

__
TR17-059
| 6th April 2017
__

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

Revisions: 1

__
TR09-017
| 20th February 2009
__

Joshua Brody#### The Maximum Communication Complexity of Multi-party Pointer Jumping.

__
TR98-071
| 26th November 1998
__

Itsik Pe'er, Ron Shamir#### The median problems for breakpoints are NP-complete

__
TR14-176
| 16th December 2014
__

Eric Allender, Dhiraj Holden, Valentine Kabanets#### The Minimum Oracle Circuit Size Problem

__
TR16-110
| 19th July 2016
__

Alexander Golovnev, Oded Regev, Omri Weinstein#### The Minrank of Random Graphs

Revisions: 1

__
TR95-059
| 21st November 1995
__

Nader Bshouty#### The Monotone Theory for the PAC-Model

__
TR16-127
| 12th August 2016
__

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

__
TR11-145
| 2nd November 2011
__

Alexander A. Sherstov#### The Multiparty Communication Complexity of Set Disjointness

__
TR07-082
| 27th July 2007
__

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou#### The Myth of the Folk Theorem

__
TR94-022
| 12th December 1994
__

Christoph Meinel, Stephan Waack#### The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

__
TR09-110
| 5th November 2009
__

Scott Aaronson, Andris Ambainis#### The Need for Structure in Quantum Speedups

Revisions: 1

__
TR20-078
| 21st May 2020
__

Eric Allender#### The New Complexity Landscape around Circuit Minimization

__
TR11-155
| 22nd November 2011
__

Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen#### The NOF Multiparty Communication Complexity of Composed Functions

__
TR18-173
| 17th October 2018
__

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

Revisions: 1

__
TR02-011
| 14th October 2001
__

Boris Ryabko#### The nonprobabilistic approach to learning the best prediction.

__
TR05-128
| 27th October 2005
__

Miroslava Sotáková#### The normal form of reversible circuits consisting of CNOT and NOT gates

__
TR95-007
| 1st January 1995
__

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern#### THE NUCLEON OF COOPERATIVE GAMES AND AN ALGORITHM FOR MATCHING GAMES

__
TR95-047
| 5th October 1995
__

Martin Loebbing, Ingo Wegener#### The Number of Knight's Tours Equals 33,439,123,484,294 -- Counting with Binary Decision Diagrams

__
TR06-087
| 25th July 2006
__

Iordanis Kerenidis, Ran Raz#### The one-way communication complexity of the Boolean Hidden Matching Problem

__
TR97-025
| 26th May 1997
__

Harald Hempel, Gerd Wechsung#### The Operators min and max on the Polynomial Hierarchy

__
TR07-110
| 24th October 2007
__

Beate Bollig#### The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function

__
TR16-194
| 4th December 2016
__

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan#### The Optimality of Correlated Sampling

Revisions: 1

__
TR96-028
| 9th April 1996
__

Sanjeev Khanna, Madhu Sudan#### The Optimization Complexity of Constraint Satisfaction Problems

__
TR08-052
| 29th April 2008
__

Vikraman Arvind, T.C. Vijayaraghavan#### The Orbit problem is in the GapL Hierarchy

Revisions: 1

__
TR13-149
| 28th October 2013
__

Albert Atserias, Neil Thapen#### The Ordering Principle in a Fragment of Approximate Counting

__
TR95-013
| 24th February 1995
__

Oleg Verbitsky#### The Parallel Repetition Conjecture for Trees is True

__
TR11-071
| 27th April 2011
__

Serge Gaspers, Stefan Szeider#### The Parameterized Complexity of Local Consistency

Revisions: 1

__
TR07-100
| 25th September 2007
__

Alexander A. Sherstov#### The Pattern Matrix Method for Lower Bounds on Quantum Communication

__
TR05-046
| 17th April 2005
__

Irit Dinur#### The PCP theorem by gap amplification

Revisions: 1
,
Comments: 3

__
TR09-051
| 2nd July 2009
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy#### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

__
TR96-013
| 14th February 1996
__

Mitsunori Ogihara#### The PL Hierarchy Collapses

__
TR17-169
| 24th October 2017
__

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

__
TR06-129
| 6th October 2006
__

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf#### The polynomially bounded perfect matching problem is in NC^2

__
TR19-107
| 29th July 2019
__

Zachary Remscrim#### The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups

Revisions: 1

__
TR15-147
| 8th September 2015
__

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

__
TR09-036
| 14th April 2009
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### The Power of Depth 2 Circuits over Algebras

__
TR18-213
| 28th December 2018
__

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

Revisions: 1

__
TR95-037
| 2nd July 1995
__

Richard Beigel, Howard Straubing#### The Power of Local Self-Reductions

__
TR20-027
| 26th February 2020
__

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan#### The Power of Many Samples in Query Complexity

__
TR17-023
| 15th February 2017
__

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

__
TR15-008
| 14th January 2015
__

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

Revisions: 1

__
TR10-131
| 9th July 2010
__

Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki#### The Power of Nondeterminism in Self-Assembly

__
TR17-081
| 2nd May 2017
__

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

__
TR14-064
| 24th April 2014
__

Arkadev Chattopadhyay, Michael Saks#### The Power of Super-logarithmic Number of Players

__
TR20-004
| 17th January 2020
__

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny#### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

Revisions: 1

__
TR08-051
| 4th April 2008
__

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor#### The Power of Unentanglement

__
TR05-056
| 25th April 2005
__

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis#### The Price of Optimum in Stackelberg Games

__
TR10-034
| 7th March 2010
__

Luca Trevisan#### The Program-Enumeration Bottleneck in Average-Case Complexity Theory

__
TR11-112
| 10th August 2011
__

Dana Moshkovitz#### The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

__
TR98-078
| 1st December 1998
__

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran#### The Query Complexity of Program Checking by Constant-Depth Circuits

__
TR17-080
| 1st May 2017
__

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

__
TR19-162
| 15th November 2019
__

Ran Raz, Wei Zhan#### The Random-Query Model and the Memory-Bounded Coupon Collector

__
TR14-082
| 3rd June 2014
__

Yu Yu, Dawu Gu, Xiangxue Li#### The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions

Revisions: 3

__
TR01-099
| 1st October 2001
__

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis#### The Range of Stability for Heterogeneous and FIFO Queueing Networks

__
TR17-154
| 12th October 2017
__

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

__
TR03-051
| 20th June 2003
__

Tsuyoshi Morioka#### The Relative Complexity of Local Search Heuristics and the Iteration Principle

__
TR09-105
| 27th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

__
TR04-012
| 19th December 2003
__

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore#### The Resolution Complexity of Random Graph $k$-Colorability

__
TR06-133
| 14th October 2006
__

Alex Hertel, Alasdair Urquhart#### The Resolution Width Problem is EXPTIME-Complete

__
TR18-024
| 1st February 2018
__

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

__
TR20-076
| 17th May 2020
__

Benny Applebaum, Eliran Kachlon, Arpita Patra#### The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency

__
TR05-110
| 3rd October 2005
__

Saurabh Sanghvi, Salil Vadhan#### The Round Complexity of Two-Party Random Selection

__
TR97-060
| 2nd December 1997
__

Manindra Agrawal, Thomas Thierauf#### The Satisfiability Problem for Probabilistic Ordered Branching Programs

__
TR99-037
| 27th August 1999
__

Johan Håstad, Mats Näslund#### The Security of all RSA and Discrete Log Bits

__
TR10-169
| 10th November 2010
__

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen#### The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

Revisions: 2

__
TR15-118
| 23rd July 2015
__

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

__
TR98-016
| 24th March 1998
__

Daniele Micciancio#### The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

__
TR97-047
| 20th October 1997
__

Miklos Ajtai#### The Shortest Vector Problem in L_2 is NP-hard for Randomized Reductions.

Revisions: 1

__
TR08-029
| 7th January 2008
__

Christian Glaßer, Christian Reitwießner, Victor Selivanov#### The Shrinking Property for NP and coNP

__
TR08-016
| 26th February 2008
__

Alexander Razborov, Alexander A. Sherstov#### The Sign-Rank of AC^0

__
TR15-083
| 14th May 2015
__

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

Revisions: 1

__
TR03-063
| 2nd July 2003
__

John Hitchcock#### The Size of SPP

__
TR14-181
| 19th December 2014
__

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee#### The space "just above" BQP

__
TR14-138
| 29th October 2014
__

Nicola Galesi, Pavel Pudlak, Neil Thapen#### The space complexity of cutting planes refutations

__
TR10-071
| 19th April 2010
__

Rahul Jain, Ashwin Nayak#### The space complexity of recognizing well-parenthesized expressions

Revisions: 4

__
TR21-106
| 22nd July 2021
__

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman#### The Space Complexity of Sampling

Revisions: 1

__
TR21-114
| 29th July 2021
__

Henning Fernau, Kshitij Gajjar#### The Space Complexity of Sum Labelling

Revisions: 1

__
TR04-067
| 20th July 2004
__

hadi salmasian, ravindran kannan, Santosh Vempala#### The Spectral Method for Mixture Models

__
TR12-174
| 12th December 2012
__

Anat Ganor, Ilan Komargodski, Ran Raz#### The Spectrum of Small DeMorgan Formulas

Revisions: 1

__
TR06-001
| 1st January 2006
__

Ran Raz, Iddo Tzameret#### The Strength of Multilinear Proofs

__
TR12-162
| 26th October 2012
__

Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock#### The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity

Revisions: 1

__
TR18-045
| 6th March 2018
__

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

Revisions: 2

__
TR95-005
| 1st January 1995
__

Maciej Liskiewicz, Rüdiger Reischuk#### The Sublogarithmic Alternating Space World

__
TR07-132
| 8th December 2007
__

Emanuele Viola#### The sum of d small-bias generators fools polynomials of degree d

__
TR19-024
| 20th February 2019
__

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi#### The Surprising Power of Constant Depth Algebraic Proofs

Revisions: 2

__
TR07-062
| 15th July 2007
__

Oded Goldreich, Or Meir#### The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Revisions: 2

__
TR08-028
| 5th December 2007
__

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer#### The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments

__
TR13-144
| 8th October 2013
__

VyasRam Selvam#### The two queries assumption and Arthur-Merlin classes

__
TR16-015
| 4th February 2016
__

Oded Goldreich#### The uniform distribution is complete with respect to testing identity to a fixed distribution

Revisions: 3

__
TR14-100
| 4th August 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### The Value of Help Bits in Randomized and Average-Case Complexity

__
TR16-147
| 19th September 2016
__

Ryan O'Donnell, A. C. Cem Say#### The weakness of CTC qubits and the power of approximate counting

Revisions: 1

__
TR16-103
| 6th July 2016
__

Jaikumar Radhakrishnan, Swagato Sanyal#### The zero-error randomized query complexity of the pointer function.

__
TR21-079
| 9th June 2021
__

Venkatesan Guruswami, Xiaoyu He, Ray Li#### The zero-rate threshold for adversarial bit-deletions is less than 1/2

__
TR96-017
| 19th February 1996
__

Christoph Meinel, Stephan Waack#### The ``Log Rank'' Conjecture for Modular Communication Complexity

__
TR20-009
| 6th February 2020
__

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality

__
TR05-013
| 22nd December 2004
__

Bin Fu#### Theory and Application of Width Bounded Geometric Separator

__
TR03-039
| 19th May 2003
__

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán#### Theory Revision with Queries: Horn, Read-once, and Parity Formulas

__
TR11-030
| 9th March 2011
__

Anna Gal, Andrew Mills#### Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

__
TR01-010
| 25th January 2001
__

Oded Goldreich, Luca Trevisan#### Three Theorems regarding Testing Graph Properties.

Revisions: 1

__
TR95-056
| 26th November 1995
__

Oded Goldreich#### Three XOR-Lemmas -- An Exposition

__
TR05-139
| 21st November 2005
__

Constantinos Daskalakis, Christos H. Papadimitriou#### Three-Player Games Are Hard

__
TR02-040
| 20th June 2002
__

Lars Engebretsen, Jonas Holmerin#### Three-Query PCPs with Perfect Completeness over non-Boolean Domains

__
TR15-034
| 8th March 2015
__

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

__
TR16-131
| 21st August 2016
__

Andrej Bogdanov, Siyao Guo, Ilan Komargodski#### Threshold Secret Sharing Requires a Linear Size Alphabet

__
TR11-098
| 11th July 2011
__

Marek Karpinski, Richard Schmied, Claus Viehmann#### Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

__
TR16-033
| 10th March 2016
__

Venkatesan Guruswami, Jaikumar Radhakrishnan#### Tight bounds for communication assisted agreement distillation

__
TR21-160
| 15th November 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Tight Bounds for General Computation in Noisy Broadcast Networks

__
TR12-185
| 29th December 2012
__

Siu Man Chan, Aaron Potechin#### Tight Bounds for Monotone Switching Networks via Fourier Analysis

__
TR21-113
| 25th July 2021
__

Nikhil Mande, Ronald de Wolf#### Tight Bounds for the Randomized and Quantum Communication Complexities of Equality with Small Error

__
TR11-150
| 4th November 2011
__

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola#### Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

__
TR20-134
| 9th September 2020
__

Siddhesh Chaubal, Anna Gal#### Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions

__
TR10-063
| 12th April 2010
__

Venkatesan Guruswami, Yuan Zhou#### Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set}

Revisions: 1

__
TR21-102
| 13th July 2021
__

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff#### Tight bounds on the Fourier growth of bounded functions on the hypercube

Revisions: 1

__
TR14-174
| 14th December 2014
__

Avishay Tal#### Tight bounds on The Fourier Spectrum of $AC^0$

Revisions: 2

__
TR11-011
| 1st February 2011
__

Ming Lam Leung, Yang Li, Shengyu Zhang#### Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models

__
TR18-038
| 21st February 2018
__

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

__
TR21-140
| 27th September 2021
__

Nathan Geier#### Tight Computational Indistinguishability Bound of Product Distributions

__
TR06-132
| 17th October 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### Tight Integrality Gaps for Lovasz-Schrijver LP Relaxations of Vertex Cover and Max Cut

Revisions: 1

__
TR06-152
| 6th December 2006
__

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis#### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy

__
TR11-054
| 13th April 2011
__

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka#### Tight lower bounds for 2-query LCCs over finite fields

__
TR07-090
| 11th September 2007
__

Shachar Lovett#### Tight lower bounds for adaptive linearity tests

Revisions: 1
,
Comments: 1

__
TR13-090
| 18th June 2013
__

Elena Grigorescu, Karl Wimmer, Ning Xie#### Tight Lower Bounds for Testing Linear Isomorphism

__
TR03-035
| 21st May 2003
__

Eran Halperin, Guy Kortsarz, Robert Krauthgamer#### Tight lower bounds for the asymmetric k-center problem

__
TR16-130
| 11th August 2016
__

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra#### Tight Network Topology Dependent Bounds on Rounds of Communication

__
TR09-109
| 3rd November 2009
__

Kai-Min Chung, Feng-Hao Liu#### Tight Parallel Repetition Theorems for Public-coin Arguments

__
TR20-090
| 10th June 2020
__

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian#### Tight Quantum Time-Space Tradeoffs for Function Inversion

Revisions: 1

__
TR15-053
| 7th April 2015
__

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

__
TR21-083
| 21st June 2021
__

Mark Braverman, Sumegha Garg, Or Zamir#### Tight Space Complexity of the Coin Problem

__
TR20-003
| 15th January 2020
__

Giuseppe Persiano, Kevin Yeo#### Tight Static Lower Bounds for Non-Adaptive Data Structures

Revisions: 1

__
TR17-168
| 5th November 2017
__

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

Revisions: 6

__
TR14-152
| 13th November 2014
__

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo#### Tighter Relations Between Sensitivity and Other Complexity Measures

__
TR05-054
| 19th May 2005
__

Konstantin Pervyshev#### Time Hierarchies for Computations with a Bit of Advice

__
TR05-076
| 2nd July 2005
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### Time hierarchies for cryptographic function inversion with advice

__
TR12-026
| 27th March 2012
__

Thomas Watson#### Time Hierarchies for Sampling Distributions

Revisions: 2

__
TR07-004
| 12th January 2007
__

Lance Fortnow, Rahul Santhanam#### Time Hierarchies: A Survey

__
TR05-144
| 5th December 2005
__

Lance Fortnow, Luis Antunes#### Time-Bounded Universal Distributions

__
TR10-147
| 22nd September 2010
__

Dieter van Melkebeek, Thomas Watson#### Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

__
TR16-113
| 22nd July 2016
__

Gillat Kol, Ran Raz, Avishay Tal#### Time-Space Hardness of Learning Sparse Parities

__
TR19-071
| 14th May 2019
__

Sumegha Garg, Ran Raz, Avishay Tal#### Time-Space Lower Bounds for Two-Pass Learning

__
TR98-053
| 30th August 1998
__

Paul Beame, Michael Saks, Jayram S. Thathachar#### Time-Space Tradeoffs for Branching Programs

Comments: 1

__
TR07-036
| 6th April 2007
__

Ryan Williams#### Time-Space Tradeoffs for Counting NP Solutions Modulo Integers

__
TR18-114
| 6th June 2018
__

Paul Beame, Shayan Oveis Gharan, Xin Yang#### Time-Space Tradeoffs for Learning Finite Functions from Random Evaluations, with Applications to Polynomials

__
TR17-120
| 31st July 2017
__

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

Revisions: 1

__
TR00-028
| 17th April 2000
__

Lance Fortnow, Dieter van Melkebeek#### Time-Space Tradeoffs for Nondeterministic Computation

__
TR12-027
| 29th March 2012
__

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang#### Time-space tradeoffs for width-parameterized SAT:Algorithms and lower bounds

Revisions: 2

__
TR11-149
| 4th November 2011
__

Paul Beame, Chris Beck, Russell Impagliazzo#### Time-Space Tradeoffs in Resolution: Superpolynomial Lower Bounds for Superlinear Space

__
TR01-041
| 23rd May 2001
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay#### Time-Space Tradeoffs in the Counting Hierarchy

__
TR94-002
| 12th December 1994
__

Oded Goldreich, Avi Wigderson#### Tiny Families of Functions with Random Properties: A Quality--Size Trade--off for Hashing

Revisions: 2

__
TR09-118
| 18th November 2009
__

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin#### Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

__
TR16-105
| 13th July 2016
__

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron#### Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism

Revisions: 1

__
TR05-019
| 9th February 2005
__

Venkatesan Guruswami, Atri Rudra#### Tolerant Locally Testable Codes

__
TR04-010
| 26th January 2004
__

Michal Parnas, Dana Ron, Ronitt Rubinfeld#### Tolerant Property Testing and Distance Approximation

__
TR04-105
| 19th November 2004
__

Eldar Fischer, Lance Fortnow#### Tolerant Versus Intolerant Testing for Boolean Properties

__
TR19-166
| 20th November 2019
__

Guy Blanc, Jane Lange, Li-Yang Tan#### Top-down induction of decision trees: rigorous guarantees and inherent limitations

__
TR20-040
| 25th March 2020
__

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny#### Topology and adjunction in promise constraint satisfaction

Revisions: 1

__
TR04-108
| 24th November 2004
__

Eric Allender, Samir Datta, Sambuddha Roy#### Topology inside NC^1

__
TR14-074
| 14th May 2014
__

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra#### Topology matters in communication

__
TR18-076
| 22nd April 2018
__

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

Revisions: 2

__
TR20-153
| 6th October 2020
__

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou#### Total Functions in the Polynomial Hierarchy

__
TR14-038
| 24th March 2014
__

Ilario Bonacina, Nicola Galesi, Neil Thapen#### Total space in resolution

Revisions: 1

__
TR16-057
| 11th April 2016
__

Ilario Bonacina#### Total space in Resolution is at least width squared

__
TR01-070
| 24th October 2001
__

Robert Albin Legenstein#### Total Wire Length as a Salient Circuit Complexity Measure for Sensory Processing

__
TR09-038
| 14th April 2009
__

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen#### Toward a Model for Backtracking and Dynamic Programming

__
TR20-116
| 1st August 2020
__

Ivan Mihajlin, Alexander Smal#### Toward better depth lower bounds: the XOR-KRW conjecture

Revisions: 2

__
TR19-120
| 11th September 2019
__

Or Meir#### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revisions: 1

__
TR13-190
| 28th December 2013
__

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson#### Toward Better Formula Lower Bounds: An Information Complexity Approach to the KRW Composition Conjecture

Revisions: 11

__
TR20-144
| 7th September 2020
__

Mohammad Jahanara, Sajin Koroth, Igor Shinkar#### Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

__
TR16-035
| 11th March 2016
__

Irit Dinur, Or Meir#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

__
TR15-107
| 21st June 2015
__

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

__
TR15-105
| 21st June 2015
__

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

__
TR16-198
| 14th December 2016
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### Towards a Proof of the 2-to-1 Games Conjecture?

__
TR12-179
| 13th December 2012
__

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

__
TR17-056
| 7th April 2017
__

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

Revisions: 1

__
TR17-009
| 19th January 2017
__

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

__
TR11-014
| 3rd February 2011
__

Antoine Taveneaux#### Towards an axiomatic system for Kolmogorov complexity

Revisions: 1

__
TR12-109
| 31st August 2012
__

Subhash Khot, Muli Safra, Madhur Tulsiani#### Towards An Optimal Query Efficient PCP?

__
TR08-026
| 28th February 2008
__

Jakob Nordström, Johan Håstad#### Towards an Optimal Separation of Space and Length in Resolution

__
TR15-097
| 16th June 2015
__

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

__
TR18-036
| 21st February 2018
__

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

__
TR10-166
| 5th November 2010
__

Mark Braverman, Anup Rao#### Towards Coding for Maximum Errors in Interactive Communication

__
TR11-064
| 23rd April 2011
__

Mark Braverman#### Towards deterministic tree code constructions

__
TR07-122
| 22nd November 2007
__

Zeev Dvir, Amir Shpilka#### Towards Dimension Expanders Over Finite Fields

__
TR96-029
| 16th April 1996
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim#### Towards efficient constructions of hitting sets that derandomize BPP

__
TR06-150
| 4th December 2006
__

Patrick Briest#### Towards Hardness of Envy-Free Pricing

__
TR10-200
| 14th December 2010
__

Eli Ben-Sasson, Michael Viderman#### Towards lower bounds on locally testable codes via density arguments

__
TR19-019
| 19th February 2019
__

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi#### Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

__
TR15-165
| 14th October 2015
__

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

Revisions: 1

__
TR19-179
| 7th December 2019
__

Avishay Tal#### Towards Optimal Separations between Quantum and Randomized Query Complexities

Revisions: 1

__
TR01-009
| 5th January 2001
__

Ronen Shaltiel#### Towards proving strong direct product theorems

__
TR04-117
| 1st December 2004
__

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis#### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

__
TR20-132
| 7th September 2020
__

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif#### Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

__
TR03-082
| 22nd November 2003
__

Andris Ambainis, Ke Yang#### Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information

__
TR99-031
| 2nd September 1999
__

Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger#### Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

__
TR21-144
| 13th October 2021
__

Leroy Chew, Friedrich Slivovsky#### Towards Uniform Certification in QBF

__
TR00-070
| 14th July 2000
__

Peter Auer, Manfred K. Warmuth#### Tracking the best disjunction

__
TR05-059
| 9th May 2005
__

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien#### Tractable Clones of Polynomials over Semigroups

__
TR02-032
| 17th April 2002
__

Andrei Bulatov#### Tractable Constraint Satisfaction Problems on a 3-element set

__
TR19-160
| 10th November 2019
__

Md Lutfar Rahman, Thomas Watson#### Tractable Unordered 3-CNF Games

__
TR16-097
| 15th June 2016
__

Vivek Anand T Kallampally, Raghunath Tewari#### Trading Determinism for Time in Space Bounded Computations

__
TR08-099
| 19th November 2008
__

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena#### Trading GRH for algebra: algorithms for factoring polynomials and related structures

__
TR16-190
| 21st November 2016
__

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li#### Trading information complexity for error

__
TR15-089
| 31st May 2015
__

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

__
TR06-155
| 15th December 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

__
TR09-046
| 9th May 2009
__

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff#### Transitive-Closure Spanners of the Hypercube and the Hypergrid

__
TR07-133
| 20th November 2007
__

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan#### Trapdoors for Hard Lattices and New Cryptographic Constructions

__
TR20-061
| 28th April 2020
__

Deepanshu Kush, Benjamin Rossman#### Tree-depth and the Formula Complexity of Subgraph Isomorphism

__
TR16-027
| 10th February 2016
__

Sagnik Mukhopadhyay#### Tribes Is Hard in the Message Passing Model

Revisions: 1

__
TR16-123
| 11th August 2016
__

Stasys Jukna#### Tropical Complexity, Sidon Sets, and Dynamic Programming

__
TR05-123
| 25th October 2005
__

Olaf Beyersdorff#### Tuples of Disjoint NP-Sets

__
TR11-047
| 8th April 2011
__

Oded Goldreich#### Two Comments on Targeted Canonical Derandomizers

__
TR08-071
| 6th August 2008
__

Dana Moshkovitz, Ran Raz#### Two Query PCP with Sub-Constant Error

__
TR14-023
| 19th February 2014
__

Gil Cohen, Anat Ganor, Ran Raz#### Two Sides of the Coin Problem

Revisions: 1

__
TR13-145
| 20th October 2013
__

Gil Cohen, Avishay Tal#### Two Structural Results for Low Degree Polynomials and Applications

Revisions: 1

__
TR10-007
| 12th January 2010
__

Atri Rudra, steve uurtamo#### Two Theorems in List Decoding

__
TR04-078
| 3rd August 2004
__

Henning Fernau#### Two-Layer Planarization: Improving on Parameterized Algorithmics

__
TR12-021
| 14th March 2012
__

Oded Goldreich, Igor Shinkar#### Two-Sided Error Proximity Oblivious Testing

Revisions: 4

__
TR05-017
| 28th January 2005
__

Phong Nguyen#### Two-Sorted Theories for L, SL, NL and P

__
TR18-066
| 8th April 2018
__

Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma#### Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

__
TR15-095
| 14th June 2015
__

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

__
TR16-114
| 30th July 2016
__

Gil Cohen#### Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols

Revisions: 1

__
TR11-035
| 4th March 2011
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### Typed Monoids -- An Eilenberg-like Theorem for non regular Languages

__
TR03-007
| 15th January 2003
__

Olivier Dubois, Yacine Boufkhad, Jacques Mandler#### Typical random 3-SAT formulae and the satisfiability threshold

Olaf Beyersdorff, Leroy Chew

In this paper we compare two proof systems for minimal entailment: a tableau system OTAB and a sequent calculus MLK, both developed by Olivetti (J. Autom. Reasoning, 1992). Our main result shows that OTAB-proofs can be efficiently translated into MLK-proofs, i.e., MLK p-simulates OTAB. The simulation is technically very involved ... more >>>

Jan Krajicek

We consider tautologies formed from a pseudo-random

number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}

and in Alekhnovich et.al. \cite{ABRW}.

We explain a strategy of proving their hardness for EF via

a conjecture about bounded arithmetic formulated

in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a

purely finitary statement, in a ...
more >>>

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

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

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

Eli Ben-Sasson, Michael Viderman

We continue the study of {\em robust} tensor codes and expand the

class of base codes that can be used as a starting point for the

construction of locally testable codes via robust two-wise tensor

products. In particular, we show that all unique-neighbor expander

codes and all locally correctable codes, ...
more >>>

Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima

In this paper we study quantum nondeterminism in multiparty communication. There are three (possibly) different types of nondeterminism in quantum computation: i) strong, ii) weak with classical proofs, and iii) weak with quantum proofs. Here we focus on the first one. A strong quantum nondeterministic protocol accepts a correct input ... more >>>

Joseph Swernofsky

We prove that approximating the rank of a 3-tensor to within a factor of $1 + 1/1852 - \delta$, for any $\delta > 0$, is NP-hard over any finite field. We do this via reduction from bounded occurrence 2-SAT.

more >>>Boris Alexeev, Michael Forbes, Jacob Tsimerman

The results of Strassen and Raz show that good enough tensor rank lower bounds have implications for algebraic circuit/formula lower bounds.

We explore tensor rank lower and upper bounds, focusing on explicit tensors. For odd d, we construct field-independent explicit 0/1 tensors T:[n]^d->F with rank at least 2n^(floor(d/2))+n-Theta(d log n). ... more >>>

Ran Raz

We show that any explicit example for a tensor $A:[n]^r \rightarrow \mathbb{F}$ with tensor-rank

$\geq n^{r \cdot (1- o(1))}$,

(where $r = r(n) \leq \log n / \log \log n$), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over $\mathbb{F}$. This shows that strong enough ...
more >>>

Nader Bshouty

We develop a new notion called {\it tester of a class $\cM$ of

functions} $f:\cA\to \cC$ that maps the elements $\bfa\in \cA$ in

the domain $\cA$ of the function to a finite number (the size of

the tester) of elements $\bfb_1,\ldots,\bfb_t$ in a smaller

sub-domain $\cB\subset \cA$ where the property ...
more >>>

Madhav Jha, Sofya Raskhodnikova

A function $f : D \to R$ has Lipschitz constant $c$ if $d_R(f(x),f(y)) \leq c\cdot d_D(x,y)$ for all $x,y$ in $D$, where $d_R$ and $d_D$ denote the distance functions on the range and domain of $f$, respectively. We say a function is Lipschitz if it has Lipschitz constant 1. (Note ... more >>>

Marcos Kiwi

We study the testing problem, that is, the problem of determining (maybe

probabilistically) if a function to which we have oracle access

satisfies a given property.

We propose a framework in which to formulate and carry out the analyzes

of several known tests. This framework establishes a connection between

more >>>

Arnab Bhattacharyya, Yuichi Yoshida

Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize ... more >>>

Tom Gur, Omer Tamuz

Let $f:\{-1,1\}^n \to \mathbb{R}$ be a real function on the hypercube, given

by its discrete Fourier expansion, or, equivalently, represented as

a multilinear polynomial. We say that it is Boolean if its image is

in $\{-1,1\}$.

We show that every function on the hypercube with a ... more >>>

Dana Ron, Gilad Tsur

Property testing is concerned with deciding whether an object

(e.g. a graph or a function) has a certain property or is ``far''

(for a prespecified distance measure) from every object with

that property. In this work we consider the property of being

computable by a read-once ...
more >>>

Angsheng Li, Yicheng Pan, Pan Peng

In this paper, we study the problem of testing the conductance of a

given graph in the general graph model. Given distance parameter

$\varepsilon$ and any constant $\sigma>0$, there exists a tester

whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log

n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where

$n$ is the number of vertices and $m$ is the number ...
more >>>

Eldar Fischer, Orly Yahalom

A coloring of a graph is {\it convex} if it

induces a partition of the vertices into connected subgraphs.

Besides being an interesting property from a theoretical point of

view, tests for convexity have applications in various areas

involving large graphs. Our results concern the important subcase

of testing for ...
more >>>

Clement Canonne, Karl Wimmer

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.

Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).

Accordingly, the ...
more >>>

Noga Alon, Klim Efremenko, Benny Sudakov

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose

that on each vertex of the graph there is a player having an $n$-bit

string. Each player is allowed to communicate with its neighbors according

to an agreed communication protocol, and the players must decide,

deterministically, if their inputs ...
more >>>

Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Lior Gishboliner, Asaf Shapira

The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property $\mathcal{P}$ is said ... more >>>

Eldar Fischer

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a

randomized algorithm which, given the ability to make queries whether

a desired pair of vertices of an input graph $G$ with $n$ vertices are

adjacent or not, distinguishes, with high probability, between the

case of $G$ satisfying ...
more >>>

Oded Goldreich

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

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

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

Artur Czumaj, Asaf Shapira, Christian Sohler

We study property testing in the model of bounded degree graphs. It

is well known that in this model many graph properties cannot be

tested with a constant number of queries and it seems reasonable to

conjecture that only few are testable with o(sqrt{n}) queries.

Therefore in this paper ...
more >>>

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

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

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

Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath

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

Oded Goldreich

We consider two versions of the problem of testing graph isomorphism in the bounded-degree graph model: A version in which one graph is fixed, and a version in which the input consists of two graphs.

We essentially determine the query complexity of these testing problems in the special case of ...
more >>>

Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

Lior Gishboliner, Asaf Shapira, Henrique Stagni

Property testers are fast randomized algorithms whose task is to distinguish between inputs satisfying some predetermined property ${\cal P}$ and those that are far from satisfying it. Since these algorithms operate by inspecting a small randomly selected portion of the input, the most natural property one would like to be ... more >>>

Madhu Sudan

The last two decades have seen enormous progress in the development of sublinear-time algorithms --- i.e., algorithms that examine/reveal properties of ``data'' in less time than it would take to read all of the data. A large, and important, subclass of such properties turn out to be ``linear''. In particular, ... more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

We consider the task of testing properties of Boolean functions that

are invariant under linear transformations of the Boolean cube. Previous

work in property testing, including the linearity test and the test

for Reed-Muller codes, has mostly focused on such tasks for linear

properties. The one exception is a test ...
more >>>

Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie

The rich collection of successes in property testing raises a natural question: Why are so many different properties turning out to be locally testable? Are there some broad "features" of properties that make them testable? Kaufman and Sudan (STOC 2008) proposed the study of the relationship between the invariances satisfied ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova

A function $f(x_1, ... , x_d)$, where each input is an integer from 1 to $n$ and output is a real number, is Lipschitz if changing one of the inputs by 1 changes the output by at most 1. In other words, Lipschitz functions are not very sensitive to small ... more >>>

Omri Ben-Eliezer

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

Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, ... more >>>

Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant

We investigate the number of samples required for testing the monotonicity of a distribution with respect to an arbitrary underlying partially ordered set. Our first result is a nearly linear lower bound for the sample complexity of testing monotonicity with respect to the poset consisting of a directed perfect matching. ... more >>>

Roy Gotlib, Tali Kaufman

In this work, using methods from high dimensional expansion, we show that the property of $k$-direct-sum is testable for odd values of $k$ . Previous work of Kaufman and Lubotzky could inherently deal only with the case that $k$ is even, using a reduction to linearity testing.

Interestingly, our work ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira

Call a function $f: \mathbb{F}_2^n \to \{0,1\}$ odd-cycle-free if there are no $x_1, \dots, x_k \in \mathbb{F}_2^n$ with $k$ an odd integer such that $f(x_1) = \cdots = f(x_k) = 1$ and $x_1 + \cdots + x_k = 0$. We show that one can distinguish odd-cycle-free functions from those $\epsilon$-far ... more >>>

Tali Kaufman, Shachar Lovett

In this work we consider linear codes which are locally testable

in a sublinear number of queries. We give the first general family

of locally testable codes of exponential size. Previous results of

this form were known only for codes of quasi-polynomial size (e.g.

Reed-Muller codes). We accomplish this by ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We propose a new model for studying graph related problems

that we call the \emph{orientation model}. In this model, an undirected

graph $G$ is fixed, and the input is any possible edge orientation

of $G$. A property is now a property of the directed graph that is

obtained by a ...
more >>>

Oded Lachish, Ilan Newman

A string $\alpha\in\Sigma^n$ is called {\it p-periodic},

if for every $i,j \in \{1,\dots,n\}$, such that $i\equiv j \bmod p$,

$\alpha_i = \alpha_{j}$, where $\alpha_i$ is the $i$-th place of $\alpha$.

A string $\alpha\in\Sigma^n$ is said to be $period(\leq g)$,

if there exists $p\in \{1,\dots,g\}$ such that $\alpha$ ...
more >>>

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Suppose we are given an oracle that claims to approximate the permanent for most matrices $X$, where $X$ is chosen from the Gaussian ensemble (the matrix entries are i.i.d. univariate complex Gaussians). Can we test that the oracle satisfies this claim? This paper gives a polynomial-time algorithm for the task.

... more >>>Clement Canonne, Ronitt Rubinfeld

In this paper, we analyze and study a hybrid model for testing and learning probability distributions. Here, in addition to samples, the testing algorithm is provided with one of two different types of oracles to the unknown distribution $D$ over $[n]$. More precisely, we define both the dual and extended ... more >>>

Clement Canonne, Dana Ron, Rocco Servedio

We study a new framework for property testing of probability distributions, by considering distribution testing algorithms that have access to a conditional sampling oracle. \footnote{Independently from our work, Chakraborty et al. [CFGM13] also considered this framework. We discuss their work in Subsection 1.4.} This is an oracle that takes as ... more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We propose a framework for studying property testing of collections of distributions,

where the number of distributions in the collection is a parameter of the problem.

Previous work on property testing of distributions considered

single distributions or pairs of distributions. We suggest two models that differ

in the way the ...
more >>>

Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

We study a model of graph related formulae that we call

the \emph{Constraint-Graph model}. A

constraint-graph is a labeled multi-graph (a graph where loops

and parallel edges are allowed), where each edge $e$ is labeled

by a distinct Boolean variable and every vertex is

associate with a Boolean function over ...
more >>>

Reut Levi, Dana Ron, Ronitt Rubinfeld

We consider the problem of testing a basic property of collections of distributions: having similar means. Namely, the algorithm should accept collections of distributions in which all distributions have means that do not differ by more than some given parameter, and should reject collections that are relatively far from having ... more >>>

Paul Valiant, Paul Valiant

We introduce the notion of a Canonical Tester for a class of properties, that is, a tester strong and

general enough that ``a property is testable if and only if the

Canonical Tester tests it''. We construct a Canonical Tester

for the class of symmetric properties of one or two

more >>>

Asaf Nachmias, Asaf Shapira

We study the problem of testing the expansion of

graphs with bounded degree d in sublinear time. A graph is said to

be an \alpha-expander if every vertex set U \subset V of size at

most |V|/2 has a neighborhood of size at least \alpha|U|.

We show that the algorithm ... more >>>

Michael Langberg

A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, ... more >>>

Scott Aaronson, DeVon Ingram, William Kretschmer

We show that, in the black-box setting, the behavior of quantum polynomial-time (${BQP}$) can be remarkably decoupled from that of classical complexity classes like ${NP}$. Specifically:

-There exists an oracle relative to which ${NP}^{{BQP}}\not \subset {BQP}^{{PH}}$, resolving a 2005 problem of Fortnow. Interpreted another way, we show that ${AC^0}$ circuits ... more >>>

Eric Miles, Emanuele Viola

We put forth several simple candidate pseudorandom functions f_k : {0,1}^n -> {0,1} with security (a.k.a. hardness) 2^n that are inspired by the AES block-cipher by Daemen and Rijmen (2000). The functions are computable more efficiently, and use a shorter key (a.k.a. seed) than previous

constructions. In particular, we ...
more >>>

Michaël Cadilhac, Andreas Krebs, Pierre McKenzie

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theory of typed monoids is used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh ... more >>>

Venkatesan Guruswami

We prove hardness results for approximating set splitting problems and

also instances of satisfiability problems which have no ``mixed'' clauses,

i.e all clauses have either all their literals unnegated or all of them

negated. Recent results of Hastad imply tight hardness results for set

splitting when all sets ...
more >>>

Noga Alon, Santosh Vempala

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>

Benjamin Rossman

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

Avishay Tal

A bipartite formula on binary variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves may compute any function of either the $x$ or $y$ variables. We show that any bipartite formula for the Inner-Product ... more >>>

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka

For any given Boolean formula $\phi(x_1,\dots,x_n)$, one can

efficiently construct (using \emph{arithmetization}) a low-degree

polynomial $p(x_1,\dots,x_n)$ that agrees with $\phi$ over all

points in the Boolean cube $\{0,1\}^n$; the constructed polynomial

$p$ can be interpreted as a polynomial over an arbitrary field

$\mathbb{F}$. The problem ...
more >>>

Manindra Agrawal, Thomas Thierauf

We investigate the computational complexity of the Boolean Isomorphism problem (BI):

on input of two Boolean formulas F and G decide whether there exists a permutation of

the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

Scott Aaronson

The Busy Beaver function, with its incomprehensibly rapid growth, has captivated generations of computer scientists, mathematicians, and hobbyists. In this survey, I offer a personal view of the BB function 58 years after its introduction, emphasizing lesser-known insights, recent progress, and especially favorite open problems. Examples of such problems include: ... more >>>

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V Vinay

Agrawal and Vinay [AV08] showed how any polynomial size arithmetic circuit can be thought of as a depth four arithmetic circuit of subexponential size. The resulting circuit size in this simulation was more carefully analyzed by Korian [Koiran] and subsequently by Tavenas [Tav13]. We provide a simple proof of this ... more >>>

Or Meir, Avishay Tal

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

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

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

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

* The choice ... more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

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

Chin Ho Lee, Emanuele Viola

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

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

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

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

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

more >>>

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

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

1. Upper ... more >>>

Mark Braverman, Sumegha Garg, David Woodruff

Consider the problem of computing the majority of a stream of $n$ i.i.d. uniformly random bits. This problem, known as the {\it coin problem}, is central to a number of counting problems in different data stream models. We show that any streaming algorithm for solving this problem with large constant ... more >>>

Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

We examine the communication required for generating random variables

remotely. One party Alice will be given a distribution D, and she

has to send a message to Bob, who is then required to generate a

value with distribution exactly D. Alice and Bob are allowed

to share random bits generated ...
more >>>

Andris Ambainis, Harry Buhrman, William Gasarch, Bala Kalyansundaram, Leen Torenvliet

Normally, communication Complexity deals with how many bits

Alice and Bob need to exchange to compute f(x,y)

(Alice has x, Bob has y). We look at what happens if

Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n

and they want to compute f(x_1,y_1)... f(x_n,y_n).

THis seems hard. We look at various ...
more >>>

Alexander A. Sherstov

In the gap Hamming distance problem, two parties must

determine whether their respective strings $x,y\in\{0,1\}^n$

are at Hamming distance less than $n/2-\sqrt n$ or greater

than $n/2+\sqrt n.$ In a recent tour de force, Chakrabarti and

Regev (STOC '11) proved the long-conjectured $\Omega(n)$ bound

on the randomized communication ...
more >>>

Timothy Gowers, Emanuele Viola

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

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

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

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

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

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

Mark Braverman, Rotem Oshman

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

Benny Applebaum, Thomas Holenstein, Manoj Mishra, Ofer Shayevitz

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the ... more >>>

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>Andrei Krokhin, Jakub Opršal

We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph $H$, the $H$-colouring problem is to decide whether a given graph has a homomorphism to $H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph $H$. In ... more >>>

Scott Aaronson

A celebrated 1976 theorem of Aumann asserts that honest, rational

Bayesian agents with common priors will never "agree to disagree": if

their opinions about any topic are common knowledge, then those

opinions must be equal. Economists have written numerous papers

examining the assumptions behind this theorem. But two key questions

more >>>

Monika Henzinger, Andrea Lincoln, Barna Saha

Statistics of small subgraph counts such as triangles, four-cycles, and $s$-$t$ paths of short lengths reveal important structural properties of the underlying graph. These problems have been widely studied in social network analysis. In most relevant applications, the graphs are not only massive but also change dynamically over time. Most ... more >>>

Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

We resolve the question of the complexity of Nash equilibrium by

showing that the problem of computing a Nash equilibrium in a game

with 4 or more players is complete for the complexity class PPAD.

Our proof uses ideas from the recently-established equivalence

between polynomial-time solvability of normal-form games and

more >>>

Steffen Reith, Heribert Vollmer

We consider the problems of finding the lexicographically

minimal (or maximal) satisfying assignment of propositional

formulae for different restricted formula classes. It turns

out that for each class from our framework, the above problem

is either polynomial time solvable or complete for ...
more >>>

Mitsunori Ogihara, Seinosuke Toda

Valiant (SIAM Journal on Computing 8, pages 410--421) showed that the

roblem of counting the number of s-t paths in graphs (both in the case

of directed graphs and in the case of undirected graphs) is complete

for #P under polynomial-time one-Turing reductions (namely, some

post-computation is needed to ...
more >>>

Andrei Krokhin, Peter Jeavons, Peter Jonsson

We study interval-valued constraint satisfaction problems (CSPs),

in which the aim is to find an assignment of intervals to a given set of

variables subject to constraints on the relative positions of intervals.

Many well-known problems such as Interval Graph Recognition

and Interval Satisfiability can be considered as examples of ...
more >>>

Emanuele Viola

We study the complexity of building

pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that

is mildly hard on average, i.e. every circuit of size 2^Omega(l)

fails to compute f on at least a 1/poly(l)

fraction of inputs, we can ...
more >>>

Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz

We study probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. We consider debates of partial and zero information, where the prover is prevented from seeing some or all of ... more >>>

Heribert Vollmer

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

Thomas Watson

We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all ... more >>>

Guy Wolfovitz

We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by ... more >>>

Gil Cohen, Igor Shinkar

We study depth 3 circuits of the form $\mathrm{OR} \circ \mathrm{AND} \circ \mathrm{XOR}$, or equivalently -- DNF of parities. This model was first explicitly studied by Jukna (CPC'06) who obtained a $2^{\Omega(n)}$ lower bound for explicit functions. Several related models have gained attention in the last few years, such as ... more >>>

Thomas Watson

Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, ... more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We prove almost tight hardness results for finding independent sets in bounded degree graphs and hypergraphs that admit a good

coloring. Our specific results include the following (where $\Delta$, assumed to be a constant, is a bound on the degree, and

$n$ is the number of vertices):

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.

The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ...
more >>>

Lance Fortnow, Rakesh Vohra

Consider a weather forecaster predicting a probability of rain for

the next day. We consider tests that given a finite sequence of

forecast predictions and outcomes will either pass or fail the

forecaster. Sandroni (2003) shows that any test which passes a

forecaster who knows the distribution of nature, can ...
more >>>

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that satisfiability for Linear Temporal Logic (LTL) is either

NP-complete or PSPACE-complete, depending on the set of temporal

operators used

If, in contrast, the set of propositional operators is restricted, the

complexity may ...
more >>>

Vikraman Arvind, Gaurav Rattan

We study the complexity of Geometric Graph Isomorphism, in

$l_2$ and other $l_p$ metrics: given two sets of $n$ points $A,

B\subset \mathbb{Q}^k$ in

$k$-dimensional euclidean space the problem is to

decide if there is a bijection $\pi:A \rightarrow B$ such that for

...
more >>>

Michael Blondin, Andreas Krebs, Pierre McKenzie

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem ... more >>>

Stephen A. Fenner, William Gasarch, Brian Postow

Higman showed that if A is *any* language then SUBSEQ(A)

is regular, where SUBSEQ(A) is the language of all

subsequences of strings in A. (The result we attribute

to Higman is actually an easy consequence of his work.)

Let s_1, s_2, s_3, ...
more >>>

Dan Gutfreund, Guy Rothblum

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

Eric Allender, Robert Beals, Mitsunori Ogihara

We characterize the complexity of some natural and important

problems in linear algebra. In particular, we identify natural

complexity classes for which the problems of (a) determining if a

system of linear equations is feasible and (b) computing the rank of

an integer matrix, ...
more >>>

Uri Zwick, Michael S. Paterson

We study the complexity of finding the values and optimal strategies of

MEAN PAYOFF GAMES on graphs, a family of perfect information games

introduced by Ehrenfeucht and Mycielski and considered by Gurvich,

Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm

for the solution of such games, the decision ...
more >>>

Lefteris Kirousis, Phokion G. Kolaitis

A dichotomy theorem for a class of decision problems is

a result asserting that certain problems in the class

are solvable in polynomial time, while the rest are NP-complete.

The first remarkable such dichotomy theorem was proved by

T.J. Schaefer in 1978. It concerns the ...
more >>>

Detlef Sieling

Free Binary Decision Diagrams (FBDDs) are a data structure

for the representation and manipulation of Boolean functions.

Efficient algorithms for most of the important operations are known if

only FBDDs respecting a fixed graph ordering are considered. However,

the size of such an FBDD may strongly depend on the chosen ...
more >>>

Alexandros Hollender, Paul Goldberg

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

Moni Naor, Guy Rothblum

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

Massimo Lauria, Pavel Pudlak, Vojtech Rodl, Neil Thapen

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of ... more >>>

Boaz Barak

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

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

Scott Aaronson

This mini-course will introduce participants to an exciting frontier for quantum computing theory: namely, questions involving the computational complexity of preparing a certain quantum state or applying a certain unitary transformation. Traditionally, such questions were considered in the context of the Nonabelian Hidden Subgroup Problem and quantum interactive proof systems, ... more >>>

Shankar Kalyanaraman, Chris Umans

Given a set of observed economic choices, can one infer

preferences and/or utility functions for the players that are

consistent with the data? Questions of this type are called {\em

rationalization} or {\em revealed preference} problems in the

economic literature, and are the subject of a rich body of work.

Shankar Kalyanaraman, Chris Umans

We study the complexity of {\em rationalizing} network formation. In

this problem we fix an underlying model describing how selfish

parties (the vertices) produce a graph by making individual

decisions to form or not form incident edges. The model is equipped

with a notion of stability (or equilibrium), and we ...
more >>>

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A boolean predicate $f:\{0,1\}^k\to\{0,1\}$ is said to be {\em somewhat approximation resistant} if for some constant $\tau > \frac{|f^{-1}(1)|}{2^k}$, given a $\tau$-satisfiable instance of the MAX-$k$-CSP$(f)$ problem, it is NP-hard to find an assignment that {\it strictly beats} the naive algorithm that outputs a uniformly random assignment. Let $\tau(f)$ denote ... more >>>

Carsten Damm, Markus Holzer, Pierre McKenzie

Tensor calculus over semirings is shown relevant to complexity

theory in unexpected ways. First, evaluating well-formed tensor

formulas with explicit tensor entries is shown complete for $\olpus\P$,

for $\NP$, and for $\#\P$ as the semiring varies. Indeed the

permanent of a matrix is shown expressible as ...
more >>>

Sabyasachi Basu, Akash Kumar, C. Seshadhri

Consider property testing on bounded degree graphs and let $\varepsilon > 0$ denote the proximity parameter. A remarkable theorem of Newman-Sohler (SICOMP 2013) asserts that all properties of planar graphs (more generally hyperfinite) are testable with query complexity only depending on $\varepsilon$. Recent advances in testing minor-freeness have proven that ... more >>>

Zhixiang Chen, Bin Fu

The work in this paper is to initiate a theory of testing

monomials in multivariate polynomials. The central question is to

ask whether a polynomial represented by certain economically

compact structure has a multilinear monomial in its sum-product

expansion. The complexity aspects of this problem and its variants

are investigated ...
more >>>

Andrei A. Bulatov

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite

relational structure H can be expressed as follows: given a

relational structure G over the same vocabulary,

determine the number of homomorphisms from G to H.

In this paper we characterize relational structures H for which

#CSP(H) can be solved in ...
more >>>

Kazuo Iwama, Suguru Tamaki

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>Thanh Minh Hoang, Thomas Thierauf

We investigate the computational complexity

of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial

is in AC^0(GapL), the AC^0-closure of the logspace

counting class GapL, which is contained in NC^2.

Our main result is that the problem is hard ...
more >>>

Olaf Beyersdorff

Autoepistemic logic is one of the most successful formalisms for nonmonotonic reasoning. In this paper we provide a proof-theoretic analysis of sequent calculi for credulous and sceptical reasoning in propositional autoepistemic logic, introduced by Bonatti and Olivetti (ACM ToCL, 2002). We show that the calculus for credulous reasoning obeys almost ... more >>>

Olaf Beyersdorff, Leroy Chew

Circumscription is one of the main formalisms for non-monotonic reasoning. It uses reasoning with minimal models, the key idea being that minimal models have as few exceptions as possible. In this contribution we provide the first comprehensive proof-complexity analysis of different proof systems for propositional circumscription. In particular, we investigate ... more >>>

Vikraman Arvind, S Raja

We study two register arithmetic computation and skew arithmetic circuits. Our main results are the following:

(1) For commutative computations, we show that an exponential circuit size lower bound

for a model of 2-register straight-line programs (SLPs) which is a universal model

of computation (unlike width-2 algebraic branching programs that ...
more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

This paper is motivated by the open question

whether the union of two disjoint NP-complete sets always is

NP-complete. We discover that such unions retain

much of the complexity of their single components. More precisely,

they are complete with respect to more general reducibilities.

Irit Dinur, Shafi Goldwasser, Huijia Lin

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested ... more >>>

Kousha Etessami, Andreas Lochbihler

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

Scott Aaronson, Alex Arkhipov

We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a

model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count ...
more >>>

Grant Schoenebeck, Salil Vadhan

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number ... more >>>

Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit

We consider the computational complexity of some problems

dealing with matrix rank. Let E,S be subsets of a

commutative ring R. Let x_1, x_2, ..., x_t be variables.

Given a matrix M = M(x_1, x_2, ..., x_t) with entries

chosen from E union {x_1, x_2, ..., ...
more >>>

Mark Braverman, Kanika Pasricha

It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or ... more >>>

Berthold Ruf

Recently one has started to investigate the

computational power of spiking neurons (also called ``integrate and

fire neurons''). These are neuron models that are substantially

more realistic from the biological point of view than the

ones which are traditionally employed in artificial neural nets.

It has turned out that the ...
more >>>

Pascal Tesson, Denis Thérien

The formalism of programs over monoids has been studied for its close

connection to parallel complexity classes defined by small-depth

boolean circuits. We investigate two basic questions about this

model. When is a monoid rich enough that it can recognize arbitrary

languages (provided no restriction on length is imposed)? When ...
more >>>

Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, Christos H. Papadimitriou

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

Nayantara Bhatnagar, Parikshit Gopalan

We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>>

Shachar Lovett

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... more >>>

Periklis Papakonstantinou

We propose the following computational assumption: in general if we try to compress the depth of a circuit family (parallel time) more than a constant factor we will suffer super-quasi-polynomial blowup in the size (number of processors). This assumption is only slightly stronger than the popular assumption about the robustness ... more >>>

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

Building upon the known generalized-quantifier-based first-order

characterization of LOGCFL, we lay the groundwork for a deeper

investigation. Specifically, we examine subclasses of LOGCFL arising

from varying the arity and nesting of groupoidal quantifiers. Our

work extends the elaborate theory relating monoidal quantifiers to

NC^1 and its subclasses. In the ...
more >>>

Till Tantau

The reachability problem for graphs cannot be described, in the

sense of descriptive complexity theory, using a single first-order

formula. This is true both for directed and undirected graphs, both

in the finite and infinite. However, if we restrict ourselves to

graphs in which a certain graph parameter is fixed ...
more >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Alexander Knop

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

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

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

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

more >>>

Or Meir

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

Eric Allender, Samir Datta, Sambuddha Roy

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

Bireswar Das, Manjish Pal, Vijay Visavaliya

In this paper, we prove that most of the boolean functions, $f : \{-1,1\}^n \rightarrow \{-1,1\}$

satisfy the Fourier Entropy Influence (FEI) Conjecture due to Friedgut and Kalai (Proc. AMS'96)\cite{FG96}. The conjecture says that the Entropy of a boolean function is at most a constant times the Influence of ...
more >>>

Scott Aaronson

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability

distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input

$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set

$A_{x}$ with high probability. ...
more >>>

Leroy Chew, Judith Clymo

The solving of Quantified Boolean Formulas (QBF) has been advanced considerably in the last two decades. In response to this, several proof systems have been put forward to universally verify QBF solvers.

QRAT by Heule et al. is one such example of this and builds on technology from DRAT, ...
more >>>

Zhiyuan Fan, Jiatu Li, Tianqi Yang

How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit ... more >>>

Joan Boyar, rene peralta

We consider the problem of computing the Hamming weight of an n-bit vector using a circuit with gates for GF2 addition and multiplication only. We show the number of multiplications necessary and sufficient to build such a circuit is n - |n| where |n| is the Hamming weight of the ... more >>>

Ilya Volkovich

We present an elementary, self-contained proof of the result of Goldwasser and Rothblum [GR07] that the existence of a (perfect) statistically secure obfuscator implies a collapse of the polynomial hierarchy. In fact, we show that an existence of a weaker object implies a somewhat stronger statement. In addition, we extend ... more >>>

Jiawei Gao, Russell Impagliazzo

The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols;

first-order on ordered structures; adding various notions ...
more >>>

Janka Chlebíková, Morgan Chopin

We consider the complexity of the firefighter problem where ${b \geq 1}$ firefighters are available at each time step. This problem is proved NP-complete even on trees of degree at most three and budget one (Finbow et al. 2007) and on trees of bounded degree $b+3$ for any fixed budget ... more >>>

Miklos Ajtai, Cynthia Dwork

We describe a public-key cryptosystem with worst-case/average case

equivalence. The cryptosystem has an amortized plaintext to

ciphertext expansion of $O(n)$, relies on the hardness of the

$\tilde O(n^2)$-unique shortest vector problem for lattices, and

requires a public key of size at most $O(n^4)$ bits. The new

cryptosystem generalizes a conceptually ...
more >>>

Shachar Lovett

We study the structure of the Fourier coefficients of low degree multivariate polynomials over finite fields. We consider three properties: (i) the number of nonzero Fourier coefficients; (ii) the sum of the absolute value of the Fourier coefficients; and (iii) the size of the linear subspace spanned by the nonzero ... more >>>

Chaim Even-Zohar, Shachar Lovett

Let $G$ be a finite abelian group of torsion $r$ and let $A$ be a subset of $G$.

The Freiman-Ruzsa theorem asserts that if $|A+A| \le K|A|$

then $A$ is contained in a coset of a subgroup of $G$ of size at most $K^2 r^{K^4} |A|$. It was ...
more >>>

Jack H. Lutz

A 1976 theorem of Chaitin, strengthening a 1969 theorem of Meyer,says that infinitely many lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. ... more >>>

Henry Corrigan-Gibbs, Dmitry Kogan

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

Oded Goldreich

We consider the function ensembles emerging from the

construction of Goldreich, Goldwasser and Micali (GGM),

when applied to an arbitrary pseudoramdon generator.

We show that, in general, such functions

fail to yield correlation intractable ensembles.

Specifically, it may happen that, given a description of such a ...
more >>>

Wolfgang Merkle

We consider separations of reducibilities in the context of

resource-bounded measure theory. First, we show a result on

polynomial-time bounded reducibilities: for every p-random set R,

there is a set which is reducible to R with k+1 non-adaptive

queries, but is not reducible to any other p-random set with ...
more >>>

Oded Goldreich

The Graph Clustering Problem is parameterized by a sequence

of positive integers, $m_1,...,m_t$.

The input is a sequence of $\sum_{i=1}^{t}m_i$ graphs,

and the question is whether the equivalence classes

under the graph isomorphism relation have sizes which match

the sequence of parameters.

In this note

we show ...
more >>>

Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano

The input to the {\em Graph Clustering Problem}\/

consists of a sequence of integers $m_1,...,m_t$

and a sequence of $\sum_{i=1}^{t}m_i$ graphs.

The question is whether the equivalence classes,

under the graph isomorphism relation,

of the input graphs have sizes which match the input sequence of integers.

In this note ...
more >>>

Alexander A. Sherstov

We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the "hardest" halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all ... more >>>

Nicollas Sdroievski, Murilo Silva, André Vignatti

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

Zachary Remscrim

In this paper, we apply tools from algebraic geometry to prove new results concerning extractors for algebraic sets, the recursive Fourier sampling problem, and VC dimension. We present a new construction of an extractor which works for algebraic sets defined by polynomials over $\mathbb{F}_2$ of substantially higher degree than the ... more >>>

Vikraman Arvind, Partha Mukhopadhyay

\begin{abstract}

Given a monomial ideal $I=\angle{m_1,m_2,\cdots,m_k}$ where $m_i$

are monomials and a polynomial $f$ as an arithmetic circuit the

\emph{Ideal Membership Problem } is to test if $f\in I$. We study

this problem and show the following results.

\begin{itemize}

\item[(a)] If the ideal $I=\angle{m_1,m_2,\cdots,m_k}$ for a

more >>>

Irit Dinur, Shmuel Safra

We show Minimum Vertex Cover NP-hard to approximate to within a factor

of 1.3606. This improves on the previously known factor of 7/6.

Miklos Ajtai

The modulo $p$ counting principle is a first-order axiom

schema saying that it is possible to count modulo $p$ the number of

elements of the first-order definable subsets of the universe (and of

the finite Cartesian products of the universe with itself) in a

consistent way. It trivially holds on ...
more >>>

Rahul Jain, Shengyu Zhang

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>

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

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function

$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real

polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We

construct two halfspaces on $\{0,1\}^n$ whose intersection has

threshold degree $\Theta(\sqrt n),$ an exponential improvement on

previous lower bounds. This solves an open problem due to Klivans

(2002) and ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

Johannes Köbler, Sebastian Kuhnert

We show that k-tree isomorphism can be decided in logarithmic

space by giving a logspace canonical labeling algorithm. This improves

over the previous StUL upper bound and matches the lower bound. As a

consequence, the isomorphism, the automorphism, as well as the

canonization problem for k-trees ...
more >>>

Thomas Thierauf, Fabian Wagner

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC^1.

In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to ... more >>>

Thomas Thierauf

We investigate the computational complexity of the

isomorphism problem for one-time-only branching programs (BP1-Iso):

on input of two one-time-only branching programs B and B',

decide whether there exists a permutation of the variables of B'

such that it becomes equivalent to B.

Our main result is a two-round interactive ... more >>>

Pavel Hubacek, Moni Naor, Eylon Yogev

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>

Ludwig Staiger

We present a brief survey of results on relations between the Kolmogorov

complexity of infinite strings and several measures of information content

(dimensions) known from dimension theory, information theory or fractal

geometry.

Special emphasis is laid on bounds on the complexity of strings in

more >>>

Oded Goldreich

This is a purely pedagogical text.

We advocate using KW-games as a teaser (or ``riddle'') for a complexity theoretic course.

In particular, stating the KW-game for a familiar NP-complete problem such as 3-Colorability and asking to prove that it requires more than polylogarithmic communication poses a seemingly tractable question ...
more >>>

Mika Göös, Toniann Pitassi, Thomas Watson

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

Mark Bun, Justin Thaler

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

Scott Aaronson

Traditional quantum state tomography requires a number of measurements that grows exponentially with the number of qubits n. But using ideas from computational learning theory, we show that "for most practical purposes" one can learn a state using a number of measurements that grows only linearly with n. Besides possible ... more >>>

Zachary Remscrim

The two-way finite automaton with quantum and classical states (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA with only a single-qubit can recognize the language $L_{pal}=\{w \in \{a,b\}^*:w \text{ is ... more >>>

Mrinal Kumar, Shubhangi Saraf

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure ... more >>>

Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

Martin Dietzfelbinger

Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,

connected by k links to form a linear array, compute a function f(x,y), for

inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and

y is only known to P_k; the intermediate ...
more >>>

Shachar Lovett, Tali Kaufman

In this work we study the list-decoding size of Reed-Muller codes. Given a received word and a distance parameter, we are interested in bounding the size of the list of Reed-Muller codewords that are within that distance from the received word. Previous bounds of Gopalan, Klivans and Zuckerman~\cite{GKZ08} on the ... more >>>

Arkadev Chattopadhyay, Nikhil Mande, Suhail Sherif

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

Amin Coja-Oghlan

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$

of the independence number and the corresponding relaxations of the

chromatic number on random graphs G(n,p). We prove that \theta is

concentrated about its mean, and that the relaxations of the chromatic

number in the case ...
more >>>

Iftach Haitner, Salil Vadhan

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

Ola Svensson, Jakub Tarnawski

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

Joshua Brody

We study the one-way number-on-the-forhead (NOF) communication

complexity of the k-layer pointer jumping problem. Strong lower

bounds for this problem would have important implications in circuit

complexity. All of our results apply to myopic protocols (where

players see only one layer ahead, but can still ...
more >>>

Itsik Pe'er, Ron Shamir

The breakpoint distance between two $n$-permutations is the number

of pairs that appear consecutively in one but not in the other. In

the median problem for breakpoints one is given a set of

permutations and has to construct a permutation that minimizes the

sum of breakpoint ...
more >>>

Eric Allender, Dhiraj Holden, Valentine Kabanets

We consider variants of the Minimum Circuit Size Problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MCSP$^{QBF}$ is known to be complete for PSPACE under ZPP reductions. We show that it is not ... more >>>

Alexander Golovnev, Oded Regev, Omri Weinstein

The minrank of a graph $G$ is the minimum rank of a matrix $M$ that can be obtained from the adjacency matrix of $G$ by switching ones to zeros (i.e., deleting edges) and setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of ... more >>>

Nader Bshouty

We show that a DNF formula that has a CNF representation that contains

at least one ``$1/poly$-heavy''

clause with respect to a distribution $D$ is weakly learnable

under this distribution. So DNF that are not weakly

learnable under the distribution $D$ do not have

any ``$1/poly$-heavy'' clauses in any of ...
more >>>

Timothy Gowers, Emanuele Viola

Party $A_i$ of $k$ parties $A_1,\dots,A_k$ receives on

its forehead a $t$-tuple $(a_{i1},\dots,a_{it})$ of

elements from the group $G=\text{SL}(2,q)$. The parties

are promised that the interleaved product $a_{11}\dots

a_{k1}a_{12}\dots a_{k2}\dots a_{1t}\dots a_{kt}$ is

equal either to the identity $e$ or to some other fixed

element $g\in G$. Their goal is ...
more >>>

Alexander A. Sherstov

We study the set disjointness problem in the number-on-the-forehead model.

(i) We prove that $k$-party set disjointness has randomized and nondeterministic

communication complexity $\Omega(n/4^k)^{1/4}$ and Merlin-Arthur complexity $\Omega(n/4^k)^{1/8}.$

These bounds are close to tight. Previous lower bounds (2007-2008) for $k\geq3$ parties

were weaker than $n^{1/(k+1)}/2^{k^2}$ in all ...
more >>>

Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Kalai, Vahab Mirrokni, Christos H. Papadimitriou

The folk theorem suggests that finding Nash Equilibria

in repeated games should be easier than in one-shot games. In

contrast, we show that the problem of finding any (epsilon) Nash

equilibrium for a three-player infinitely-repeated game is

computationally intractable (even when all payoffs are in

{-1,0,-1}), unless all of PPAD ...
more >>>

Christoph Meinel, Stephan Waack

We prove that the modular communication complexity of the

undirected graph connectivity problem UCONN equals Theta(n),

in contrast to the well-known Theta(n*log n) bound in the

deterministic case, and to the Omega(n*loglog n) lower bound

in the nondeterministic case, recently proved by ...
more >>>

Scott Aaronson, Andris Ambainis

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

Eric Allender

We survey recent developments related to the Minimum Circuit Size Problem

more >>>Anil Ada, Arkadev Chattopadhyay, Omar Fawzi, Phuong Nguyen

We study the $k$-party `number on the forehead' communication complexity of composed functions $f \circ \vec{g}$, where $f:\{0,1\}^n \to \{\pm 1\}$, $\vec{g} = (g_1,\ldots,g_n)$, $g_i : \{0,1\}^k \to \{0,1\}$ and for $(x_1,\ldots,x_k) \in (\{0,1\}^n)^k$, $f \circ \vec{g}(x_1,\ldots,x_k) = f(\ldots,g_i(x_{1,i},\ldots,x_{k,i}), \ldots)$. When $\vec{g} = (g,g,\ldots,g)$ we denote $f \circ \vec{g}$ by ... more >>>

Eric Allender, Rahul Ilango, Neekon Vafa

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

Boris Ryabko

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs

to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted

using information on the word $x_1, x_2, ...., x_t $ only. We use the game

theoretical interpretation which can be traced to Laplace where there ...
more >>>

Miroslava Sotáková

This paper deals with the reversible circuits with n input and

output nodes, consisting of the reversible gates FAN-IN=FAN-OUT<3.

We define a normal form of such type of circuits and describe a reduction

algorithm to transform a circuit in this form. Furthermore we use it for

checking whether two circuits ...
more >>>

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

The {\it nucleon} is introduced as a new allocation concept for

non-negative cooperative n-person transferable utility games.

The nucleon may be viewed as the multiplicative analogue of

Schmeidler's nucleolus.

It is shown that the nucleon of (not necessarily bipartite) matching

games ...
more >>>

Martin Loebbing, Ingo Wegener

An increasing number of results in graph theory, combinatorics and

theoretical computer science is obtained with the help of computers,

e.g. the proof of the Four Colours Theorem or the computation of

certain Ramsey numbers. Binary decision diagrams, known as tools in

hardware verification ...
more >>>

Iordanis Kerenidis, Ran Raz

We give a tight lower bound of Omega(\sqrt{n}) for the randomized one-way communication complexity of the Boolean Hidden Matching Problem [BJK04]. Since there is a quantum one-way communication complexity protocol of O(log n) qubits for this problem, we obtain an exponential separation of quantum and classical one-way communication complexity for ... more >>>

Harald Hempel, Gerd Wechsung

We define a general maximization operator max and a general minimization

operator min for complexity classes and study the inclusion structure of

the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.

It turns out that Krentel's class OptP fits naturally into this frame-

work (it can be ...
more >>>

Beate Bollig

Branching programs are computation models

measuring the space of (Turing machine) computations.

Read-once branching programs (BP1s) are the

most general model where each graph-theoretical path is the computation

path for some input. Exponential lower bounds on the size of read-once

branching programs are known since a long time. Nevertheless, there ...
more >>>

Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald Rivest, Madhu Sudan

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to ... more >>>

Sanjeev Khanna, Madhu Sudan

In 1978, Schaefer considered a subclass of languages in

NP and proved a ``dichotomy theorem'' for this class. The subclass

considered were problems expressible as ``constraint satisfaction

problems'', and the ``dichotomy theorem'' showed that every language in

this class is either in P, or is NP-hard. This result is in ...
more >>>

Vikraman Arvind, T.C. Vijayaraghavan

The \emph{Orbit problem} is defined as follows: Given a matrix $A\in

\Q ^{n\times n}$ and vectors $\x,\y\in \Q ^n$, does there exist a

non-negative integer $i$ such that $A^i\x=\y$. This problem was

shown to be in deterministic polynomial time by Kannan and Lipton in

\cite{KL1986}. In this paper we place ...
more >>>

Albert Atserias, Neil Thapen

The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk ... more >>>

Oleg Verbitsky

The parallel repetition conjecture (PRC) of Feige and Lovasz says that the

error probability of a two prover one round interactive protocol repeated $n$

times in parallel is exponentially small in $n$.

We show that the PRC is true in the case when

the bipartite graph of dependence between ...
more >>>

Serge Gaspers, Stefan Szeider

We investigate the parameterized complexity of deciding whether a constraint network is $k$-consistent. We show that, parameterized by $k$, the problem is complete for the complexity class co-W[2]. As secondary parameters we consider the maximum domain size $d$ and the maximum number $\ell$ of constraints in which a variable occurs. ... more >>>

Alexander A. Sherstov

In a breakthrough result, Razborov (2003) gave optimal

lower bounds on the communication complexity of every function f

of the form f(x,y)=D(|x AND y|) for some D:{0,1,...,n}->{0,1}, in

the bounded-error quantum model with and without prior entanglement.

This was proved by the _multidimensional_ discrepancy method. We

give an entirely ...
more >>>

Irit Dinur

Let C={c_1,...,c_n} be a set of constraints over a set of

variables. The {\em satisfiability-gap} of C is the smallest

fraction of unsatisfied constraints, ranging over all possible

assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the

satisfiability-gap of a constraint-system, with only a linear ...
more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Mitsunori Ogihara

It is shown that the PL hierarchy defined in terms of the

standard Ruzzo-Simon-Tompa relativization collapses to PL.

Mark Bun, Robin Kothari, Justin Thaler

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

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The perfect matching problem is known to

be in P, in randomized NC, and it is hard for NL.

Whether the perfect matching problem is in NC is one of

the most prominent open questions in complexity

theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem

more >>>

Zachary Remscrim

The two-way quantum/classical finite automaton (2QCFA), defined by Ambainis and Watrous, is a model of quantum computation whose quantum part is extremely limited; however, as they showed, 2QCFA are surprisingly powerful: a 2QCFA, with a single qubit, can recognize, with one-sided bounded-error, the language $L_{eq}=\{a^m b^m |m \in \mathbb{N}\}$ in ... more >>>

Alexander A. Sherstov

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

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

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

some of the strongest algorithmic and complexity-theoretic results for

more >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We study the problem of polynomial identity testing (PIT) for depth

2 arithmetic circuits over matrix algebra. We show that identity

testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field

F is polynomial time equivalent to identity testing of depth 2

(Pi-Sigma) arithmetic circuits over U_2(F), the ...
more >>>

Moni Naor, Merav Parter, Eylon Yogev

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

Richard Beigel, Howard Straubing

Identify a string x over {0,1} with the positive integer

whose binary representation is 1x. We say that a self-reduction is

k-local if on input x all queries belong to {x-1,...,x-k}. We show

that all k-locally self-reducible sets belong to PSPACE. However, the

power of k-local self-reductions changes drastically between ...
more >>>

Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan

The randomized query complexity $R(f)$ of a boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is famously characterized (via Yao's minimax) by the least number of queries needed to distinguish a distribution $D_0$ over $0$-inputs from a distribution $D_1$ over $1$-inputs, maximized over all pairs $(D_0,D_1)$. We ask: Does this task become easier if we ... more >>>

Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich

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

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

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

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

Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki

We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), which was conceived to model artificial molecular self-assembling systems constructed from DNA. Designing tile systems that assemble shapes, due to the algorithmic richness of the aTAM, is a form of sophisticated "molecular programming". Of particular practical importance ... more >>>

Badih Ghazi, Madhu Sudan

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

Arkadev Chattopadhyay, Michael Saks

In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a $k \times m$ boolean matrix $A$ (where $k$ is the number of players) and Player $i$ sees all bits except those in the $i$-th row, and the players communicate by broadcast in order to evaluate a specified ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter Shor

The class QMA(k), introduced by Kobayashi et al., consists

of all languages that can be verified using k unentangled quantum

proofs. Many of the simplest questions about this class have remained

embarrassingly open: for example, can we give any evidence that k

quantum proofs are more powerful than one? Can ...
more >>>

Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>

Luca Trevisan

Three fundamental results of Levin involve algorithms or reductions

whose running time is exponential in the length of certain programs. We study the

question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly

than any other fixed ...
more >>>

Dana Moshkovitz

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

Vikraman Arvind, K.V. Subrahmanyam, N. V. Vinodchandran

In this paper we study program checking (in the

sense of Blum and Kannan) using constant-depth circuits as

checkers. Our focus is on the number of queries made by the

checker to the program being checked and we term this as the

query complexity of the checker for the given ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami

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

Ran Raz, Wei Zhan

We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables $x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i \in \{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an ... more >>>

Yu Yu, Dawu Gu, Xiangxue Li

We revisit ``the randomized iterate'' technique that was originally used by Goldreich, Krawczyk, and Luby (SICOMP 1993) and refined by Haitner, Harnik and Reingold (CRYPTO 2006) in constructing pseudorandom generators (PRGs) from regular one-way functions (OWFs). We abstract out a technical lemma with connections to several recent work on cryptography ... more >>>

Dimitrios Koukopoulos, Sotiris Nikoletseas, Paul Spirakis

In this paper, we investigate and analyze for the first time the

stability properties of heterogeneous networks, which use a

combination of different universally stable queueing policies for

packet routing, in the Adversarial Queueing model. We

interestingly prove that the combination of SIS and LIS policies,

LIS and NTS policies, ...
more >>>

Christoph Berkholz

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

Tsuyoshi Morioka

Johnson, Papadimitriou and Yannakakis introduce the class $\PLS$

consisting of optimization problems for which efficient local-

search heuristics exist. We formulate a type-2 problem $\iter$

that characterizes $\PLS$ in style of Beame et al., and prove

a criterion for type-2 problems to be nonreducible to $\iter$.

As a corollary, ...
more >>>

Vikraman Arvind, Srikanth Srinivasan

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore

We consider the resolution proof complexity of propositional formulas which encode random instances of graph $k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity.

For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any $\epsilon>0$, ...
more >>>

Alex Hertel, Alasdair Urquhart

The importance of {\em width} as a resource in resolution theorem proving

has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower

bounds on the size of resolution refutations can be proved in a uniform manner by

demonstrating lower bounds on the width ...
more >>>

Olaf Beyersdorff, Judith Clymo, Stefan Dantchev, Barnaby Martin

We give an analogue of the Riis Complexity Gap Theorem for Quanti fied Boolean Formulas (QBFs). Every fi rst-order sentence $\phi$ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like Q-Resolution are either of polynomial size (if $\phi$ has no models) or at least ... more >>>

Benny Applebaum, Eliran Kachlon, Arpita Patra

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of ... more >>>

Saurabh Sanghvi, Salil Vadhan

We study the round complexity of two-party protocols for

generating a random $n$-bit string such that the output is

guaranteed to have bounded bias (according to some measure) even

if one of the two parties deviates from the protocol (even using

unlimited computational resources). Specifically, we require that

the output's ...
more >>>

Manindra Agrawal, Thomas Thierauf

We show that the satisfiability problem for

bounded error probabilistic ordered branching programs is NP-complete.

If the error is very small however

(more precisely,

if the error is bounded by the reciprocal of the width of the branching program),

then we have a polynomial-time algorithm for the satisfiability problem.

more >>>

Johan Håstad, Mats Näslund

We study the security of individual bits in an

RSA encrypted message $E_N(x)$. We show that given $E_N(x)$,

predicting any single bit in $x$ with only a non-negligible

advantage over the trivial guessing strategy, is (through a

polynomial time reduction) as hard as breaking ...
more >>>

Siavosh Benabbas, Konstantinos Georgiou, Avner Magen

We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector

chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to

$O(1/ \epsilon)$ tightenings we show ...
more >>>

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

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

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

Daniele Micciancio

We show that computing the approximate length of the shortest vector

in a lattice within a factor c is NP-hard for randomized reductions

for any constant c<sqrt(2). We also give a deterministic reduction

based on a number theoretic conjecture.

Miklos Ajtai

We show that the shortest vector problem in lattices

with L_2 norm is NP-hard for randomized reductions. Moreover we

also show that there is a positive absolute constant c, so that to

find a vector which is longer than the shortest non-zero vector by no

more than a factor of ...
more >>>

Christian Glaßer, Christian Reitwießner, Victor Selivanov

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

Alexander Razborov, Alexander A. Sherstov

The sign-rank of a matrix A=[A_{ij}] with +/-1 entries

is the least rank of a real matrix B=[B_{ij}] with A_{ij}B_{ij}>0

for all i,j. We obtain the first exponential lower bound on the

sign-rank of a function in AC^0. Namely, let

f(x,y)=\bigwedge_{i=1}^m\bigvee_{j=1}^{m^2} (x_{ij}\wedge y_{ij}).

We show that the matrix [f(x,y)]_{x,y} has ...
more >>>

Omri Weinstein, David Woodruff

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

John Hitchcock

Derandomization techniques are used to show that at least one of the

following holds regarding the size of the counting complexity class

SPP.

1. SPP has p-measure 0.

2. PH is contained in SPP.

In other words, SPP is small by being a negligible subset of

exponential time or large ...
more >>>

Scott Aaronson, Adam Bouland, Joseph Fitzsimons, Mitchell Lee

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the ... more >>>

Nicola Galesi, Pavel Pudlak, Neil Thapen

We study the space complexity of the cutting planes proof system, in which the lines in a proof are integral linear inequalities. We measure the space used by a refutation as the number of inequalities that need to be kept on a blackboard while verifying it. We show that any ... more >>>

Rahul Jain, Ashwin Nayak

We show an Omega(sqrt(n)/T^3) lower bound for the space required by any

unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak

(2009) and rigorously establishes the peculiar power of bi-directional streams ...
more >>>

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

Henning Fernau, Kshitij Gajjar

A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most papers on sum graphs consider ... more >>>

hadi salmasian, ravindran kannan, Santosh Vempala

We present an algorithm for learning a mixture of distributions.

The algorithm is based on spectral projection and

is efficient when the components of the mixture are logconcave

distributions.

Anat Ganor, Ilan Komargodski, Ran Raz

We show a connection between the deMorgan formula size of a Boolean function and the noise stability of the function. Using this connection, we show that the Fourier spectrum of any balanced Boolean function computed by a deMorgan formula of size $s$ is concentrated on coefficients of degree up to ... more >>>

Ran Raz, Iddo Tzameret

We introduce an algebraic proof system that manipulates multilinear arithmetic formulas. We show that this proof system is fairly strong, even when restricted to multilinear arithmetic formulas of a very small depth. Specifically, we show the following:

1. Algebraic proofs manipulating depth 2 multilinear arithmetic formulas polynomially simulate Resolution, Polynomial ... more >>>

Hans-Joachim Boeckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock

The advice complexity of an online problem describes the additional information both necessary and sufficient for online algorithms to compute solutions of a certain quality. In this model, an oracle inspects the input before it is processed by an online algorithm. Depending on the input string, the oracle prepares an ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of testing properties of graphs that are presented as subgraphs of a fixed (or an explicitly given) graph.

The tester is given free access to a base graph $G=([\n],E)$, and oracle access to a function $f:E\to\{0,1\}$ that represents a subgraph of $G$.

The tester is ...
more >>>

Maciej Liskiewicz, Rüdiger Reischuk

This paper tries to fully characterize the properties and relationships

of space classes defined by Turing machines that use less than

logarithmic space - may they be deterministic,

nondeterministic or alternating (DTM, NTM or ATM).

We provide several examples of specific languages ...
more >>>

Emanuele Viola

We prove that the sum of $d$ small-bias generators $L

: \F^s \to \F^n$ fools degree-$d$ polynomials in $n$

variables over a prime field $\F$, for any fixed

degree $d$ and field $\F$, including $\F = \F_2 =

{0,1}$.

Our result improves on both the work by Bogdanov and

Viola ...
more >>>

Russell Impagliazzo, Sasank Mouli, Toniann Pitassi

A major open problem in proof complexity is to prove super-polynomial lower bounds for AC^0[p]-Frege proofs. This system is the analog of AC^0[p], the class of bounded depth circuits with prime modular counting gates. Despite strong lower bounds for this class dating back thirty years (Razborov, '86 and Smolensky, '87), ... more >>>

Oded Goldreich, Or Meir

Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it ... more >>>

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete

or PSPACE-complete, depending on the set of temporal operators used.

If, in contrast, the set of propositional operators is restricted, the complexity may decrease.

...
more >>>

VyasRam Selvam

We explore the implications of the two queries assumption, $P^{NP[1]}=P_{||}^{NP[2]}$, with respect to the polynomial hierarchy and the classes $AM$ and $MA$.

We prove the following results:

1. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $AM = MA$

2. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH \subset MA_{/1}$

3. $\exists\;B\;P^{NP[1]^B}=P^{NP[2]^B}$ and $NP^B \not\subseteq coMA^B$.

4. $P^{NP[1]}=P_{||}^{NP[2]}$ $\implies$ $PH ...
more >>>

Oded Goldreich

Inspired by Diakonikolas and Kane (2016), we reduce the class of problems consisting of testing whether an unknown distribution over $[n]$ equals a fixed distribution to this very problem when the fixed distribution is uniform over $[n]$. Our reduction preserves the parameters of the problem, which are $n$ and the ... more >>>

Salman Beigi, Omid Etesami, Amin Gohari

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity.

Amir, Beigel, and Gasarch ... more >>>

Ryan O'Donnell, A. C. Cem Say

We present two results in structural complexity theory concerned with the following interrelated

topics: computation with postselection/restarting, closed timelike curves (CTCs), and

approximate counting. The first result is a new characterization of the lesser known complexity

class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ...
more >>>

Jaikumar Radhakrishnan, Swagato Sanyal

The pointer function of G{\"{o}}{\"{o}}s, Pitassi and Watson

\cite{DBLP:journals/eccc/GoosP015a} and its variants have recently

been used to prove separation results among various measures of

complexity such as deterministic, randomized and quantum query

complexities, exact and approximate polynomial degrees, etc. In

particular, the widest possible (quadratic) separations between

deterministic and zero-error ...
more >>>

Venkatesan Guruswami, Xiaoyu He, Ray Li

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>

Christoph Meinel, Stephan Waack

The ``log rank'' conjecture consists in the question how exact

the deterministic communication complexity of a problem can be

determinied in terms of algebraic invarants of the communication

matrix of this problem. In the following, we answer this question

in the context of modular communication complexity. ...
more >>>

Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL

Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a

new approach: looking at the first Fourier level of the function after a suitable random restriction and

applying the Log-Sobolev ...
more >>>

Bin Fu

We introduce the notion of width bounded geometric separator,

develop the techniques for its existence as well as algorithm, and

apply it to obtain a $2^{O(\sqrt{n})}$ time exact algorithm for the

disk covering problem, which seeks to determine the minimal number

of fixed size disks to cover $n$ points on ...
more >>>

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

A theory, in this context, is a Boolean formula; it is

used to classify instances, or truth assignments. Theories

can model real-world phenomena, and can do so more or less

correctly.

The theory revision, or concept revision, problem is to

correct a given, roughly correct concept.

This problem is ...
more >>>

Anna Gal, Andrew Mills

Locally decodable codes

are error correcting codes with the extra property that, in order

to retrieve the correct value of just one position of the input with

high probability, it is

sufficient to read a small number of

positions of the corresponding,

possibly corrupted ...
more >>>

Oded Goldreich, Luca Trevisan

Property testing is a relaxation of decision problems

in which it is required to distinguish {\sc yes}-instances

(i.e., objects having a predetermined property) from instances

that are far from any {\sc yes}-instance.

We presents three theorems regarding testing graph

properties in the adjacency matrix representation. ...
more >>>

Oded Goldreich

We provide an exposition of three Lemmas which relate

general properties of distributions

with the exclusive-or of certain bit locations.

The first XOR-Lemma, commonly attributed to U.V. Vazirani,

relates the statistical distance of a distribution from uniform

to the maximum bias of the xor of certain bit positions.

more >>>

Constantinos Daskalakis, Christos H. Papadimitriou

We prove that computing a Nash equilibrium in a 3-player

game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

Lars Engebretsen, Jonas Holmerin

We study non-Boolean PCPs that have perfect completeness and read

three positions from the proof. For the case when the proof consists

of values from a domain of size d for some integer constant d

>= 2, we construct a non-adaptive PCP with perfect completeness

more >>>

Xin Li

We continue the study of constructing explicit extractors for independent

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

Andrej Bogdanov, Siyao Guo, Ilan Komargodski

We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$ threshold secret sharing scheme for one-bit secrets requires share size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a prime power. In 1990 Kilian and Nisan proved ... more >>>

Marek Karpinski, Richard Schmied, Claus Viehmann

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

more >>>Venkatesan Guruswami, Jaikumar Radhakrishnan

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Let $\Pi$ be a protocol over the $n$-party broadcast channel, where in each round, a pre-specified party broadcasts a symbol to all other parties. We wish to design a scheme that takes such a protocol $\Pi$ as input and outputs a noise resilient protocol $\Pi'$ that simulates $\Pi$ over the ... more >>>

Siu Man Chan, Aaron Potechin

We prove tight size bounds on monotone switching networks for the NP-complete problem of

$k$-clique, and for an explicit monotone problem by analyzing a pyramid structure of height $h$ for

the P-complete problem of generation. This gives alternative proofs of the separations of m-NC

from m-P and of m-NC$^i$ from ...
more >>>

Nikhil Mande, Ronald de Wolf

We investigate the randomized and quantum communication complexities of the well-studied Equality function with small error probability $\epsilon$, getting the optimal constant factors in the leading terms in a number of different models.

The following are our results in the randomized model:

1) We give a general technique to convert ... more >>>

Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak, Emanuele Viola

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code

$C:\{0,1\}^{\Omega(n)} \to \{0,1\}^n$ with minimum distance $\Omega(n)$,

using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are:

(1) If $d=2$ then $w = \Theta(n ({\log n/ \log \log n})^2)$.

(2) ... more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most

polynomial in sensitivity for any Boolean function.

Until a recent breakthrough of Huang, the conjecture had been

wide open in the general case,

and was proved only for a few special classes

of Boolean functions.

Huang's result implies that block ...
more >>>

Venkatesan Guruswami, Yuan Zhou

We study the approximability of two natural Boolean constraint satisfaction problems: Horn satisfiability and exact hitting set. Under the Unique Games conjecture, we prove the following optimal inapproximability and approximability results for finding an assignment satisfying as many constraints as possible given a {\em

near-satisfiable} instance.

\begin{enumerate}

\item ...
more >>>

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff

We give tight bounds on the degree $\ell$ homogenous parts $f_\ell$ of a bounded function $f$ on the cube. We show that if $f: \{\pm 1\}^n \rightarrow [-1,1]$ has degree $d$, then $\| f_\ell \|_\infty$ is bounded by $d^\ell/\ell!$, and $\| \hat{f}_\ell \|_1$ is bounded by $d^\ell e^{{\ell+1 \choose 2}} ... more >>>

Avishay Tal

We show that $AC^0$ circuits of depth $d$ and size $m$ have at most $2^{-\Omega(k/(\log m)^{d-1})}$ of their Fourier mass at level $k$ or above. Our proof builds on a previous result by H{\aa}stad (SICOMP, 2014) who proved this bound for the special case $k=n$. Our result is tight up ... more >>>

Ming Lam Leung, Yang Li, Shengyu Zhang

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin ... more >>>

Nathanael Fijalkow, Guillaume Lagarde, Pierre Ohlmann

This paper studies lower bounds for arithmetic circuits computing (non-commutative) polynomials. Our conceptual contribution is an exact correspondence between circuits and weighted automata: algebraic branching programs are captured by weighted automata over words, and circuits with unique parse trees by weighted automata over trees.

The key notion for understanding the ... more >>>

Nathan Geier

Assume that $X_0,X_1$ (respectively $Y_0,Y_1$) are $d_X$ (respectively $d_Y$) indistinguishable for circuits of a given size. It is well known that the product distributions $X_0Y_0,\,X_1Y_1$ are $d_X+d_Y$ indistinguishable for slightly smaller circuits. However, in probability theory where unbounded adversaries are considered through statistical distance, it is folklore knowledge that in ... more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study linear programming relaxations of Vertex Cover and Max Cut

arising from repeated applications of the ``lift-and-project''

method of Lovasz and Schrijver starting from the standard linear

programming relaxation.

For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that

the integrality gap remains at least $2-\epsilon$ after

$\Omega_\epsilon(\log n)$ ...
more >>>

Konstantinos Georgiou, Avner Magen, Iannis Tourlakis

We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1).

more >>>Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic

self-correcting algorithm that, with high probability, can correct any coordinate of the

codeword by looking at only a few other coordinates, even if a fraction $\delta$ of the

coordinates are corrupted. LCC's are a stronger form ...
more >>>

Shachar Lovett

Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,

which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ...
more >>>

Elena Grigorescu, Karl Wimmer, Ning Xie

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>

Eran Halperin, Guy Kortsarz, Robert Krauthgamer

In the {\sc $k$-center} problem, the input is a bound $k$

and $n$ points with the distance between every two of them,

such that the distances obey the triangle inequality.

The goal is to choose a set of $k$ points to serve as centers,

so that the maximum distance ...
more >>>

Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra

We prove tight network topology dependent bounds on the round complexity of computing well studied $k$-party functions such as set disjointness and element distinctness. Unlike the usual case in the CONGEST model in distributed computing, we fix the function and then vary the underlying network topology. This complements the recent ... more >>>

Kai-Min Chung, Feng-Hao Liu

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian

In function inversion, we are given a function $f: [N] \mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower ... more >>>

Massimo Lauria, Jakob Nordström

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

Mark Braverman, Sumegha Garg, Or Zamir

In the coin problem we are asked to distinguish, with probability at least $2/3$, between $n$ $i.i.d.$ coins which are heads with probability $\frac{1}{2}+\beta$ from ones which are heads with probability $\frac{1}{2}-\beta$. We are interested in the space complexity of the coin problem, corresponding to the width of a read-once ... more >>>

Giuseppe Persiano, Kevin Yeo

In this paper, we study the static cell probe complexity of non-adaptive data structures that maintain a subset of $n$ points from a universe consisting of $m=n^{1+\Omega(1)}$ points. A data structure is defined to be non-adaptive when the memory locations that are chosen to be accessed during a query depend ... more >>>

Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri

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

Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances ... more >>>

Konstantin Pervyshev

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We prove a time hierarchy theorem for inverting functions

computable in polynomial time with one bit of advice.

In particular, we prove that if there is a strongly

one-way function, then for any k and for any polynomial p,

there is a function f computable in linear time

with one ...
more >>>

Thomas Watson

We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, there exists a family of distributions on $k$ elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-1/k-\epsilon$ in time $t$. Our proof involves reducing ... more >>>

Lance Fortnow, Rahul Santhanam

We survey time hierarchies, with an emphasis on recent attempts to prove hierarchies for semantic classes.

more >>>Lance Fortnow, Luis Antunes

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions.

more >>>Dieter van Melkebeek, Thomas Watson

We give two time- and space-efficient simulations of quantum computations with

intermediate measurements, one by classical randomized computations with

unbounded error and the other by quantum computations that use an arbitrary

fixed universal set of gates. Specifically, our simulations show that every

language solvable by a bounded-error quantum algorithm running ...
more >>>

Gillat Kol, Ran Raz, Avishay Tal

We define a concept class ${\cal F}$ to be time-space hard (or memory-samples hard) if any learning algorithm for ${\cal F}$ requires either a memory of size super-linear in $n$ or a number of samples super-polynomial in $n$, where $n$ is the length of one sample.

A recent work shows ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz16,KRT17,Raz17,MM18,BOGY18,GRT18]. For example, any algorithm for learning parities of size $n$ requires either a memory of size $\Omega(n^{2})$ or an exponential number ... more >>>

Paul Beame, Michael Saks, Jayram S. Thathachar

We obtain the first non-trivial time-space tradeoff lower bound for

functions f:{0,1}^n ->{0,1} on general branching programs by exhibiting a

Boolean function f that requires exponential size to be computed by any

branching program of length cn, for some constant c>1. We also give the first

separation result between the ...
more >>>

Ryan Williams

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

We develop an extension of recent analytic methods for obtaining time-space tradeoff lower bounds for problems of learning from uniformly random labelled examples. With our methods we can obtain bounds for learning concept classes of finite functions from random evaluations even when the sample space of random inputs can be ... more >>>

Paul Beame, Shayan Oveis Gharan, Xin Yang

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

Lance Fortnow, Dieter van Melkebeek

We show new tradeoffs for satisfiability and nondeterministic

linear time. Satisfiability cannot be solved on general purpose

random-access Turing machines in time $n^{1.618}$ and space

$n^{o(1)}$. This improves recent results of Lipton and Viglas and

Fortnow.

Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou, Bangsheng Tang

A decade has passed since Alekhnovich and Razborov presented an algorithm that solves SAT on instances $\phi$ of size $n$ having tree-width $TW(\phi)$, using time (and space) bounded by $2^{O(TW(\phi))}n^{O(1)}$. Although there have been several papers over the ensuing years building on the work of Alekhnovich and Razborov there has ... more >>>

Paul Beame, Chris Beck, Russell Impagliazzo

We give the first time-space tradeoff lower bounds for Resolution proofs that apply to superlinear space. In particular, we show that there are formulas of size $N$ that have Resolution refutations of space and size each roughly $N^{\log_2 N}$ (and like all formulas have Resolution refutations of space $N$) for ... more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy, V Vinay

We extend the lower bound techniques of [Fortnow], to the

unbounded-error probabilistic model. A key step in the argument

is a generalization of Nepomnjascii's theorem from the Boolean

setting to the arithmetic setting. This generalization is made

possible, due to the recent discovery of logspace-uniform TC^0

more >>>

Oded Goldreich, Avi Wigderson

We present three explicit constructions of hash functions,

which exhibit a trade-off between the size of the family

(and hence the number of random bits needed to generate a member of the family),

and the quality (or error parameter) of the pseudo-random property it

achieves. Unlike previous constructions, ...
more >>>

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model.

Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ...
more >>>

Eric Blais, Clement Canonne, Talya Eden, Amit Levi, Dana Ron

The function $f\colon \{-1,1\}^n \to \{-1,1\}$ is a $k$-junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$-juntas, where the testing algorithm must accept any function that is $\epsilon$-close to some $k$-junta and reject any function that is $\epsilon'$-far from ... more >>>

Venkatesan Guruswami, Atri Rudra

An error-correcting code is said to be {\em locally testable} if it has an

efficient spot-checking procedure that can distinguish codewords

from strings that are far from every codeword, looking at very few

locations of the input in doing so. Locally testable codes (LTCs) have

generated ...
more >>>

Michal Parnas, Dana Ron, Ronitt Rubinfeld

A standard property testing algorithm is required to determine

with high probability whether a given object has property

P or whether it is \epsilon-far from having P, for any given

distance parameter \epsilon. An object is said to be \epsilon-far

from having ...
more >>>

Eldar Fischer, Lance Fortnow

A property tester with high probability accepts inputs satisfying a given property and rejects

inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron

and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We

construct properties of binary functions ...
more >>>

Guy Blanc, Jane Lange, Li-Yang Tan

Consider the following heuristic for building a decision tree for a function $f : \{0,1\}^n \to \{\pm 1\}$. Place the most influential variable $x_i$ of $f$ at the root, and recurse on the subfunctions $f_{x_i=0}$ and $f_{x_i=1}$ on the left and right subtrees respectively; terminate once the tree is an ... more >>>

Andrei Krokhin, Jakub Opršal, Marcin Wrochna, Stanislav Zivny

The approximate graph colouring problem concerns colouring a $k$-colourable

graph with $c$ colours, where $c\geq k$. This problem naturally generalises

to promise graph homomorphism and further to promise constraint satisfaction

problems. Complexity analysis of all these problems is notoriously difficult.

In this paper, we introduce ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model.

We consider other generalizations of ...
more >>>

Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra

We provide the first communication lower bounds that are sensitive to the network topology for computing natural and simple functions by point to point message passing protocols for the `Number in Hand' model. All previous lower bounds were either for the broadcast model or assumed full connectivity of the network. ... more >>>

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao Karingula

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>

Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string ... more >>>

Ilario Bonacina, Nicola Galesi, Neil Thapen

We show $\Omega(n^2)$ lower bounds on the total space used in resolution refutations of random $k$-CNFs over $n$ variables, and of the graph pigeonhole principle and the bit pigeonhole principle for $n$ holes. This answers the long-standing open problem of whether there are families of $k$-CNF formulas of size $O(n)$ ... more >>>

Ilario Bonacina

Given an unsatisfiable $k$-CNF formula $\phi$ we consider two complexity measures in Resolution: width and total space. The width is the minimal $W$ such that there exists a Resolution refutation of $\phi$ with clauses of at most $W$ literals. The total space is the minimal size $T$ of a memory ... more >>>

Robert Albin Legenstein

We introduce em total wire length as salient complexity measure

for analyzing the circuit complexity of sensory processing in

biological neural systems and neuromorphic engineering. The new

complexity measure is applied in this paper to two basic

computational problems that arise in translation- and

scale-invariant pattern recognition, and hence appear ...
more >>>

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

We propose a model called priority branching trees (pBT ) for backtracking and dynamic

programming algorithms. Our model generalizes both the priority model of Borodin, Nielson

and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence

spans a wide spectrum of algorithms. After witnessing the ...
more >>>

Ivan Mihajlin, Alexander Smal

In this paper, we propose a new conjecture, the XOR-KRW conjecture, which is a relaxation of the Karchmer-Raz-Wigderson conjecture [KRW95]. This relaxation is still strong enough to imply $\mathbf{P} \not\subseteq \mathbf{NC}^1$ if proven. We also present a weaker version of this conjecture that might be used for breaking $n^3$ lower ... more >>>

Or Meir

One of the major open problems in complexity theory is proving super-logarithmic

lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f ...
more >>>

Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the ... more >>>

Mohammad Jahanara, Sajin Koroth, Igor Shinkar

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

Irit Dinur, Or Meir

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

Sagnik Mukhopadhyay, Swagato Sanyal

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

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

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

Venkatesan Guruswami, Euiwoong Lee

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

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

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

Paul Goldberg, Christos Papadimitriou

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

Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

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

Antoine Taveneaux

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

Subhash Khot, Muli Safra, Madhur Tulsiani

We construct a PCP based on the hyper-graph linearity test with 3 free queries. It has near-perfect completeness and soundness strictly less than 1/8. Such a PCP was known before only assuming the Unique Games Conjecture, albeit with soundness arbitrarily close to 1/16.

At a technical level, our ...
more >>>

Jakob Nordström, Johan Håstad

Most state-of-the-art satisfiability algorithms today are variants of

the DPLL procedure augmented with clause learning. The main bottleneck

for such algorithms, other than the obvious one of time, is the amount

of memory used. In the field of proof complexity, the resources of

time and memory correspond to the length ...
more >>>

Marek Karpinski

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

Michael Forbes, Sumanta Ghosh, Nitin Saxena

Derandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few ... more >>>

Mark Braverman, Anup Rao

We show that it is possible to encode any communication protocol

between two parties so that the protocol succeeds even if a $(1/4 -

\epsilon)$ fraction of all symbols transmitted by the parties are

corrupted adversarially, at a cost of increasing the communication in

the protocol by a constant factor ...
more >>>

Mark Braverman

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>

Zeev Dvir, Amir Shpilka

In this paper we study the problem of explicitly constructing a

{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$

be the $n$ dimensional linear space over the field $\mathbb{F}$.

Find a small (ideally constant) set of linear transformations from

$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear

more >>>

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

The efficient construction of Hitting Sets for non trivial classes

of boolean functions is a fundamental problem in the theory

of derandomization. Our paper presents a new method to efficiently

construct Hitting Sets for the class of systems of boolean linear

functions. Systems of boolean linear functions ...
more >>>

Patrick Briest

We consider the envy-free pricing problem, in which we want to compute revenue maximizing prices for a set of products P assuming that each consumer from a set of consumer samples C will buy the product maximizing her personal utility, i.e., the difference between her respective budget and the product's ... more >>>

Eli Ben-Sasson, Michael Viderman

The main open problem in the area of locally testable codes (LTCs) is whether there exists an asymptotically good family of LTCs and to resolve this question it suffices to consider the case of query complexity $3$. We argue that to refute the existence of such an asymptotically good family ... more >>>

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS ... more >>>

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

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

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

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of $O(1)$ vs. ... more >>>

Ronen Shaltiel

A fundamental question of complexity theory is the direct product

question. Namely weather the assumption that a function $f$ is hard on

average for some computational class (meaning that every algorithm from

the class has small advantage over random guessing when computing $f$)

entails that computing $f$ on ...
more >>>

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT).

We prove strong nonapproximability results in this model for well-known problems such ... more >>>

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $\Theta(n)$. This improves upon the ... more >>>

Andris Ambainis, Ke Yang

Entanglement is an essential resource for quantum communication and quantum computation, similar to shared random bits in the classical world. Entanglement distillation extracts nearly-perfect entanglement from imperfect entangled state. The classical communication complexity of these protocols is the minimal amount of classical information that needs to be exchanged for the ... more >>>

Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger

The investigation of the possibility to efficiently compute

approximations of hard optimization problems is one of the central

and most fruitful areas of current algorithm and complexity theory.

The aim of this paper is twofold. First, we introduce the notion of

stability of approximation algorithms. This notion is shown to ...
more >>>

Leroy Chew, Friedrich Slivovsky

We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution.

These results are obtained by taking a technique ...
more >>>

Peter Auer, Manfred K. Warmuth

Littlestone developed a simple deterministic on-line learning

algorithm for learning $k$-literal disjunctions. This algorithm

(called Winnow) keeps one weight for each variable and does

multiplicative updates to its weights. We develop a randomized

version of Winnow and prove bounds for an adaptation of the

algorithm ...
more >>>

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

It is well known that coset-generating relations lead to tractable

constraint satisfaction problems. These are precisely the relations closed

under the operation $xy^{-1}z$ where the multiplication is taken in

some finite group. Bulatov et al. have on the other hand shown that

any clone containing the multiplication of some ``block-group'' ...
more >>>

Andrei Bulatov

The Constraint Satisfaction Problem (CSP) provides a common framework for many combinatorial problems. The general CSP is known to be NP-complete; however, certain restrictions on a possible form of constraints may affect the complexity, and lead to tractable problem classes. There is, therefore, a fundamental research direction, aiming to separate ... more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in ... more >>>

Vivek Anand T Kallampally, Raghunath Tewari

Savitch showed in $1970$ that nondeterministic logspace (NL) is contained in deterministic $\mathcal{O}(\log^2 n)$ space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open.

...
more >>>

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

In this paper we develop techniques that eliminate the need of the Generalized

Riemann Hypothesis (GRH) from various (almost all) known results about deterministic

polynomial factoring over finite fields. Our main result shows that given a

polynomial f(x) of degree n over a finite field k, we ...
more >>>

Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li

We consider the standard two-party communication model. The central problem studied in this article is how much one can save in information complexity by allowing an error of $\epsilon$.

For arbitrary functions, we obtain lower bounds and upper bounds indicating a gain that is of order $\Omega(h(\epsilon))$ and $O(h(\sqrt{\epsilon}))$. ...
more >>>

Eldar Fischer, Oded Lachish, Yadu Vadusev

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

Wenceslas Fernandez de la Vega, Marek Karpinski

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... more >>>

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

Craig Gentry, Chris Peikert, Vinod Vaikuntanathan

We show how to construct a variety of ``trapdoor'' cryptographic tools

assuming the worst-case hardness of standard lattice problems (such as

approximating the shortest nonzero vector to within small factors).

The applications include trapdoor functions with \emph{preimage

sampling}, simple and efficient ``hash-and-sign'' digital signature

schemes, universally composable oblivious transfer, ...
more >>>

Deepanshu Kush, Benjamin Rossman

For a fixed "pattern" graph $G$, the $\textit{colored}$ $G\textit{-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ... more >>>

Sagnik Mukhopadhyay

We consider the point-to-point message passing model of communication in which there are $k$ processors

with individual private inputs, each $n$-bit long. Each processor is located at the node of an underlying

undirected graph and has access to private random coins. An edge of the graph is a private channel ...
more >>>

Stasys Jukna

Many dynamic programming algorithms for discrete 0-1 optimization problems are just special (recursively constructed) tropical (min,+) or (max,+) circuits. A problem is homogeneous if all its feasible solutions have the same number of 1s. Jerrum and Snir [JACM 29 (1982), pp. 874-897] proved that tropical circuit complexity of homogeneous problems ... more >>>

Olaf Beyersdorff

Disjoint NP-pairs are a well studied complexity theoretic concept with

important applications in cryptography and propositional proof

complexity.

In this paper we introduce a natural generalization of the notion of

disjoint NP-pairs to disjoint k-tuples of NP-sets for k>1.

We define subclasses of ...
more >>>

Oded Goldreich

We revisit the notion of a {\em targeted canonical derandomizer},

introduced in our recent ECCC Report (TR10-135) as a uniform notion of

a pseudorandom generator that suffices for yielding BPP=P.

The original notion was derived (as a variant of the standard notion

of a canonical derandomizer) by providing both ...
more >>>

Dana Moshkovitz, Ran Raz

We show that the NP-Complete language 3Sat has a PCP

verifier that makes two queries to a proof of almost-linear size

and achieves sub-constant probability of error $o(1)$. The

verifier performs only projection tests, meaning that the answer

to the first query determines at most one accepting answer to the

more >>>

Gil Cohen, Anat Ganor, Ran Raz

In the Coin Problem, one is given n independent flips of a coin that has bias $\beta > 0$ towards either Head or Tail. The goal is to decide which side the coin is biased towards, with high confidence. An optimal strategy for solving the coin problem is to apply ... more >>>

Gil Cohen, Avishay Tal

In this paper, two structural results concerning low degree polynomials over the field $\mathbb{F}_2$ are given. The first states that for any degree d polynomial f in n variables, there exists a subspace of $\mathbb{F}_2^n$ with dimension $\Omega(n^{1/(d-1)})$ on which f is constant. This result is shown to be tight. ... more >>>

Atri Rudra, steve uurtamo

We prove the following results concerning the list decoding of error-correcting codes:

We show that for any code with a relative distance of $\delta$

(over a large enough alphabet), the

following result holds for random errors: With high probability,

for a $\rho\le \delta -\eps$ fraction of random errors (for any ...
more >>>

Henning Fernau

A bipartite graph is biplanar if the vertices can be

placed on two parallel lines in the plane such that there are

no edge crossings when edges are drawn as straight-line segments.

We study two variants of biplanarization problems:

- Two-Layer Planarization TLP: can $k$ edges be deleted from

a ...
more >>>

Oded Goldreich, Igor Shinkar

Loosely speaking, a proximity-oblivious (property) tester is a randomized algorithm that makes a constant number of queries to a tested object and distinguishes objects that have a predetermined property from those that lack it. Specifically, for some threshold probability $c$, objects having the property are accepted with probability at least ... more >>>

Phong Nguyen

We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP

that characterize the classes L, SL, NL and P in the same

way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy.

Our theories arise from natural combinatorial problems, namely the st-Connectivity

Problem and the Circuit Value Problem.

It ...
more >>>

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

In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error $\varepsilon$ for $n$-bit sources having min-entropy $poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is $poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a $poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any $k ... more >>>

Gil Cohen

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

Gil Cohen

This paper offers the following contributions:

* We construct a two-source extractor for quasi-logarithmic min-entropy. That is, an extractor for two independent $n$-bit sources with min-entropy $\widetilde{O}(\log{n})$. Our construction is optimal up to $\mathrm{poly}(\log\log{n})$ factors and improves upon a recent result by Ben-Aroya, Doron, and Ta-Shma (ECCC'16) that can handle ... more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

Based on different concepts to obtain a finer notion of language recognition via finite monoids we develop an algebraic structure called typed monoid.

This leads to an algebraic description of regular and non regular languages.

We obtain for each language a unique minimal recognizing typed monoid, the typed syntactic monoid.

more >>>

Olivier Dubois, Yacine Boufkhad, Jacques Mandler

$k$-SAT is one of the best known among a wide class of random

constraint satisfaction problems believed to exhibit a threshold

phenomenon where the control parameter is the ratio, number of

constraints to number of variables. There has been a large amount of

work towards estimating ...
more >>>