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

**A**

__
TR11-028
| 24th February 2011
__

Richard Beigel, Bin Fu#### A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing

__
TR18-162
| 16th September 2018
__

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan#### A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates

__
TR17-159
| 28th October 2017
__

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

__
TR16-133
| 25th August 2016
__

C. Seshadhri, Deeparnab Chakrabarty#### A $\widetilde{O}(n)$ Non-Adaptive Tester for Unateness

Revisions: 1

__
TR07-047
| 15th May 2007
__

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum#### A (De)constructive Approach to Program Checking

__
TR04-084
| 28th September 2004
__

George Karakostas#### A better approximation ratio for the Vertex Cover problem

__
TR15-166
| 17th October 2015
__

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

Revisions: 2

__
TR22-033
| 1st March 2022
__

Ivan Mihajlin, Anastasia Sofronova#### A better-than-$3\log{n}$ depth lower bound for De Morgan formulas with restrictions on top gates

Comments: 2

__
TR18-142
| 17th August 2018
__

Kaave Hosseini, Shachar Lovett#### A bilinear Bogolyubov-Ruzsa lemma with poly-logarithmic bounds

__
TR22-130
| 15th September 2022
__

Hamed Hatami, Kaave Hosseini, Xiang Meng#### A Borsuk-Ulam lower bound for sign-rank and its application

__
TR09-028
| 2nd April 2009
__

Oded Goldreich#### A Candidate Counterexample to the Easy Cylinders Conjecture

__
TR11-021
| 13th February 2011
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### A Case of Depth-3 Identity Testing, Sparse Factorization and Duality

__
TR13-146
| 20th October 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Approximation Resistance

Revisions: 1

__
TR16-201
| 19th December 2016
__

Eric Blais, Yuichi Yoshida#### A Characterization of Constant-Sample Testable Properties

__
TR22-035
| 7th March 2022
__

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff#### A Characterization of Multiclass Learnability

__
TR13-075
| 23rd May 2013
__

Subhash Khot, Madhur Tulsiani, Pratik Worah#### A Characterization of Strong Approximation Resistance

__
TR12-161
| 20th November 2012
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### A Characterization of Tree-Like Resolution Size

__
TR14-156
| 26th November 2014
__

Jayadev Acharya, Clement Canonne, Gautam Kamath#### A Chasm Between Identity and Equivalence Testing with Conditional Queries

Revisions: 2

__
TR10-179
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### A CLT and tight lower bounds for estimating entropy

Revisions: 1

__
TR11-087
| 3rd June 2011
__

Michael Viderman#### A Combination of Testability and Decodability by Tensor Products

Revisions: 3

__
TR99-030
| 9th July 1999
__

Meena Mahajan, P R Subramanya, V Vinay#### A Combinatorial Algorithm for Pfaffians

__
TR10-095
| 11th June 2010
__

Masaki Yamamoto#### A combinatorial analysis for the critical clause tree

__
TR02-035
| 27th May 2002
__

Albert Atserias, Víctor Dalmau#### A Combinatorial Characterization of Resolution Width

__
TR12-159
| 20th November 2012
__

Eli Ben-Sasson, Michael Viderman#### A Combinatorial Characterization of smooth LTCs and Applications

__
TR03-044
| 12th May 2003
__

Juan Luis Esteban, Jacobo Toran#### A Combinatorial Characterization of Treelike Resolution Space

__
TR96-047
| 2nd September 1996
__

Oded Goldreich, Muli Safra#### A Combinatorial Consistency Lemma with application to the PCP Theorem

Revisions: 1

__
TR07-066
| 24th April 2007
__

Maciej Liskiewicz, Christian Hundt#### A Combinatorial Geometric Approach to Linear Image Matching

__
TR20-043
| 29th March 2020
__

Dorit Aharonov, Alex Bredariol Grilo#### A combinatorial MA-complete problem

Revisions: 2

__
TR96-039
| 27th June 1996
__

Carme Alvarez, Raymond Greenlaw#### A Compendium of Problems Complete for Symmetric Logarithmic Space

Comments: 2

__
TR10-018
| 15th February 2010
__

Vitaly Feldman#### A Complete Characterization of Statistical Query Learning with Applications to Evolvability

Revisions: 1

__
TR96-062
| 3rd December 1996
__

Sanjeev Khanna, Madhu Sudan, David P. Williamson#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

__
TR00-084
| 6th November 2000
__

Salil Vadhan, Amit Sahai#### A Complete Problem for Statistical Zero Knowledge

__
TR06-046
| 1st April 2006
__

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev#### A Complete Public-Key Cryptosystem

Comments: 1

__
TR10-092
| 22nd May 2010
__

Charanjit Jutla, Arnab Roy#### A Completeness Theorem for Pseudo-Linear Functions with Applications to UC Security

Revisions: 1
,
Comments: 1

__
TR09-140
| 18th December 2009
__

Saugata Basu#### A complex analogue of Toda's Theorem

Revisions: 1

__
TR15-167
| 15th October 2015
__

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

__
TR96-059
| 12th November 1996
__

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz#### A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

__
TR17-107
| 1st June 2017
__

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

Revisions: 1

__
TR18-014
| 10th January 2018
__

Swagato Sanyal#### A Composition Theorem via Conflict Complexity

__
TR15-142
| 28th August 2015
__

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

__
TR08-046
| 14th April 2008
__

Nikhil R. Devanur, Lance Fortnow#### A Computational Theory of Awareness and Decision Making

__
TR11-051
| 8th April 2011
__

Thomas Vidick#### A concentration inequality for the overlap of a vector on a large set, With application to the communication complexity of the Gap-Hamming-Distance problem

__
TR02-061
| 14th November 2002
__

Miklos Ajtai#### A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.

__
TR98-010
| 22nd January 1998
__

Phong Nguyen, Jacques Stern#### A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

__
TR12-173
| 8th December 2012
__

Kfir Barhum, Thomas Holenstein#### A Cookbook for Black-Box Separations and a Recipe for UOWHFs

__
TR08-018
| 28th February 2008
__

Ran Raz#### A Counterexample to Strong Parallel Repetition

__
TR10-026
| 25th February 2010
__

Hao Huang, Benny Sudakov#### A counterexample to the Alon-Saks-Seymour conjecture and related problems

__
TR10-109
| 11th July 2010
__

Scott Aaronson#### A Counterexample to the Generalized Linial-Nisan Conjecture

__
TR97-055
| 22nd September 1997
__

Bruce Edward Litow#### A Decision Method for the Rational Sequence Problem

__
TR10-098
| 17th June 2010
__

Daniel Kane, Jelani Nelson#### A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

__
TR12-116
| 13th September 2012
__

Luca Trevisan#### A Derandomized Switching Lemma and an Improved Derandomization of AC0

Revisions: 1

__
TR10-014
| 2nd February 2010
__

Daniele Micciancio, Panagiotis Voulgaris#### A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations

Revisions: 1

__
TR11-126
| 17th September 2011
__

Benny Applebaum, Andrej Bogdanov, Alon Rosen#### A Dichotomy for Local Small-Bias Generators

__
TR07-029
| 20th January 2007
__

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto#### A Dichotomy Theorem within Schaefer for the Boolean Connectivity Problem

Revisions: 1

__
TR20-131
| 20th August 2020
__

Rahul Jain, Srijita Kundu#### A Direct Product Theorem for One-Way Quantum Communication

__
TR21-078
| 8th June 2021
__

Rahul Jain, Srijita Kundu#### A direct product theorem for quantum communication complexity with applications to device-independent QKD

__
TR11-164
| 9th December 2011
__

Mark Braverman, Omri Weinstein#### A discrepancy lower bound for information complexity

__
TR98-050
| 6th July 1998
__

Farid Ablayev, Svetlana Ablayeva#### A Discrete Approximation and Communication Complexity Approach to the Superposition Problem

__
TR08-106
| 12th November 2008
__

Jack H. Lutz#### A Divergence Formula for Randomness and Dimension

__
TR17-092
| 10th May 2017
__

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

__
TR17-141
| 19th September 2017
__

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

__
TR09-037
| 10th April 2009
__

Parikshit Gopalan#### A Fourier-analytic approach to Reed-Muller decoding

__
TR13-027
| 29th January 2013
__

Luke Friedman#### A Framework for Proving Proof Complexity Lower Bounds on Random CNFs Using Encoding Techniques

__
TR10-057
| 1st April 2010
__

Scott Aaronson, Andrew Drucker#### A Full Characterization of Quantum Advice

Revisions: 3

__
TR11-036
| 17th March 2011
__

Gilad Asharov, Yehuda Lindell#### A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation

Revisions: 5

__
TR14-131
| 7th October 2014
__

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah#### A game characterisation of tree-like Q-Resolution size

__
TR02-003
| 24th December 2001
__

Eli Ben-Sasson, Yonatan Bilu#### A Gap in Average Proof Complexity

__
TR02-058
| 25th September 2002
__

Philippe Moser#### A generalization of Lutz's measure to probabilistic classes

__
TR98-058
| 2nd August 1998
__

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar#### A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

__
TR13-093
| 21st June 2013
__

Anna Gal, Jing-Tang Jang#### A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators

__
TR15-078
| 4th May 2015
__

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

__
TR18-007
| 9th January 2018
__

Lior Gishboliner, Asaf Shapira#### A Generalized Turan Problem and its Applications

__
TR05-111
| 3rd October 2005
__

Dieter van Melkebeek, Konstantin Pervyshev#### A Generic Time Hierarchy for Semantic Models With One Bit of Advice

__
TR05-009
| 14th December 2004
__

David P. Woodruff, Sergey Yekhanin#### A Geometric Approach to Information-Theoretic Private Information Retrieval

__
TR09-096
| 7th October 2009
__

Haralampos Tsaknakis, Paul Spirakis#### A Graph Spectral Approach for Computing Approximate Nash Equilibria

__
TR15-115
| 20th July 2015
__

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

__
TR96-050
| 23rd September 1996
__

Petr Savicky, Stanislav Zak#### A hierarchy for (1,+k)-branching programs with respect to k

__
TR01-017
| 14th February 2001
__

Petr Savicky, Detlef Sieling#### A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism

__
TR08-098
| 12th November 2008
__

Victor Chen#### A Hypergraph Dictatorship Test with Perfect Completeness

Revisions: 1

__
TR01-059
| 20th July 2001
__

Elvira Mayordomo#### A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

__
TR11-018
| 8th February 2011
__

Jochen Messner, Thomas Thierauf#### A Kolmogorov Complexity Proof of the Lovász Local Lemma for Satisfiability

__
TR96-036
| 28th May 1996
__

Petr Savicky, Stanislav Zak#### A large lower bound for 1-branching programs

Revisions: 1

__
TR06-098
| 17th August 2006
__

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani#### A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover

__
TR00-074
| 12th July 2000
__

Daniele Micciancio, Bogdan Warinschi#### A Linear Space Algorithm for Computing the Hermite Normal Form

__
TR11-043
| 25th March 2011
__

Scott Aaronson#### A Linear-Optical Proof that the Permanent is #P-Hard

__
TR09-049
| 5th May 2009
__

Derrick Stolee, Chris Bourke, N. V. Vinodchandran#### A log-space algorithm for reachability in planar DAGs with few sources

__
TR08-083
| 10th June 2008
__

Yijia Chen, Jörg Flum#### A logic for PTIME and a parameterized halting problem

__
TR19-150
| 24th October 2019
__

Stanislav Žák#### A Logical Characteristic of Read-Once Branching Programs

__
TR22-054
| 21st April 2022
__

Anastasia Sofronova, Dmitry Sokolov#### A Lower Bound for $k$-DNF Resolution on Random CNF Formulas via Expansion

__
TR18-140
| 11th August 2018
__

Ilan Komargodski, Ran Raz, Yael Tauman Kalai#### A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols

Revisions: 1

__
TR10-087
| 17th May 2010
__

Shachar Lovett, Ely Porat#### A lower bound for dynamic approximate membership data structures

__
TR98-011
| 29th January 1998
__

Farid Ablayev, Marek Karpinski#### A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

__
TR17-111
| 2nd June 2017
__

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

__
TR99-010
| 1st April 1999
__

Eric Allender, Igor E. Shparlinski, Michael Saks#### A Lower Bound for Primality

Comments: 1

__
TR95-063
| 19th December 1995
__

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky#### A Lower Bound for Randomized Algebraic Decision Trees

__
TR97-019
| 5th May 1997
__

Martin Sauerhoff#### A Lower Bound for Randomized Read-k-Times Branching Programs

__
TR19-056
| 11th April 2019
__

Tom Gur, Oded Lachish#### A Lower Bound for Relaxed Locally Decodable Codes

Revisions: 1

__
TR19-066
| 3rd May 2019
__

Thomas Watson#### A Lower Bound for Sampling Disjoint Sets

Revisions: 2

__
TR10-081
| 10th May 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria#### A Lower Bound for the Pigeonhole Principle in Tree-like Resolution by Asymmetric Prover-Delayer Games

__
TR06-060
| 4th May 2006
__

Ran Raz, Amir Shpilka, Amir Yehudayoff#### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

__
TR20-129
| 5th September 2020
__

Mrinal Kumar, Ben Lee Volk#### A Lower Bound on Determinantal Complexity

__
TR21-129
| 6th September 2021
__

Oded Goldreich, Dana Ron#### A Lower Bound on the Complexity of Testing Grained Distributions

__
TR02-002
| 3rd January 2002
__

Howard Barnum, Michael Saks#### A lower bound on the quantum query complexity of read-once functions

__
TR11-162
| 7th December 2011
__

Pavel Pudlak#### A lower bound on the size of resolution proofs of the Ramsey theorem

__
TR08-110
| 19th November 2008
__

Chris Calabro#### A Lower Bound on the Size of Series-Parallel Graphs Dense in Long Paths

__
TR01-101
| 14th December 2001
__

Philipp Woelfel#### A Lower Bound Technique for Restricted Branching Programs and Applications

__
TR21-024
| 15th February 2021
__

Mika Göös, Gilbert Maystre#### A Majority Lemma for Randomised Query Complexity

__
TR19-130
| 26th September 2019
__

Naomi Kirshner, Alex Samorodnitsky#### A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres

__
TR12-085
| 5th July 2012
__

Tsuyoshi Ito, Thomas Vidick#### A multi-prover interactive proof for NEXP sound against entangled provers

__
TR09-015
| 19th February 2009
__

Joshua Brody, Amit Chakrabarti#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

__
TR22-101
| 15th July 2022
__

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar#### A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation

__
TR18-062
| 7th April 2018
__

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan#### A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

__
TR17-051
| 16th March 2017
__

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

__
TR03-087
| 10th December 2003
__

Richard Beigel, Lance Fortnow, William Gasarch#### A Nearly Tight Bound for Private Information Retrieval Protocols

Comments: 1

__
TR16-058
| 12th April 2016
__

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin#### A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

__
TR99-036
| 6th September 1999
__

Edward Hirsch#### A New Algorithm for MAX-2-SAT

Revisions: 2

__
TR04-032
| 5th February 2004
__

Ryan Williams#### A new algorithm for optimal constraint satisfaction and its implications

__
TR16-074
| 9th May 2016
__

Ilias Diakonikolas, Daniel Kane#### A New Approach for Testing Properties of Discrete Distributions

__
TR10-064
| 13th April 2010
__

Xin Li#### A New Approach to Affine Extractors and Dispersers

__
TR15-161
| 24th September 2015
__

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

__
TR98-013
| 3rd March 1998
__

Nader Bshouty#### A New Composition Theorem for Learning Algorithms

__
TR12-148
| 7th November 2012
__

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf#### A new family of locally correctable codes based on degree-lifted algebraic geometry codes

Revisions: 1

__
TR06-096
| 10th August 2006
__

Iftach Haitner, Omer Reingold#### A New Interactive Hashing Theorem

__
TR09-059
| 2nd July 2009
__

Gábor Kun, Mario Szegedy#### A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

__
TR09-025
| 11th March 2009
__

Arnaldo Moura, Igor Carboni Oliveira#### A New Look at Some Classical Results in Computational Complexity

__
TR19-014
| 22nd January 2019
__

Himanshu Tyagi, Shun Watanabe#### A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem

__
TR10-001
| 30th December 2009
__

Iftach Haitner, Mohammad Mahmoody, David Xiao#### A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of $NP$

__
TR98-005
| 27th January 1998
__

Jin-Yi Cai#### A new transference theorem and applications to Ajtai's connection factor

__
TR12-046
| 24th April 2012
__

Madhu Sudan, Noga Ron-Zewi#### A new upper bound on the query complexity for testing generalized Reed-Muller codes

Revisions: 1

__
TR99-026
| 7th July 1999
__

Miklos Ajtai#### A Non-linear Time Lower Bound for Boolean Branching Programs

__
TR05-122
| 31st October 2005
__

Pavel Pudlak#### A nonlinear bound on the number of wires in bounded depth circuits

__
TR06-089
| 16th July 2006
__

Sofya Raskhodnikova, Adam Smith#### A Note on Adaptivity in Testing Properties of Bounded Degree Graphs

__
TR10-134
| 23rd August 2010
__

Avraham Ben-Aroya, Klim Efremenko, Amnon Ta-Shma#### A Note on Amplifying the Error-Tolerance of Locally Decodable Codes

Revisions: 2

__
TR00-043
| 21st June 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### A Note on Approximating MAX-BISECTION on Regular Graphs

__
TR13-106
| 29th July 2013
__

Shay Moran, Amir Yehudayoff#### A note on average-case sorting

Revisions: 2

__
TR10-099
| 20th June 2010
__

T.C. Vijayaraghavan#### A Note on Closure Properties of ModL

__
TR02-069
| 14th November 2002
__

Luca Trevisan#### A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

__
TR04-047
| 22nd April 2004
__

Xiaoyang Gu#### A note on dimensions of polynomial size circuits

__
TR09-069
| 2nd September 2009
__

Parikshit Gopalan#### A note on Efremenko's Locally Decodable Codes

Revisions: 1

__
TR10-174
| 12th November 2010
__

Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek#### A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

__
TR20-158
| 26th October 2020
__

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla#### A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity

__
TR10-171
| 11th November 2010
__

Michael Viderman#### A Note on high-rate Locally Testable Codes with sublinear query complexity

__
TR99-009
| 26th March 1999
__

Marek Karpinski, Rustam Mubarakzjanov#### A Note on Las Vegas OBDDs

__
TR22-085
| 8th June 2022
__

Andrzej Lingas#### A Note on Lower Bounds for Monotone Multilinear Boolean Circuits

__
TR17-048
| 14th March 2017
__

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

__
TR21-092
| 28th June 2021
__

Yanyi Liu, Rafael Pass#### A Note on One-way Functions and Sparse Languages

__
TR15-187
| 24th November 2015
__

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

Revisions: 1

__
TR10-100
| 25th June 2010
__

Amit Chakrabarti#### A Note on Randomized Streaming Space Bounds for the Longest Increasing Subsequence Problem

__
TR94-027
| 12th December 1994
__

Stasys Jukna#### A Note on Read-k Times Branching Programs

__
TR95-009
| 2nd February 1995
__

Matthias Krause#### A note on realizing iterated multiplication by small depth threshold circuits

__
TR13-128
| 16th September 2013
__

Pavel Hrubes#### A note on semantic cutting planes

__
TR07-105
| 21st September 2007
__

Jelani Nelson#### A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

__
TR01-029
| 27th March 2001
__

Denis Xavier Charles#### A Note on Subgroup Membership Problem for PSL(2,p).

Comments: 1

__
TR12-095
| 23rd July 2012
__

Avraham Ben-Aroya, Igor Shinkar#### A Note on Subspace Evasive Sets

__
TR16-065
| 18th April 2016
__

Xi Chen, Yu Cheng, Bo Tang#### A Note on Teaching for VC Classes

Revisions: 1

__
TR05-130
| 31st October 2005
__

Ahuva Mu'alem#### A Note on Testing Truthfulness

__
TR04-056
| 1st July 2004
__

N. V. Vinodchandran#### A note on the circuit complexity of PP

__
TR13-069
| 1st May 2013
__

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis#### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing

__
TR01-092
| 2nd October 2001
__

Till Tantau#### A Note on the Complexity of the Reachability Problem for Tournaments

__
TR06-076
| 4th May 2006
__

Noam Nisan#### A Note on the computational hardness of evolutionary stable strategies

__
TR08-012
| 20th November 2007
__

Arnab Bhattacharyya#### A Note on the Distance to Monotonicity of Boolean Functions

__
TR20-019
| 19th February 2020
__

Siddharth Bhandari, Prahladh Harsha#### A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet

__
TR00-088
| 28th November 2000
__

Meena Mahajan, V Vinay#### A note on the hardness of the characteristic polynomial

__
TR12-092
| 6th July 2012
__

Pavol Duris#### A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata.

__
TR17-187
| 3rd December 2017
__

Roei Tell#### A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization

__
TR01-058
| 28th August 2001
__

Stasys Jukna#### A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

__
TR04-062
| 28th July 2004
__

Stasys Jukna#### A note on the P versus NP intersected with co-NP question in communication complexity

Revisions: 1
,
Comments: 1

__
TR02-004
| 2nd November 2001
__

Till Tantau#### A Note on the Power of Extra Queries to Membership Comparable Sets

__
TR12-121
| 25th September 2012
__

Pavel Hrubes#### A note on the real $\tau$-conjecture and the distribution of roots

Revisions: 2

__
TR19-105
| 16th August 2019
__

Ragesh Jaiswal#### A note on the relation between XOR and Selective XOR Lemmas

__
TR98-042
| 27th July 1998
__

Pavel Pudlak#### A Note On the Use of Determinant for Proving Lower Bounds on the Size of Linear Circuits

Comments: 1

__
TR16-032
| 10th March 2016
__

Roei Tell#### A Note on Tolerant Testing with One-Sided Error

__
TR04-118
| 21st December 2004
__

Marek Karpinski, Yakov Nekrich#### A Note on Traversing Skew Merkle Trees

__
TR96-023
| 21st March 1996
__

Eric Allender#### A Note on Uniform Circuit Lower Bounds for the Counting Hierarchy

Comments: 1

__
TR07-016
| 13th February 2007
__

Prasad Raghavendra#### A Note on Yekhanin's Locally Decodable Codes

Revisions: 1

__
TR16-060
| 15th April 2016
__

Henry Yuen#### A parallel repetition theorem for all entangled games

__
TR09-027
| 2nd April 2009
__

Iftach Haitner#### A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 2

__
TR20-120
| 12th August 2020
__

Justin Holmgren, Ran Raz#### A Parallel Repetition Theorem for the GHZ Game

__
TR21-101
| 13th July 2021
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

__
TR10-019
| 19th February 2010
__

Andrew Drucker#### A PCP Characterization of AM

__
TR14-084
| 12th June 2014
__

Luke Schaeffer#### A Physically Universal Cellular Automaton

__
TR20-041
| 29th March 2020
__

Mrinal Kumar, Ben Lee Volk#### A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

Revisions: 2

__
TR17-026
| 17th February 2017
__

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

__
TR00-064
| 29th August 2000
__

Klaus Jansen, Marek Karpinski, Andrzej Lingas#### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

__
TR02-041
| 2nd July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon#### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

__
TR02-044
| 16th July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### A Polynomial Time Approximation Scheme for Subdense MAX-CUT

__
TR10-088
| 17th May 2010
__

Jiri Sima, Stanislav Zak#### A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Revisions: 2
,
Comments: 3

__
TR04-038
| 27th April 2004
__

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann#### A Polynomial Time Learner for a Subclass of Regular Patterns

__
TR00-079
| 12th September 2000
__

Mark Jerrum, Eric Vigoda#### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

__
TR09-078
| 16th September 2009
__

Falk Unger#### A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

__
TR98-051
| 20th July 1998
__

Petr Savicky#### A probabilistic nonequivalence test for syntactic (1,+k)-branching programs

__
TR05-103
| 17th August 2005
__

Leonid Gurvits#### A proof of hyperbolic van der Waerden conjecture : the right generalization is the ultimate simplification

__
TR22-168
| 23rd November 2022
__

Zubayir Kazi#### A Proof of the Generalized Union-Closed Set Conjecture assuming the Union-Closed Set Conjecture

Revisions: 1

__
TR18-047
| 7th March 2018
__

Shachar Lovett#### A proof of the GM-MDS conjecture

Revisions: 1

__
TR04-063
| 23rd July 2004
__

Yehuda Lindell, Benny Pinkas#### A Proof of Yao's Protocol for Secure Two-Party Computation

Revisions: 1

__
TR17-163
| 2nd November 2017
__

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

__
TR96-065
| 13th December 1996
__

Miklos Ajtai, Cynthia Dwork#### A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1
,
Comments: 1

__
TR19-170
| 27th November 2019
__

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk#### A Quadratic Lower Bound for Algebraic Branching Programs

Revisions: 3

__
TR17-028
| 17th February 2017
__

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

Revisions: 1

__
TR03-086
| 1st December 2003
__

Amos Beimel, Tal Malkin#### A Quantitative Approach to Reductions in Secure Computation

__
TR19-061
| 16th April 2019
__

Scott Aaronson, Daniel Grier, Luke Schaeffer#### A Quantum Query Complexity Trichotomy for Regular Languages

__
TR08-017
| 16th December 2007
__

Thomas Watson, Dieter van Melkebeek#### A Quantum Time-Space Lower Bound for the Counting Hierarchy

__
TR18-128
| 11th July 2018
__

Ewin Tang#### A quantum-inspired classical algorithm for recommendation systems

Revisions: 3

__
TR09-074
| 10th September 2009
__

Suguru Tamaki, Yuichi Yoshida#### A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

__
TR05-156
| 13th December 2005
__

Jonathan A. Kelner, Daniel A. Spielman#### A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version)

__
TR05-107
| 28th September 2005
__

Avi Wigderson, David Xiao#### A Randomness-Efficient Sampler for Matrix-valued Functions and Applications

Revisions: 1

__
TR12-124
| 29th September 2012
__

Massimo Lauria#### A rank lower bound for cutting planes proofs of Ramsey Theorem

__
TR05-035
| 24th March 2005
__

Christian Glaßer, Stephen Travers, Klaus W. Wagner#### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

__
TR17-027
| 16th February 2017
__

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

Revisions: 1

__
TR13-156
| 15th November 2013
__

Jan Krajicek#### A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

Revisions: 2

__
TR21-134
| 19th August 2021
__

Siddharth Bhaskar#### A refinement of the Meyer-McCreight Union Theorem

__
TR21-089
| 25th June 2021
__

Hanlin Ren, Rahul Santhanam#### A Relativization Perspective on Meta-Complexity

__
TR04-006
| 6th January 2004
__

Günter Hotz#### A remark on nondecidabilities of the initial value problem of ODEs

__
TR12-005
| 13th January 2012
__

Periklis Papakonstantinou, Guang Yang#### A remark on one-wayness versus pseudorandomness

__
TR20-046
| 13th April 2020
__

Srikanth Srinivasan#### A Robust Version of Heged\H{u}s's Lemma, with Applications

__
TR97-020
| 15th May 1997
__

Oded Goldreich#### A Sample of Samplers -- A Computational Perspective on Sampling (survey).

__
TR17-166
| 3rd November 2017
__

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

__
TR12-071
| 29th May 2012
__

Kazuhisa Seto, Suguru Tamaki#### A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

__
TR16-100
| 27th June 2016
__

Suguru Tamaki#### A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

__
TR15-136
| 28th July 2015
__

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

__
TR01-024
| 1st March 2001
__

Stephen Cook, Antonina Kolokolova#### A second-order system for polynomial-time reasoning based on Graedel's theorem

__
TR16-149
| 23rd September 2016
__

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev#### A security analysis of Probabilistically Checkable Proofs

Comments: 1

__
TR00-027
| 11th April 2000
__

Pavol Duris, Juraj Hromkovic, Katsushi Inoue#### A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition

__
TR10-060
| 5th April 2010
__

Dmytro Gavinsky, Alexander A. Sherstov#### A Separation of NP and coNP in Multiparty Communication Complexity

__
TR22-089
| 18th June 2022
__

Ilario Bonacina, Neil Thapen#### A separation of PLS from PPP

__
TR98-045
| 17th July 1998
__

Detlef Sieling#### A Separation of Syntactic and Nonsyntactic (1,+k)-Branching Programs

__
TR19-181
| 9th December 2019
__

Michal Koucky, Vojtech Rodl, Navid Talebanfard#### A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm

Revisions: 1

__
TR13-017
| 23rd January 2013
__

Pratik Worah#### A Short Excursion into Semi-Algebraic Hierarchies

__
TR13-176
| 8th December 2013
__

Daniel Kane, Osamu Watanabe#### A Short Implicant of CNFs with Relatively Many Satisfying Assignments

Revisions: 1
,
Comments: 1

__
TR13-012
| 16th January 2013
__

Hasan Abasi, Nader Bshouty#### A Simple Algorithm for Undirected Hamiltonicity

__
TR06-121
| 14th September 2006
__

Charanjit Jutla#### A Simple Biased Distribution for Dinur's Construction

__
TR08-093
| 1st October 2008
__

Cristopher Moore, Alexander Russell#### A simple constant-probability RP reduction from NP to Parity P

__
TR00-030
| 31st May 2000
__

#### A Simple Model for Neural Computation with Firing Rates and Firing Correlations

__
TR08-081
| 11th September 2008
__

Alexander Razborov#### A simple proof of Bazzi's theorem

__
TR15-080
| 7th May 2015
__

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

__
TR19-131
| 11th September 2019
__

Lieuwe Vinkhuijzen, André Deutz#### A Simple Proof of Vyalyi's Theorem and some Generalizations

__
TR14-075
| 16th May 2014
__

Holger Dell#### A simple proof that AND-compression of NP-complete problems is hard

Revisions: 3

__
TR22-007
| 14th January 2022
__

Halley Goldberg, Valentine Kabanets#### A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information

__
TR07-114
| 28th September 2007
__

Jakob Nordström#### A Simplified Way of Proving Trade-off Results for Resolution

__
TR12-053
| 30th April 2012
__

Ankur Moitra#### A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

__
TR09-047
| 20th April 2009
__

Eli Ben-Sasson, Jakob Nordström#### A Space Hierarchy for k-DNF Resolution

Comments: 1

__
TR18-202
| 1st December 2018
__

Xinyu Wu#### A stochastic calculus approach to the oracle separation of BQP and PH

__
TR18-088
| 24th April 2018
__

Ilya Volkovich#### A story of AM and Unique-SAT

Revisions: 1

__
TR10-150
| 19th September 2010
__

Bjørn Kjos-Hanssen#### A strong law of computationally weak subsets

__
TR10-141
| 18th September 2010 (removed)
__

Ran Raz#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.

__
TR10-142
| 18th September 2010
__

Ran Raz, Ricky Rosen#### A Strong Parallel Repetition Theorem for Projection Games on Expanders

__
TR20-124
| 3rd August 2020
__

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu#### A Strong XOR Lemma for Randomized Query Complexity

__
TR20-154
| 10th October 2020
__

Marcel Dall'Agnol, Tom Gur, Oded Lachish#### A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

__
TR13-133
| 23rd September 2013
__

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland#### A Structured View on Weighted Counting with Relations to Quantum Computation and Applications

Revisions: 2

__
TR95-060
| 21st November 1995
__

Nader Bshouty#### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

__
TR97-050
| 27th October 1997
__

Stanislav Zak#### A subexponential lower bound for branching programs restricted with regard to some semantic aspects

__
TR19-091
| 7th July 2019
__

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

__
TR15-108
| 30th June 2015
__

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

__
TR13-091
| 17th June 2013
__

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi#### A super-polynomial lower bound for regular arithmetic formulas.

__
TR21-176
| 30th November 2021
__

Theodoros Papamakarios#### A super-polynomial separation between resolution and cut-free sequent calculus

__
TR20-028
| 27th February 2020
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits

__
TR17-001
| 6th January 2017
__

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

__
TR07-099
| 30th September 2007
__

Dieter van Melkebeek#### A Survey of Lower Bounds for Satisfiability and Related Problems

__
TR20-086
| 5th June 2020
__

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi#### A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

__
TR15-063
| 15th April 2015
__

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

Revisions: 1

__
TR12-051
| 25th April 2012
__

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan#### A Tail Bound for Read-k Families of Functions

__
TR10-145
| 21st September 2010
__

Ron Rothblum#### A Taxonomy of Enhanced Trapdoor Permutations

__
TR09-075
| 17th September 2009
__

Oded Goldreich, Brendan Juba, Madhu Sudan#### A Theory of Goal-Oriented Communication

Revisions: 1
,
Comments: 1

__
TR98-034
| 23rd June 1998
__

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan#### A tight characterization of NP with 3 query PCPs

__
TR18-119
| 21st June 2018
__

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang#### A Tight Lower Bound for Entropy Flattening

Revisions: 1

__
TR20-071
| 4th May 2020
__

Iftach Haitner, Yonatan Karidi-Heller#### A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip

Revisions: 1

__
TR14-027
| 21st February 2014
__

Andris Ambainis, Krisjanis Prusis#### A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

Revisions: 1

__
TR19-049
| 2nd April 2019
__

Itay Berman, Iftach Haitner, Eliad Tsfadia#### A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments

Revisions: 2

__
TR11-086
| 2nd June 2011
__

Masaki Yamamoto#### A tighter lower bound on the circuit size of the hardest Boolean functions

__
TR17-020
| 12th February 2017
__

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

__
TR04-073
| 9th July 2004
__

Henning Fernau#### A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set

__
TR14-137
| 24th October 2014
__

Neil Thapen#### A trade-off between length and width in resolution

__
TR03-075
| 7th September 2003
__

Agostino Capponi#### A tutorial on the Deterministic two-party Communication Complexity

__
TR01-016
| 22nd December 2000
__

Ran Canetti#### A unified framework for analyzing security of protocols

Revisions: 6

__
TR10-161
| 25th October 2010
__

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira#### A Unified Framework for Testing Linear-Invariant Properties

__
TR16-186
| 19th November 2016
__

Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh#### A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation

__
TR17-019
| 8th February 2017
__

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

Revisions: 2

__
TR13-101
| 12th July 2013
__

Colin Jia Zheng, Salil Vadhan#### A Uniform Min-Max Theorem with Applications in Cryptography

Revisions: 2

__
TR14-103
| 8th August 2014
__

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis#### A Unifying Hierarchy of Valuations with Complements and Substitutes

__
TR05-078
| 25th May 2005
__

Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz#### A Verifiable Partial Key Escrow, Based on McCurley Encryption Scheme

Revisions: 1

__
TR02-033
| 11th June 2002
__

Beate Bollig#### A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs

__
TR17-057
| 7th April 2017
__

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

__
TR17-139
| 18th September 2017
__

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

Revisions: 1

__
TR13-029
| 19th February 2013
__

C. Seshadhri, Deeparnab Chakrabarty#### A {\huge ${o(n)}$} monotonicity tester for Boolean functions over the hypercube

Revisions: 1

__
TR13-030
| 20th February 2013
__

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan#### Absolutely Sound Testing of Lifted Codes

__
TR18-209
| 8th December 2018
__

Emanuele Viola#### AC0 unpredictability

__
TR19-018
| 18th February 2019
__

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal#### AC0[p] Lower Bounds against MCSP via the Coin Problem

__
TR11-050
| 11th April 2011
__

Claus-Peter Schnorr#### Accelerated Slide- and LLL-Reduction

Revisions: 7

__
TR17-085
| 4th May 2017
__

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

__
TR07-088
| 7th September 2007
__

Elad Hazan, C. Seshadhri#### Adaptive Algorithms for Online Decision Problems

Revisions: 1

__
TR18-005
| 9th January 2018
__

C. Seshadhri, Deeparnab Chakrabarty#### Adaptive Boolean Monotonicity Testing in Total Influence Time

__
TR06-042
| 16th March 2006
__

Amit Deshpande, Santosh Vempala#### Adaptive Sampling and Fast Low-Rank Matrix Approximation

__
TR96-051
| 1st October 1996
__

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang#### Addition in $\log_2{n}$ + O(1)$ Steps on Average: A Simple Analysis

__
TR15-123
| 31st July 2015
__

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

__
TR14-044
| 2nd April 2014
__

Daniel Dewey#### Additively efficient universal computers

__
TR18-163
| 18th September 2018
__

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov#### Adventures in Monotone Complexity and TFNP

__
TR11-008
| 27th January 2011
__

Scott Aaronson, Andrew Drucker#### Advice Coins for Classical and Quantum Computation

__
TR11-120
| 6th September 2011
__

Thomas Watson#### Advice Lower Bounds for the Dense Model Theorem

Revisions: 1

__
TR10-044
| 12th March 2010
__

Eli Ben-Sasson, Swastik Kopparty#### Affine Dispersers from Subspace Polynomials

__
TR21-137
| 14th September 2021
__

Xuangui Huang, Peter Ivanov, Emanuele Viola#### Affine extractors and AC0-Parity

Revisions: 1

__
TR21-075
| 4th June 2021
__

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao#### Affine Extractors for Almost Logarithmic Entropy

__
TR14-010
| 23rd January 2014
__

Jean Bourgain, Zeev Dvir, Ethan Leeman#### Affine extractors over large fields with exponential error

__
TR11-061
| 18th April 2011
__

Neeraj Kayal#### Affine projections of polynomials

Revisions: 1

__
TR01-035
| 15th April 2001
__

Amir Shpilka#### Affine Projections of Symmetric Polynomials

__
TR16-040
| 16th March 2016
__

Baris Aydinlioglu, Eric Bach#### Affine Relativization: Unifying the Algebrization and Relativization Barriers

Revisions: 3

__
TR15-179
| 10th November 2015
__

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

__
TR15-009
| 16th January 2015
__

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

Revisions: 1

__
TR04-028
| 19th March 2004
__

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker#### Aggregates with Component Size One Characterize Polynomial Space

__
TR10-185
| 2nd December 2010
__

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu#### Agnostic Learning of Monomials by Halfspaces is Hard

__
TR94-020
| 12th December 1994
__

#### Agnostic PAC-Learning of Functions on Analog Neural Nets

__
TR19-112
| 1st September 2019
__

Yotam Dikstein, Irit Dinur#### Agreement testing theorems on layered set systems

__
TR17-181
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Agreement tests on graphs and hypergraphs

Revisions: 1

__
TR00-013
| 14th February 2000
__

Daniel Král#### Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization

__
TR15-172
| 3rd November 2015
__

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

Revisions: 1

__
TR20-031
| 10th March 2020
__

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh#### Algebraic Branching Programs, Border Complexity, and Tangent Spaces

__
TR18-019
| 28th January 2018
__

Zeyu Guo, Nitin Saxena, Amit Sinhababu#### Algebraic dependencies and PSPACE algorithms in approximative complexity

Revisions: 1

__
TR14-130
| 17th October 2014
__

Ankit Gupta#### Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties

Revisions: 1

__
TR20-081
| 21st May 2020
__

Robert Andrews#### Algebraic Hardness versus Randomness in Low Characteristic

__
TR11-022
| 14th February 2011
__

Malte Beecken, Johannes Mittmann, Nitin Saxena#### Algebraic Independence and Blackbox Identity Testing

__
TR12-014
| 20th February 2012
__

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner#### Algebraic Independence in Positive Characteristic -- A p-Adic Calculus

__
TR07-022
| 20th February 2007
__

Rafail Ostrovsky, William Skeith#### Algebraic Lower Bounds for Computing on Encrypted Data

__
TR16-101
| 1st July 2016
__

Toniann Pitassi, Iddo Tzameret#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

__
TR01-011
| 21st January 2001
__

Dima Grigoriev, Edward Hirsch#### Algebraic proof systems over formulas

__
TR10-097
| 16th June 2010
__

Iddo Tzameret#### Algebraic Proofs over Noncommutative Formulas

Revisions: 1

__
TR07-111
| 1st November 2007
__

Tali Kaufman, Madhu Sudan#### Algebraic Property Testing: The Role of Invariance

__
TR05-132
| 8th November 2005
__

Venkatesan Guruswami#### Algebraic-geometric generalizations of the Parvaresh-Vardy codes

__
TR08-005
| 15th January 2008
__

Scott Aaronson, Avi Wigderson#### Algebrization: A New Barrier in Complexity Theory

__
TR08-039
| 7th April 2008
__

Oded Goldreich, Dana Ron#### Algorithmic Aspects of Property Testing in the Dense Graphs Model

__
TR11-128
| 21st September 2011
__

Michael Elberfeld, Andreas Jakoby, Till Tantau#### Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth

__
TR09-147
| 30th December 2009
__

Stephan Kreutzer#### Algorithmic Meta-Theorems

__
TR18-010
| 14th January 2018
__

Alexander A. Sherstov#### Algorithmic polynomials

__
TR21-163
| 19th November 2021
__

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Algorithmizing the Multiplicity Schwartz-Zippel Lemma

Revisions: 1

__
TR21-171
| 2nd December 2021
__

Bruno Pasqualotto Cavalar, Zhenjian Lu#### Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

__
TR20-018
| 18th February 2020
__

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira#### Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

__
TR10-073
| 21st April 2010
__

Neeraj Kayal#### Algorithms for Arithmetic Circuits

__
TR05-033
| 5th March 2005
__

Martin Furer, Shiva Prasad Kasiviswanathan#### Algorithms for Counting 2-SAT Solutions and Colorings with Applications

__
TR13-123
| 6th September 2013
__

Joshua Grochow, Youming Qiao#### Algorithms for group isomorphism via group extensions and cohomology

__
TR07-059
| 6th July 2007
__

Shankar Kalyanaraman, Chris Umans#### Algorithms for Playing Games with Limited Randomness

__
TR01-012
| 4th January 2001
__

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov#### Algorithms for SAT and Upper Bounds on Their Complexity

__
TR03-072
| 15th September 2003
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Algorithms for SAT based on search in Hamming balls

__
TR10-122
| 18th July 2010
__

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller#### Algorithms for Testing Monomials in Multivariate Polynomials

__
TR11-124
| 15th September 2011
__

Nader Bshouty, Hanna Mazzawi#### Algorithms for the Coin Weighing Problems with the Presence of Noise

__
TR16-008
| 26th January 2016
__

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova#### Algorithms from Natural Lower Bounds

__
TR13-117
| 1st September 2013
__

Igor Oliveira#### Algorithms versus Circuit Lower Bounds

__
TR16-168
| 2nd November 2016
__

Eric Blais, Clement Canonne, Tom Gur#### Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.)

Revisions: 1

__
TR17-150
| 26th September 2017
__

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

Revisions: 2

__
TR06-122
| 20th September 2006
__

Noam Livne#### All Natural NPC Problems Have Average-Case Complete Versions

Revisions: 1

__
TR97-040
| 17th September 1997
__

Dorit Dor, Shay Halperin, Uri Zwick#### All Pairs Almost Shortest Paths

__
TR00-060
| 17th August 2000
__

Uri Zwick#### All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication

__
TR99-004
| 3rd February 1999
__

Valentine Kabanets#### Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

__
TR02-048
| 31st July 2002
__

Noga Alon, Oded Goldreich, Yishay Mansour#### Almost $k$-wise independence versus $k$-wise independence

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 1

__
TR05-010
| 8th December 2004
__

Olivier Powell#### Almost Completeness in Small Complexity Classes

__
TR16-187
| 21st November 2016
__

morris yau#### Almost Cubic Bound for Depth Three Circuits in VP

Revisions: 3

__
TR07-012
| 22nd January 2007
__

Shachar Lovett, Sasha Sodin#### Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

__
TR07-086
| 7th September 2007
__

Venkatesan Guruswami, James R. Lee, Alexander Razborov#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

__
TR11-049
| 9th April 2011
__

Noga Alon, Shachar Lovett#### Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

__
TR09-120
| 18th November 2009
__

Charanjit Jutla#### Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

__
TR10-183
| 29th November 2010
__

Raghu Meka#### Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Revisions: 2

__
TR21-007
| 14th January 2021
__

Sai Sandeep#### Almost Optimal Inapproximability of Multidimensional Packing Problems

__
TR21-027
| 24th February 2021
__

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu#### Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

__
TR19-156
| 7th November 2019
__

Nader Bshouty#### Almost Optimal Testers for Concise Representations

__
TR03-066
| 2nd September 2003
__

Daniele Micciancio#### Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

__
TR15-200
| 4th December 2015
__

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

Revisions: 1

__
TR19-178
| 5th December 2019
__

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov#### Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

__
TR20-150
| 7th October 2020
__

Lijie Chen, Xin Lyu, Ryan Williams#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

__
TR16-195
| 19th November 2016
__

Pasin Manurangsi#### Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Revisions: 1

__
TR17-192
| 15th December 2017
__

Krishnamoorthy Dinesh, Jayalal Sarma#### Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps

Revisions: 1

__
TR14-012
| 27th January 2014
__

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz#### AM with Multiple Merlins

Revisions: 1

__
TR21-035
| 13th March 2021
__

Robert Robere, Jeroen Zuiddam#### Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms

Revisions: 1

__
TR16-054
| 11th April 2016
__

Omri Weinstein, Huacheng Yu#### Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication

__
TR15-158
| 27th September 2015
__

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

__
TR15-031
| 2nd March 2015
__

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

Revisions: 1

__
TR18-058
| 5th April 2018
__

Thomas Watson#### Amplification with One NP Oracle Query

Revisions: 1

__
TR08-038
| 4th April 2008
__

Eric Allender, Michal Koucky#### Amplifying Lower Bounds by Means of Self-Reducibility

Revisions: 2

__
| 22nd June 2015 (removed)
__

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

__
TR15-102
| 22nd June 2015
__

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

__
TR15-016
| 16th January 2015
__

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

Revisions: 1

__
TR16-126
| 8th August 2016
__

Subhash Khot, Igor Shinkar#### An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness

__
TR19-144
| 29th October 2019
__

Young Ko, Omri Weinstein#### An Adaptive Step Toward the Multiphase Conjecture

Revisions: 1

__
TR17-029
| 18th February 2017
__

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

Revisions: 1

__
TR11-157
| 25th November 2011
__

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi#### An additive combinatorics approach to the log-rank conjecture in communication complexity

Revisions: 1

__
TR96-010
| 9th February 1996
__

Christoph Meinel, Anna Slobodova#### An Adequate Reducibility Concept for Problems Defined in Terms of Ordered Binary Decision Diagrams

Revisions: 1

__
TR11-172
| 20th December 2011
__

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg#### An Algorithmic Characterization of Multi-Dimensional Mechanisms

__
TR16-143
| 15th September 2016
__

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan#### An Almost Cubic Lower Bound for $\Sigma\Pi\Sigma$ Circuits Computing a Polynomial in VP

__
TR16-006
| 22nd January 2016
__

Neeraj Kayal, Chandan Saha, Sébastien Tavenas#### An almost Cubic Lower Bound for Depth Three Arithmetic Circuits

Revisions: 2

__
TR08-108
| 19th November 2008
__

Nitin Saxena, C. Seshadhri#### An Almost Optimal Rank Bound for Depth-3 Identities

__
TR17-124
| 6th August 2017
__

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

Revisions: 2

__
TR14-114
| 27th August 2014
__

Roei Tell#### An Alternative Proof of an $\Omega(k)$ Lower Bound for Testing $k$-linear Boolean Functions

__
TR10-096
| 16th June 2010
__

Dana Moshkovitz#### An Alternative Proof of The Schwartz-Zippel Lemma

Revisions: 1

__
TR00-018
| 16th February 2000
__

Oliver Kullmann#### An application of matroid theory to the SAT problem

__
TR04-110
| 24th November 2004
__

Tomoyuki Yamakami, Harumichi Nishimura#### An Application of Quantum Finite Automata to Interactive Proof Systems

__
TR09-085
| 14th September 2009
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### An Approach to characterize the Regular Languages in TC0 with Linear Wires

Revisions: 1

__
TR14-030
| 5th March 2014
__

Dana Moshkovitz#### An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing

__
TR97-017
| 5th May 1997
__

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky#### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

__
TR04-048
| 21st April 2004
__

André Lanka, Andreas Goerdt#### An approximation hardness result for bipartite Clique

__
TR15-065
| 18th April 2015
__

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

__
TR16-041
| 17th March 2016
__

Johan Håstad#### An average-case depth hierarchy theorem for higher depth

__
TR17-173
| 6th November 2017
__

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

__
TR98-069
| 7th December 1998
__

Rüdiger Reischuk, Thomas Zeugmann#### An Average-Case Optimal One-Variable Pattern Language Learner

__
TR21-041
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira#### An Efficient Coding Theorem via Probabilistic Representations and its Applications

__
TR95-038
| 2nd July 1995
__

Joe Kilian, Erez Petrank#### An Efficient Non-Interactive Zero-Knowledge Proof System for NP with General Assumptions

__
TR17-129
| 27th August 2017
__

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

Revisions: 8

__
TR06-119
| 13th September 2006
__

Noga Alon, Oded Schwartz, Asaf Shapira#### An Elementary Construction of Constant-Degree Expanders

__
TR11-026
| 27th February 2011
__

Evgeny Demenkov, Alexander Kulikov#### An Elementary Proof of $3n-o(n)$ Lower Bound on the Circuit Complexity of Affine Dispersers

__
TR10-182
| 26th November 2010
__

Shachar Lovett#### An elementary proof of anti-concentration of polynomials in Gaussian variables

__
TR10-091
| 14th May 2010
__

Nikolay Vereshchagin#### An Encoding Invariant Version of Polynomial Time
Computable Distributions

__
TR18-008
| 10th January 2018
__

Tom Gur, Igor Shinkar#### An Entropy Lower Bound for Non-Malleable Extractors

__
TR14-165
| 3rd December 2014
__

Venkatesan Guruswami, Ameya Velingker#### An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets

__
TR01-083
| 29th October 2001
__

Nikolay Vereshchagin#### An enumerable undecidable set with low prefix complexity: a simplified proof

Revisions: 1

__
TR03-013
| 7th March 2003
__

Luca Trevisan#### An epsilon-Biased Generator in NC0

Comments: 1

__
TR12-127
| 3rd October 2012
__

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari#### An Explicit VC-Theorem for Low-Degree Polynomials

__
TR07-007
| 17th January 2007
__

Jan Krajicek#### An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

__
TR12-098
| 3rd August 2012
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin

Revisions: 3

__
TR14-005
| 14th January 2014
__

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan#### An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

__
TR15-109
| 1st July 2015
__

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

__
TR12-081
| 26th June 2012
__

Neeraj Kayal#### An exponential lower bound for the sum of powers of bounded degree polynomials

Revisions: 1

__
TR95-057
| 24th November 1995
__

Dima Grigoriev, Marek Karpinski, A. C. Yao#### An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

__
TR19-005
| 16th January 2019
__

Omar Alrabiah, Venkatesan Guruswami#### An Exponential Lower Bound on the Sub-Packetization of MSR Codes

Revisions: 1

__
TR94-018
| 12th December 1994
__

Jan Krajicek, Pavel Pudlak, Alan Woods#### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

__
TR18-083
| 25th April 2018
__

Tom Gur, Ron D. Rothblum, Yang P. Liu#### An Exponential Separation Between MA and AM Proofs of Proximity

Revisions: 2

__
TR01-056
| 6th August 2001
__

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart#### An Exponential Separation between Regular and General Resolution

__
TR15-173
| 29th October 2015
__

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

__
TR07-046
| 23rd April 2007
__

Philipp Hertel#### An Exponential Time/Space Speedup For Resolution

Comments: 1

__
TR07-034
| 29th March 2007
__

Anup Rao#### An Exposition of Bourgain's 2-Source Extractor

__
TR12-029
| 3rd April 2012
__

Shachar Lovett#### An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem

__
TR05-067
| 28th June 2005
__

Zeev Dvir, Amir Shpilka#### An Improved Analysis of Mergers

__
TR06-107
| 26th August 2006
__

Arkadev Chattopadhyay#### An improved bound on correlation between polynomials over Z_m and MOD_q

Revisions: 1

__
TR15-117
| 21st July 2015
__

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

Revisions: 1

__
TR20-182
| 3rd December 2020
__

Zander Kelley#### An Improved Derandomization of the Switching Lemma

Revisions: 1

__
TR13-150
| 4th November 2013
__

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh#### An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

__
TR17-030
| 15th February 2017
__

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

__
TR20-145
| 23rd September 2020
__

Andrew Drucker#### An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature

__
TR00-057
| 25th July 2000
__

Martin Sauerhoff#### An Improved Hierarchy Result for Partitioned BDDs

__
TR16-206
| 24th December 2016
__

Benjamin Rossman#### An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity

__
TR12-099
| 5th August 2012
__

Nikos Leonardos#### An improved lower bound for the randomized decision tree complexity of recursive majority

Revisions: 1

__
TR05-030
| 12th February 2005
__

Evgeny Dantsin, Alexander Wolpert#### An Improved Upper Bound for SAT

__
TR17-140
| 11th September 2017
__

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

__
TR07-117
| 8th November 2007
__

Edward Hirsch, Dmitry Itsykson#### An infinitely-often one-way function based on an average-case assumption

__
TR12-131
| 18th October 2012
__

Mark Braverman, Ankur Moitra#### An Information Complexity Approach to Extended Formulations

Revisions: 1

__
TR14-047
| 8th April 2014
__

Mark Braverman, Omri Weinstein#### An Interactive Information Odometer with Applications

Revisions: 1

__
TR09-144
| 24th December 2009
__

Prahladh Harsha, Adam Klivans, Raghu Meka#### An Invariance Principle for Polytopes

__
TR22-126
| 12th September 2022
__

Andrei Krokhin, Jakub Opršal#### An Invitation to the Promise Constraint Satisfaction Problem

__
TR06-011
| 2nd January 2006
__

Yijia Chen, Martin Grohe#### An Isomorphism between Subexponential and Parameterized Complexity Theory

__
TR96-002
| 10th January 1996
__

Manindra Agrawal, Eric Allender#### An Isomorphism Theorem for Circuit Complexity

__
TR04-114
| 21st November 2004
__

Vladimir Trifonov#### An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity

__
TR06-050
| 18th April 2006
__

Alexander Razborov, Sergey Yekhanin#### An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval

__
TR18-043
| 22nd February 2018
__

Andrei Romashchenko, Marius Zimand#### An operational characterization of mutual information in algorithmic information theory

Revisions: 2

__
TR22-044
| 4th April 2022
__

Meghal Gupta, Naren Manoj#### An Optimal Algorithm for Certifying Monotone Functions

__
TR13-062
| 18th April 2013
__

C. Seshadhri, Deeparnab Chakrabarty#### An optimal lower bound for monotonicity testing over hypergrids

__
TR10-140
| 17th September 2010
__

Amit Chakrabarti, Oded Regev#### An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

__
TR03-070
| 19th August 2003
__

Amit Chakrabarti, Oded Regev#### An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

__
TR20-128
| 3rd September 2020
__

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu#### An Optimal Separation of Randomized and Quantum Query Complexity

Revisions: 1

__
TR20-123
| 17th August 2020
__

Nader Bshouty#### An Optimal Tester for k-Linear

__
TR96-020
| 6th March 1996
__

C.P. Schnorr, Carsten Rössner#### An Optimal, Stable Continued Fraction Algorithm for Arbitrary Dimension

__
TR15-130
| 11th August 2015
__

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

__
TR18-166
| 18th September 2018
__

Tayfun Pay, James Cox#### An overview of some semantic and syntactic complexity classes

__
TR15-033
| 6th March 2015
__

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

Revisions: 1

__
TR06-056
| 27th April 2006
__

Salil Vadhan#### An Unconditional Study of Computational Zero Knowledge

__
TR95-010
| 16th February 1995
__

Pavel Pudlak, Jiri Sgall#### An Upper Bound for a Communication Game Related to Time-Space Tradeoffs

__
TR18-168
| 25th September 2018
__

Alex Samorodnitsky#### An upper bound on $\ell_q$ norms of noisy functions

Revisions: 1

__
TR01-079
| 6th September 2001
__

Michele Zito#### An Upper Bound on the Space Complexity of Random Formulae in Resolution

__
TR18-131
| 17th July 2018
__

Gautam Kamath, Christos Tzamos#### Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing

__
TR97-052
| 11th November 1997
__

Eduardo D. Sontag#### Analog Neural Nets with Gaussian or other Common Noise Distributions cannot Recognize Arbitrary Regular Languages

__
TR95-025
| 8th May 1995
__

Günter Hotz, Gero Vierke, Bjoern Schieffer#### Analytic Machines

Comments: 1

__
TR05-025
| 20th February 2005
__

Zeev Dvir, Ran Raz#### Analyzing Linear Mergers

__
TR22-004
| 3rd January 2022
__

Silas Richelson, Sourya Roy#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

__
TR19-046
| 1st April 2019
__

Akash Kumar, C. Seshadhri, Andrew Stolman#### andom walks and forbidden minors II: A $\poly(d\eps^{-1})$-query tester for minor-closed properties of bounded degree graphs

Revisions: 1

__
TR12-022
| 14th March 2012
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler#### Annotations in Data Streams

Revisions: 1

__
TR97-045
| 29th September 1997
__

Oded Goldreich, David Zuckerman#### Another proof that BPP subseteq PH (and more).

Comments: 1

__
TR06-143
| 15th November 2006
__

Frank Neumann, Carsten Witt#### Ant Colony Optimization and the Minimum Spanning Tree Problem

__
TR18-194
| 15th November 2018
__

Amir Yehudayoff#### Anti-concentration in most directions

Revisions: 5

__
TR13-147
| 25th October 2013
__

Adam Bouland, Scott Aaronson#### Any Beamsplitter Generates Universal Quantum Linear Optics

Revisions: 3

__
TR14-061
| 21st April 2014
__

Raghav Kulkarni, Youming Qiao, Xiaoming Sun#### Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

__
TR21-156
| 10th November 2021
__

Boris Bukh, Karthik C. S., Bhargav Narayanan#### Applications of Random Algebraic Constructions to Hardness of Approximation

__
TR00-052
| 3rd July 2000
__

Beate Bollig, Ingo Wegener#### Approximability and Nonapproximability by Binary Decision Diagrams

__
TR21-063
| 3rd May 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Approximability of all finite CSPs in the dynamic streaming setting

Revisions: 3

__
TR00-091
| 21st December 2000
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximability of Dense Instances of NEAREST CODEWORD Problem

__
TR03-056
| 29th July 2003
__

Piotr Berman, Marek Karpinski#### Approximability of Hypergraph Minimum Bisection

__
TR06-045
| 13th March 2006
__

Jan Arpe, Bodo Manthey#### Approximability of Minimum AND-Circuits

Revisions: 1

__
TR14-065
| 2nd May 2014
__

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska#### Approximate Counting of Matchings in $(3,3)$-Hypergraphs

__
TR02-031
| 30th April 2002
__

Vikraman Arvind, Venkatesh Raman#### Approximate Counting small subgraphs of bounded treewidth and related problems

Revisions: 1

__
TR16-121
| 4th August 2016
__

Mark Bun, Justin Thaler#### Approximate Degree and the Complexity of Depth Three Circuits

Revisions: 1

__
TR18-197
| 22nd November 2018
__

Andrej Bogdanov#### Approximate degree of AND via Fourier analysis

Revisions: 1

__
TR19-082
| 2nd June 2019
__

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson#### Approximate degree, secret sharing, and concentration phenomena

__
TR19-085
| 7th June 2019
__

Xuangui Huang, Emanuele Viola#### Approximate Degree-Weight and Indistinguishability

Revisions: 2

__
TR12-078
| 14th June 2012
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev#### Approximate Graph Isomorphism

__
TR20-167
| 9th November 2020
__

Venkatesan Guruswami, Sai Sandeep#### Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture

__
TR07-116
| 25th September 2007
__

Alexander A. Sherstov#### Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions

Comments: 1

__
TR14-046
| 8th April 2014
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

__
TR10-032
| 19th January 2010
__

Jack H. Lutz, Brad Shutters#### Approximate Self-Assembly of the Sierpinski Triangle

__
TR15-046
| 2nd April 2015
__

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

Comments: 1

__
TR11-171
| 15th December 2011
__

Piotr Indyk, Reut Levi, Ronitt Rubinfeld#### Approximating and Testing $k$-Histogram Distributions in Sub-linear time

Revisions: 1

__
TR05-073
| 14th July 2005
__

Oded Goldreich, Dana Ron#### Approximating Average Parameters of Graphs.

__
TR13-051
| 2nd April 2013
__

Eric Blais, Li-Yang Tan#### Approximating Boolean functions with depth-2 circuits

__
TR01-042
| 31st May 2001
__

Marek Karpinski#### Approximating Bounded Degree Instances of NP-Hard Problems

__
TR12-074
| 12th June 2012
__

Venkatesan Guruswami, Yuan Zhou#### Approximating Bounded Occurrence Ordering CSPs

__
TR06-007
| 23rd November 2005
__

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour#### Approximating Buy-at-Bulk $k$-Steiner trees

__
TR07-027
| 2nd February 2007
__

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt#### Approximating Covering Problems by Randomized Search Heuristics Using Multi-Objective Models

__
TR16-116
| 26th July 2016
__

Subhash Khot, Rishi Saket#### Approximating CSPs using LP Relaxation

__
TR98-048
| 6th July 1998
__

Irit Dinur, Guy Kindler, Shmuel Safra#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

__
TR97-004
| 19th February 1997
__

Marek Karpinski, Alexander Zelikovsky#### Approximating Dense Cases of Covering Problems

Comments: 1

__
TR02-018
| 22nd March 2002
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Approximating Huffman Codes in Parallel

__
TR00-072
| 14th July 2000
__

Peter Auer, Philip M. Long, Aravind Srinivasan#### Approximating Hyper-Rectangles: Learning and Pseudo-random Sets

__
TR22-149
| 7th November 2022
__

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma#### Approximating Iterated Multiplication of Stochastic Matrices in Small Space

__
TR22-008
| 14th January 2022
__

Gil Cohen, Dean Doron, Ori Sberlo#### Approximating Large Powers of Stochastic Matrices in Small Space

Comments: 1

__
TR10-132
| 18th August 2010
__

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson#### Approximating Linear Threshold Predicates

__
TR03-032
| 16th April 2003
__

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna#### Approximating Longest Directed Path

__
TR01-025
| 28th March 2001
__

Piotr Berman, Marek Karpinski#### Approximating Minimum Unsatisfiability of Linear Equations

__
TR10-124
| 18th July 2010
__

Zhixiang Chen, Bin Fu#### Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials

__
TR18-097
| 15th May 2018
__

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani#### Approximating Operator Norms via Generalized Krivine Rounding

__
TR01-038
| 14th May 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Approximating Schedules for Dynamic Graphs Efficiently

__
TR99-002
| 22nd January 1999
__

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

__
TR99-016
| 25th April 1999
__

Irit Dinur#### Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

__
TR13-023
| 6th February 2013
__

Alexander A. Sherstov#### Approximating the AND-OR Tree

__
TR14-092
| 22nd July 2014
__

Mark Braverman, Young Kun Ko, Omri Weinstein#### Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis

__
TR19-163
| 16th November 2019
__

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten#### Approximating the Distance to Monotonicity of Boolean Functions

Revisions: 1

__
TR05-084
| 31st July 2005
__

Mickey Brautbar, Alex Samorodnitsky#### Approximating the entropy of large alphabets

__
TR12-025
| 23rd March 2012
__

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin#### Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques

__
TR07-092
| 10th July 2007
__

Piotr Berman, Bhaskar DasGupta#### Approximating the Online Set Multicover Problems Via Randomized Winnowing

__
TR97-059
| 22nd December 1997
__

Jin-Yi Cai, Ajay Nerurkar#### Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

__
TR07-119
| 5th December 2007
__

Piotr Berman, Bhaskar DasGupta, Marek Karpinski#### Approximating Transitive Reductions for Directed Networks

__
TR06-063
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Approximation Algorithm for the Max k-CSP Problem

__
TR00-051
| 14th July 2000
__

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas#### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

__
TR05-034
| 5th April 2005
__

Luca Trevisan#### Approximation Algorithms for Unique Games

Revisions: 1
,
Comments: 1

__
TR06-101
| 22nd August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximation Complexity of Nondense Instances of MAX-CUT

__
TR96-030
| 31st March 1996
__

Meera Sitharam#### Approximation from linear spaces and applications to complexity

__
TR03-022
| 11th April 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

__
TR02-073
| 12th December 2002
__

Janka Chlebíková, Miroslav Chlebik#### Approximation Hardness for Small Occurrence Instances of NP-Hard Problem

__
TR01-026
| 3rd April 2001
__

Piotr Berman, Marek Karpinski#### Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

__
TR13-066
| 25th April 2013
__

Marek Karpinski, Richard Schmied#### Approximation Hardness of Graphic TSP on Cubic Graphs

__
TR03-049
| 25th June 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness of Short Symmetric Instances of MAX-3SAT

__
TR00-089
| 1st December 2000
__

Lars Engebretsen, Marek Karpinski#### Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

__
TR18-127
| 9th July 2018
__

Stasys Jukna, Hannes Seiwert#### Approximation Limitations of Tropical Circuits

__
TR00-058
| 1st August 2000
__

Martin Sauerhoff#### Approximation of Boolean Functions by Combinatorial Rectangles

__
TR06-124
| 25th September 2006
__

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Approximation of Global MAX-CSP Problems

__
TR12-110
| 4th September 2012
__

Siu On Chan#### Approximation Resistance from Pairwise Independent Subgroups

__
TR12-040
| 17th April 2012
__

Sangxia Huang#### Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity

__
TR08-009
| 7th December 2007
__

Per Austrin, Elchanan Mossel#### Approximation Resistant Predicates From Pairwise Independence

__
TR01-065
| 10th August 2001
__

Chandra Chekuri, Sanjeev Khanna#### Approximation Schemes for Preemptive Weighted Flow Time

__
TR06-074
| 24th April 2006
__

Shahar Dobzinski, Noam Nisan#### Approximations by Computationally-Efficient VCG-Based Mechanisms

__
TR99-011
| 14th April 1999
__

Matthias Krause, Petr Savicky, Ingo Wegener#### Approximations by OBDDs and the variable ordering problem

__
TR19-154
| 6th November 2019
__

Venkatesan Guruswami, Andrii Riazanov, Min Ye#### Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity

Revisions: 3

__
TR09-114
| 13th November 2009
__

Emanuele Viola#### Are all distributions easy?

__
TR15-160
| 30th September 2015
__

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

Revisions: 1

__
TR09-089
| 26th September 2009
__

Guy Rothblum, Salil Vadhan#### Are PCPs Inherent in Efficient Arguments?

__
TR15-152
| 16th September 2015
__

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

__
TR09-057
| 23rd June 2009
__

Yonatan Bilu, Nathan Linial#### Are stable instances easy?

__
TR15-145
| 5th September 2015
__

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

__
TR21-072
| 23rd May 2021
__

Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu#### Arithmetic Circuit Complexity of Division and Truncation

__
TR13-028
| 14th February 2013
__

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma#### Arithmetic Circuit Lower Bounds via MaxRank

__
TR09-026
| 17th February 2009
__

Vikraman Arvind, Pushkar Joglekar#### Arithmetic Circuit Size, Identity Testing, and Finite Automata

__
TR15-194
| 30th November 2015
__

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

Revisions: 1

__
TR08-048
| 8th April 2008
__

Meena Mahajan, B. V. Raghavendra Rao#### Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae

__
TR08-062
| 11th June 2008
__

Manindra Agrawal, V Vinay#### Arithmetic Circuits: A Chasm at Depth Four

__
TR13-026
| 11th February 2013
__

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi#### Arithmetic circuits: A chasm at depth three

Revisions: 1

__
TR99-008
| 19th March 1999
__

Eric Allender, Vikraman Arvind, Meena Mahajan#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

Revisions: 1
,
Comments: 1

__
TR15-061
| 14th April 2015
__

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

Revisions: 1

__
TR01-095
| 12th November 2001
__

Hubie Chen#### Arithmetic Versions of Constant Depth Circuit Complexity Classes

__
TR07-087
| 11th July 2007
__

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao#### Arithmetizing classes around NC^1 and L

__
TR09-055
| 10th June 2009
__

Venkatesan Chakaravarthy, Sambuddha Roy#### Arthur and Merlin as Oracles

__
TR97-054
| 17th November 1997
__

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin#### Arthur-Merlin Games in Boolean Decision Trees

__
TR13-020
| 2nd February 2013
__

Tom Gur, Ran Raz#### Arthur-Merlin Streaming Complexity

__
TR09-001
| 26th November 2008
__

Venkatesan Guruswami#### Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

__
TR13-105
| 29th July 2013
__

Raghu Meka, Avi Wigderson#### Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique

Revisions: 1

__
TR03-038
| 15th May 2003
__

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor#### Asymmetric k-center is log^*n-hard to Approximate

__
TR99-048
| 7th December 1999
__

Beate Bollig, Ingo Wegener#### Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems

__
TR95-026
| 7th June 1995
__

Claus-Peter Schnorr, Horst Helmut Hoerner#### Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction

__
TR98-076
| 13th November 1998
__

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon#### Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

__
TR12-056
| 1st May 2012
__

Rocco Servedio, Li-Yang Tan, Justin Thaler#### Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

Revisions: 1

__
TR20-064
| 2nd May 2020
__

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende#### Automating Algebraic Proof Systems is NP-Hard

Revisions: 2

__
TR20-049
| 17th April 2020
__

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi#### Automating Cutting Planes is NP-Hard

__
TR22-046
| 4th April 2022
__

Dmitry Itsykson, Artur Riazanov#### Automating OBDD proofs is NP-hard

__
TR20-105
| 14th July 2020
__

Zoë Bell#### Automating Regular or Ordered Resolution is NP-Hard

__
TR21-033
| 7th March 2021
__

Susanna de Rezende#### Automating Tree-Like Resolution in Time $n^{o(\log n)}$ Is ETH-Hard

__
TR13-188
| 13th December 2013
__

Christian Glaßer, Maximilian Witek#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

__
TR13-047
| 27th March 2013
__

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

__
TR16-012
| 21st January 2016
__

John Hitchcock, Hadi Shafei#### Autoreducibility of NP-Complete Sets

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR19-079
| 28th May 2019
__

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka#### Average Bias and Polynomial Sources

Revisions: 2

__
TR13-054
| 4th April 2013
__

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook#### Average Case Lower Bounds for Monotone Switching Networks

Revisions: 1

__
TR06-073
| 8th June 2006
__

Andrej Bogdanov, Luca Trevisan#### Average-Case Complexity

Revisions: 1

__
TR03-031
| 8th April 2003
__

Birgit Schelm#### Average-Case Complexity Theory of Approximation Problems

__
TR17-039
| 28th February 2017
__

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

__
TR21-166
| 21st November 2021
__

Lijie Chen, Shuichi Hirahara, Neekon Vafa#### Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions

__
TR21-058
| 21st April 2021
__

Shuichi Hirahara#### Average-Case Hardness of NP from Exponential Worst-Case Hardness Assumptions

__
TR22-076
| 16th May 2022
__

Hunter Monroe#### Average-Case Hardness of Proving Tautologies and Theorems

__
TR98-037
| 29th June 1998
__

Johannes Köbler, Rainer Schuler#### Average-Case Intractability vs. Worst-Case Intractability

__
TR18-029
| 9th February 2018
__

Neeraj Kayal, vineet nair, Chandan Saha#### Average-case linear matrix factorization and reconstruction of low width Algebraic Branching Programs

Revisions: 2

__
TR15-191
| 26th November 2015
__

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

__
TR12-062
| 17th May 2012
__

Ilan Komargodski, Ran Raz#### Average-Case Lower Bounds for Formula Size

Revisions: 2

__
TR21-021
| 18th February 2021
__

Per Austrin, Kilian Risse#### Average-Case Perfect Matching Lower Bounds from Hardness of Tseitin Formulas

Revisions: 2

__
TR20-193
| 29th December 2020
__

Xuangui Huang, Emanuele Viola#### Average-case rigidity lower bounds

Revisions: 1

__
TR11-006
| 20th January 2011
__

Sebastian Müller, Iddo Tzameret#### Average-Case Separation in Proof Complexity: Short Propositional Refutations for Random 3CNF Formulas

Revisions: 1

__
TR10-055
| 31st March 2010
__

Eric Allender#### Avoiding Simplicity is Complex

Revisions: 2

Richard Beigel, Bin Fu

The bin packing problem is to find the minimum

number of bins of size one to pack a list of items with sizes

$a_1,\ldots , a_n$ in $(0,1]$. Using uniform sampling, which selects

a random element from the input list each time, we develop a

randomized $O({n(\log n)(\log\log n)\over ...
more >>>

Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan

We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit $C$ made up of gates that compute constant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functions that compute signs of constant-degree polynomials), counts the number of satisfying assignments to $C$ in significantly better than ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

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

C. Seshadhri, Deeparnab Chakrabarty

Khot and Shinkar (RANDOM, 2016) recently describe an adaptive, $O(n\log(n)/\varepsilon)$-query tester for unateness of Boolean functions $f:\{0,1\}^n \mapsto \{0,1\}$. In this note we describe a simple non-adaptive, $O(n\log(n/\varepsilon)/\varepsilon)$ -query tester for unateness for functions over the hypercube with any ordered range.

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

Program checking, program self-correcting and program self-testing

were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in

the mid eighties as a new way to gain confidence in software, by

considering program correctness on an input by input basis rather than

full program verification. Work in ...
more >>>

George Karakostas

We reduce the approximation factor for Vertex Cover to $2-\Theta(1/\sqrt{logn})$

(instead of the previous $2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even,

and by Monien and Speckenmeyer in 1985. The improvement of the vanishing

factor comes as an application of the recent results of Arora, Rao, and Vazirani

that improved ...
more >>>

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

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

Ivan Mihajlin, Anastasia Sofronova

We prove that a modification of Andreev's function is not computable by $(3 + \alpha - \varepsilon) \log{n}$ depth De Morgan formula with $(2\alpha - \varepsilon)\log{n}$ layers of AND gates at the top for any $1/5 > \alpha > 0$ and any constant $\varepsilon > 0$. In order to do ... more >>>

Kaave Hosseini, Shachar Lovett

The Bogolyubov-Ruzsa lemma, in particular the quantitative bounds obtained by Sanders, plays a central role

in obtaining effective bounds for the inverse $U^3$ theorem for the Gowers norms. Recently, Gowers and Mili\'cevi\'c

applied a bilinear Bogolyubov-Ruzsa lemma as part of a proof of the inverse $U^4$ theorem

with effective bounds.

more >>>

Hamed Hatami, Kaave Hosseini, Xiang Meng

We introduce a new topological argument based on the Borsuk-Ulam theorem to prove a lower bound on sign-rank.

This result implies the strongest possible separation between randomized and unbounded-error communication complexity. More precisely, we show that for a particular range of parameters, the randomized communication complexity of ... more >>>

Oded Goldreich

We present a candidate counterexample to the

easy cylinders conjecture, which was recently suggested

by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019).

Loosely speaking, the conjecture asserts that any 1-1 function

in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential

size that can each be inverted by some polynomial-size circuit.

more >>>

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Finding an efficient solution to the general problem of polynomial identity testing (PIT) is a challenging task. In this work, we study the complexity of two special but natural cases of identity testing - first is a case of depth-$3$ PIT, the other of depth-$4$ PIT.

Our first problem is ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

A predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$ is called {\it approximation resistant} if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment that satisfies at least $\rho(f)+\Omega(1)$ fraction of the constraints.

We present a complete characterization of approximation resistant predicates under the ... more >>>

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $\mathcal{X}$ that are testable with a constant number of samples.

Specifically, we show that a property $\mathcal{P}$ is testable with a constant number of samples if and only if it is (essentially) a $k$-part symmetric property ...
more >>>

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability ... more >>>

Subhash Khot, Madhur Tulsiani, Pratik Worah

For a predicate $f:\{-1,1\}^k \mapsto \{0,1\}$ with $\rho(f) = \frac{|f^{-1}(1)|}{2^k}$, we call the predicate strongly approximation resistant if given a near-satisfiable instance of CSP$(f)$, it is computationally hard to find an assignment such that the fraction of constraints satisfied is outside the range $[\rho(f)-\Omega(1), \rho(f)+\Omega(1)]$.

We present a characterization of ... more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

We explain an asymmetric Prover-Delayer game which precisely characterizes proof size in tree-like Resolution. This game was previously described in a parameterized complexity context to show lower bounds for parameterized formulas and for the classical pigeonhole principle. The main point of this note is to show that the asymmetric game ... more >>>

Jayadev Acharya, Clement Canonne, Gautam Kamath

A recent model for property testing of probability distributions enables tremendous savings in the sample complexity of testing algorithms, by allowing them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., ...
more >>>

Gregory Valiant, Paul Valiant

We prove two new multivariate central limit theorems; the first relates the sum of independent distributions to the multivariate Gaussian of corresponding mean and covariance, under the earthmover distance matric (also known as the Wasserstein metric). We leverage this central limit theorem to prove a stronger but more specific central ... more >>>

Michael Viderman

Ben-Sasson and Sudan (RSA 2006) showed that repeated tensor products of linear codes with a very large distance are locally testable. Due to the requirement of a very large distance the associated tensor products could be applied only over sufficiently large fields. Then Meir (SICOMP 2009) used this result (as ... more >>>

Meena Mahajan, P R Subramanya, V Vinay

The Pfaffian of an oriented graph is closely linked to

Perfect Matching. It is also naturally related to the determinant of

an appropriately defined matrix. This relation between Pfaffian and

determinant is usually exploited to give a fast algorithm for

computing Pfaffians.

We present the first completely combinatorial algorithm for ... more >>>

Masaki Yamamoto

In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at ...
more >>>

Albert Atserias, Víctor Dalmau

We provide a characterization of the resolution

width introduced in the context of Propositional Proof Complexity

in terms of the existential pebble game introduced

in the context of Finite Model Theory. The characterization

is tight and purely combinatorial. Our

first application of this result is a surprising

proof that the ...
more >>>

Eli Ben-Sasson, Michael Viderman

The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs ... more >>>

Juan Luis Esteban, Jacobo Toran

We show that the Player-Adversary game from a paper

by Pudlak and Impagliazzo played over

CNF propositional formulas gives

an exact characterization of the space needed

in treelike resolution refutations. This

characterization is purely combinatorial

and independent of the notion of resolution.

We use this characterization to give ...
more >>>

Oded Goldreich, Muli Safra

The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1)))

is very complicated.

One source of difficulty is the technically involved

analysis of low-degree tests.

Here, we refer to the difficulty of obtaining strong results

regarding low-degree tests; namely, results of the type obtained and

used by ...
more >>>

Maciej Liskiewicz, Christian Hundt

The problem of image matching is to find for two given digital images $A$ and $B$

an admissible transformation that converts image $A$ as close as possible to $B$.

This problem becomes hard if the space of admissible transformations is too complex.

Consequently, in many real applications, like the ones ...
more >>>

Dorit Aharonov, Alex Bredariol Grilo

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>

Carme Alvarez, Raymond Greenlaw

We provide a compendium of problems that are complete for

symmetric logarithmic space (SL). Complete problems are one method

of studying this class for which programming is nonintuitive. A

number of the problems in the list were not previously known to be

complete. A ...
more >>>

Vitaly Feldman

Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistical properties of the examples but cannot see the examples themselves. We describe a new and simple characterization of the query complexity ... more >>>

Sanjeev Khanna, Madhu Sudan, David P. Williamson

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier ...
more >>>

Salil Vadhan, Amit Sahai

We present the first complete problem for SZK, the class of (promise)

problems possessing statistical zero-knowledge proofs (against an

honest verifier). The problem, called STATISTICAL DIFFERENCE, is to

decide whether two efficiently samplable distributions are either

statistically close or far apart. This gives a new characterization

of SZK that makes ...
more >>>

Dima Grigoriev, Edward Hirsch, Konstantin Pervyshev

We present a cryptosystem which is complete for the class of probabilistic public-key cryptosystems with bounded error. Besides traditional encryption schemes such as RSA and El Gamal, this class contains probabilistic encryption of Goldwasser-Micali as well as Ajtai-Dwork and NTRU cryptosystems. The latter two are known to make errors with ... more >>>

Charanjit Jutla, Arnab Roy

We consider multivariate pseudo-linear functions

over finite fields of characteristic two. A pseudo-linear polynomial

is a sum of guarded linear-terms, where a guarded linear-term is a product of one or more linear-guards

and a single linear term, and each linear-guard is

again a linear term but raised ...
more >>>

Saugata Basu

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,

$\mathbf{PH}$,

is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,

namely the class of languages that can be

decided by a Turing machine in polynomial time given access to an

oracle with the power to compute a function in the ...
more >>>

Mika Göös, T.S. Jayram

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

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

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

This paper solves the open problem of exact learning

geometric objects bounded by hyperplanes (and more generally by any constant

degree algebraic surfaces) in the constant

dimensional space from equivalence queries only (i.e., in the on-line learning

model).

We present a novel approach that allows, under ...
more >>>

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

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

Swagato Sanyal

Let $\R(\cdot)$ stand for the bounded-error randomized query complexity. We show that for any relation $f \subseteq \{0,1\}^n \times \mathcal{S}$ and partial Boolean function $g \subseteq \{0,1\}^n \times \{0,1\}$, $\R_{1/3}(f \circ g^n) = \Omega(\R_{4/9}(f) \cdot \sqrt{\R_{1/3}(g)})$. Independently of us, Gavinsky, Lee and Santha \cite{newcomp} proved this result. By an example ... more >>>

Srikanth Srinivasan

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

Nikhil R. Devanur, Lance Fortnow

We exhibit a new computational-based definition of awareness,

informally that our level of unawareness of an object is the amount

of time needed to generate that object within a certain environment.

We give several examples to show this notion matches our intuition

in scenarios where one organizes, accesses and transfers

more >>>

Thomas Vidick

Given two sets $A,B\subseteq\R^n$, a measure of their dependence, or correlation, is given by the expected squared inner product between random $x\in A $ and $y\in B$. We prove an inequality showing that no two sets of large enough Gaussian measure (at least $e^{-\delta n}$ for some constant $\delta >0$) ... more >>>

Miklos Ajtai

A measure $\mu_{n}$ on $n$-dimensional lattices with

determinant $1$ was introduced about fifty years ago to prove the

existence of lattices which contain points from certain sets. $\mu_{n}$

is the unique probability measure on lattices with determinant $1$ which

is invariant under linear transformations with determinant $1$, where a

more >>>

Phong Nguyen, Jacques Stern

Recently, Ajtai discovered a fascinating connection

between the worst-case complexity and the average-case

complexity of some well-known lattice problems.

Later, Ajtai and Dwork proposed a cryptosystem inspired

by Ajtai's work, provably secure if a particular lattice

problem is difficult. We show that there is a converse

to the ...
more >>>

Kfir Barhum, Thomas Holenstein

We present a new framework for proving fully black-box

separations and lower bounds. We prove a general theorem that facilitates

the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box

construction does ...
more >>>

Ran Raz

The parallel repetition theorem states that for any two-prover game,

with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of

the game repeated in parallel $n$ times is at most

$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length

(of the original game) and $c$ is a universal ...
more >>>

Hao Huang, Benny Sudakov

Consider a graph obtained by taking edge disjoint union of $k$ complete bipartite graphs.

Alon, Saks and Seymour conjectured that such graph has chromatic number at most $k+1$.

This well known conjecture remained open for almost twenty years.

In this paper, we construct a counterexample to this

conjecture and discuss ...
more >>>

Scott Aaronson

In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that "almost k-wise independent" distributions are indistinguishable from the uniform distribution by constant-depth ... more >>>

Bruce Edward Litow

We give a method to decide whether or not an

ordinary finite order linear recurrence with constant, rational

coefficients ever generates zero.

Daniel Kane, Jelani Nelson

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in ... more >>>

Luca Trevisan

We describe a new pseudorandom generator for AC0. Our generator $\epsilon$-fools circuits of depth $d$ and size $M$ and uses a seed of length $\tilde O( \log^{d+4} M/\epsilon)$. The previous best construction for $d \geq 3$ was due to Nisan, and had seed length $O(\log^{2d+6} M/\epsilon)$.

A seed length of ...
more >>>

Daniele Micciancio, Panagiotis Voulgaris

We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP).

This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, ...
more >>>

Benny Applebaum, Andrej Bogdanov, Alon Rosen

We consider pseudorandom generators in which each output bit depends on a constant number of input bits. Such generators have appealingly simple structure: they can be described by a sparse input-output dependency graph and a small predicate that is applied at each output. Following the works of Cryan and Miltersen ... more >>>

Kazuhisa Makino, Suguru Tamaki, Masaki Yamamoto

P. Gopalan, P. G. Kolaitis, E. N. Maneva and C. H. Papadimitriou

studied in [Gopalan et al., ICALP2006] connectivity properties of the

solution-space of Boolean formulas, and investigated complexity issues

on connectivity problems in Schaefer's framework [Schaefer, STOC1978].

A set S of logical relations is Schaefer if all relations in ...
more >>>

Rahul Jain, Srijita Kundu

We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $f\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{Z}$. For any $\varepsilon, \zeta > 0$ and any $k\geq1$, we show that

\[ \mathrm{Q}^1_{1-(1-\varepsilon)^{\Omega(\zeta^6k/\log|\mathcal{Z}|)}}(f^k) = \Omega\left(k\left(\zeta^5\cdot\mathrm{Q}^1_{\varepsilon + 12\zeta}(f) - \log\log(1/\zeta)\right)\right),\]

where $\mathrm{Q}^1_{\varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with ...
more >>>

Rahul Jain, Srijita Kundu

We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an $l$-player predicate $V$. In particular we show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol for computing $n$ ... more >>>

Mark Braverman, Omri Weinstein

This paper provides the first general technique for proving information lower bounds on two-party

unbounded-rounds communication problems. We show that the discrepancy lower bound, which

applies to randomized communication complexity, also applies to information complexity. More

precisely, if the discrepancy of a two-party function $f$ with respect ...
more >>>

Farid Ablayev, Svetlana Ablayeva

The superposition (or composition) problem is a problem of

representation of a function $f$ by a superposition of "simpler" (in a

different meanings) set $\Omega$ of functions. In terms of circuits

theory this means a possibility of computing $f$ by a finite circuit

with 1 fan-out gates $\Omega$ of functions. ...
more >>>

Jack H. Lutz

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

Shuichi Hirahara

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

Joshua Brakensiek, Venkatesan Guruswami

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

Parikshit Gopalan

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

Luke Friedman

Propositional proof complexity is an area of complexity theory that addresses the question of whether the class NP is closed under complement, and also provides a theoretical framework for studying practical applications such as SAT solving.

Some of the most well-studied contradictions are random $k$-CNF formulas where each clause of ...
more >>>

Scott Aaronson, Andrew Drucker

We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size. ... more >>>

Gilad Asharov, Yehuda Lindell

In the setting of secure multiparty computation, a set of $n$ parties with private inputs wish to jointly compute some functionality of their inputs. One of the most fundamental results of information-theoretically secure computation was presented by Ben-Or, Goldwasser and Wigderson (BGW) in 1988. They demonstrated that any $n$-party functionality ... more >>>

Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF ... more >>>

Eli Ben-Sasson, Yonatan Bilu

We present the first example of a natural distribution on instances

of an NP-complete problem, with the following properties.

With high probability a random formula from this

distribution (a) is unsatisfiable,

(b) has a short proof that can be found easily, and (c) does not have a short

(general) resolution ...
more >>>

Philippe Moser

We extend Lutz's measure to probabilistic classes, and obtain notions of measure on probabilistic complexity classes

C

such as BPP , BPE and BPEXP. Unlike former attempts,

all our measure notions satisfy all three Lutz's measure axioms, that is

every singleton {L} has measure zero ...
more >>>

H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

We introduce "resource-bounded betting games", and propose

a generalization of Lutz's resource-bounded measure in which the choice

of next string to bet on is fully adaptive. Lutz's martingales are

equivalent to betting games constrained to bet on strings in lexicographic

order. We show that if strong pseudo-random number generators exist,

more >>>

Anna Gal, Jing-Tang Jang

Spira showed that any Boolean formula of size $s$ can be simulated in depth $O(\log s)$. We generalize Spira's theorem and show that any Boolean circuit of size $s$ with segregators of size $f(s)$ can be simulated in depth $O(f(s)\log s)$. If the segregator size is at least $s^{\varepsilon}$ for ... more >>>

Mladen Mikša, Jakob Nordström

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

Lior Gishboliner, Asaf Shapira

Our first theorem in this papers is a hierarchy theorem for the query complexity of testing graph properties with $1$-sided error; more precisely, we show that for every super-polynomial $f$, there is a graph property whose 1-sided-error query complexity is $f(\Theta(1/\varepsilon))$. No result of this type was previously known for ... more >>>

Dieter van Melkebeek, Konstantin Pervyshev

We show that for any reasonable semantic model of computation and for

any positive integer $a$ and rationals $1 \leq c < d$, there exists a language

computable in time $n^d$ with $a$ bits of advice but not in time $n^c$

with $a$ bits of advice. A semantic ...
more >>>

David P. Woodruff, Sergey Yekhanin

A t-private private information retrieval (PIR) scheme allows a user to retrieve the i-th bit of an n-bit string x replicated among k servers, while any coalition of up to t servers learns no information about i. We present a new geometric approach to PIR, and obtain (1) A t-private ... more >>>

Haralampos Tsaknakis, Paul Spirakis

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based

upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem ...
more >>>

Ilya Volkovich

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

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

In particular, we show that:

\begin{enumerate}

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

Petr Savicky, Stanislav Zak

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. The b.p.'s of

polynomial size are a nonuniform counterpart of LOG. Lower bounds

for different kinds of restricted b.p.'s are intensively

investigated. An important restriction are so called $k$-b.p.'s,

where each computation reads each input ...
more >>>

Petr Savicky, Detlef Sieling

Restricted branching programs are considered in complexity theory in

order to study the space complexity of sequential computations and

in applications as a data structure for Boolean functions. In this

paper (\oplus,k)-branching programs and (\vee,k)-branching

programs are considered, i.e., branching programs starting with a

...
more >>>

Victor Chen

A hypergraph dictatorship test is first introduced by Samorodnitsky

and Trevisan and serves as a key component in

their unique games based $\PCP$ construction. Such a test has oracle

access to a collection of functions and determines whether all the

functions are the same dictatorship, or all their low degree ...
more >>>

Elvira Mayordomo

We obtain the following full characterization of constructive dimension

in terms of algorithmic information content. For every sequence A,

cdim(A)=liminf_n (K(A[0..n-1])/n.

Jochen Messner, Thomas Thierauf

Recently, Moser and Tardos [MT10] came up with a constructive proof of the Lovász Local Lemma. In this paper, we give another constructive proof of the lemma, based on Kolmogorov complexity. Actually, we even improve the Local Lemma slightly.

Petr Savicky, Stanislav Zak

Branching programs (b.p.'s) or decision diagrams are a general

graph-based model of sequential computation. B.p.'s of polynomial

size are a nonuniform counterpart of LOG. Lower bounds for

different kinds of restricted b.p.'s are intensively investigated.

An important restriction are so called 1-b.p.'s, where each

computation reads each input bit at ...
more >>>

Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani

We study semidefinite programming relaxations of Vertex Cover arising from

repeated applications of the LS+ ``lift-and-project'' method of Lovasz and

Schrijver starting from the standard linear programming relaxation.

Goemans and Kleinberg prove that after one round of LS+ the integrality

gap remains arbitrarily close to 2. Charikar proves an integrality ...
more >>>

Daniele Micciancio, Bogdan Warinschi

Computing the Hermite Normal Form

of an $n\times n$ matrix using the best current algorithms typically

requires $O(n^3\log M)$ space, where $M$ is a bound on the length of

the columns of the input matrix.

Although polynomial in the input size (which ...
more >>>

Scott Aaronson

One of the crown jewels of complexity theory is Valiant's 1979 theorem that computing the permanent of an n*n matrix is #P-hard. Here we show that, by using the model of linear-optical quantum computing---and in particular, a universality theorem due to Knill, Laflamme, and Milburn---one can give a different and ... more >>>

Derrick Stolee, Chris Bourke, N. V. Vinodchandran

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

Yijia Chen, Jörg Flum

In [Blass, Gurevich, and Shelah, 99] a logic L_Y has been introduced as a possible candidate for a logic capturing the PTIME properties of structures (even in the absence of an ordering of their universe). A reformulation of this problem in terms of a parameterized halting problem p-Acc for nondeterministic ... more >>>

Stanislav Žák

We present a mathematical model of the intuitive notions such as the

knowledge or the information arising at different stages of

computations on branching programs (b.p.). The model has two

appropriate

properties:\\

i) The "knowledge" arising at a stage of computation in question is

derivable from the "knowledge" arising ...
more >>>

Anastasia Sofronova, Dmitry Sokolov

Random $\Delta$-CNF formulas are one of the few candidates that are expected to be hard to refute in any proof system. One of the frontiers in the direction of proving lower bounds on these formulas is the $k$-DNF Resolution proof system (aka $\mathrm{Res}(k)$). Assume we sample $m$ clauses over $n$ ... more >>>

Ilan Komargodski, Ran Raz, Yael Tauman Kalai

In 1985, Ben-Or and Linial (Advances in Computing Research '89) introduced the collective coin-flipping problem, where $n$ parties communicate via a single broadcast channel and wish to generate a common random bit in the presence of adaptive Byzantine corruptions. In this model, the adversary can decide to corrupt a party ... more >>>

Shachar Lovett, Ely Porat

An approximate membership data structure is a randomized data

structure for representing a set which supports membership

queries. It allows for a small false positive error rate but has

no false negative errors. Such data structures were first

introduced by Bloom in the 1970's, and have since had numerous

applications, ...
more >>>

Farid Ablayev, Marek Karpinski

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the

size of any randomized ordered read-once branching program

computing integer multiplication. Our proof depends on proving

a new lower bound on Yao's randomized one-way communication

complexity of certain boolean functions. It generalizes to some

other ...
more >>>

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

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

Eric Allender, Igor E. Shparlinski, Michael Saks

Recent work by Bernasconi, Damm and Shparlinski

proved lower bounds on the circuit complexity of the square-free

numbers, and raised as an open question if similar (or stronger)

lower bounds could be proved for the set of prime numbers. In

this short note, we answer this question ...
more >>>

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees

to the case of {\em randomized} algebraic decision trees (with

two-sided error) for languages being finite unions of hyperplanes

and the intersections of halfspaces, solving a long standing open

problem. As an application, among ...
more >>>

Martin Sauerhoff

In this paper, we are concerned with randomized OBDDs and randomized

read-k-times branching programs. We present an example of a Boolean

function which has polynomial size randomized OBDDs with small,

one-sided error, but only non-deterministic read-once branching

programs of exponential size. Furthermore, we discuss a lower bound

technique for randomized ...
more >>>

Tom Gur, Oded Lachish

A locally decodable code (LDC) C:{0,1}^k -> {0,1}^n is an error correcting code wherein individual bits of the message can be recovered by only querying a few bits of a noisy codeword. LDCs found a myriad of applications both in theory and in practice, ranging from probabilistically checkable proofs to ... more >>>

Thomas Watson

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. ... more >>>

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria

In this note we show that the asymmetric Prover-Delayer game developed by Beyersdorff, Galesi, and Lauria (ECCC TR10-059) for Parameterized Resolution is also applicable to other tree-like proof systems. In particular, we use this asymmetric Prover-Delayer game to show a lower bound of the form $2^{\Omega(n\log n)}$ for the pigeonhole ... more >>>

Ran Raz, Amir Shpilka, Amir Yehudayoff

We construct an explicit polynomial $f(x_1,...,x_n)$, with

coefficients in ${0,1}$, such that the size of any syntactically

multilinear arithmetic circuit computing $f$ is at least

$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field.

Mrinal Kumar, Ben Lee Volk

The determinantal complexity of a polynomial $P \in \mathbb{F}[x_1, \ldots, x_n]$ over a field $\mathbb{F}$ is the dimension of the smallest matrix $M$ whose entries are affine functions in $\mathbb{F}[x_1, \ldots, x_n]$ such that $P = Det(M)$. We prove that the determinantal complexity of the polynomial $\sum_{i = 1}^n x_i^n$ ... more >>>

Oded Goldreich, Dana Ron

A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.

We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.

Howard Barnum, Michael Saks

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires ``decoherence'' ... more >>>

Pavel Pudlak

We prove an exponential lower bound on the lengths of resolution proofs of propositions expressing the finite Ramsey theorem for pairs.

more >>>Chris Calabro

One way to quantify how dense a multidag is in long paths is to find

the largest n, m such that whichever ≤ n edges are removed, there is still

a path from an original input to an original output with ≥ m edges

- the larger ...
more >>>

Philipp Woelfel

We present a new lower bound technique for two types of restricted

Branching Programs (BPs), namely for read-once BPs (BP1s) with

restricted amount of nondeterminism and for (1,+k)-BPs. For this

technique, we introduce the notion of (strictly) k-wise l-mixed

Boolean functions, which generalizes the concept of l-mixedness ...
more >>>

Mika Göös, Gilbert Maystre

We show that computing the majority of $n$ copies of a boolean function $g$ has randomised query complexity $\mathrm{R}(\mathrm{Maj} \circ g^n) = \Theta(n\cdot \bar{\mathrm{R}}_{1/n}(g))$. In fact, we show that to obtain a similar result for any composed function $f\circ g^n$, it suffices to prove a sufficiently strong form of the ... more >>>

Naomi Kirshner, Alex Samorodnitsky

Let $p \ge 2$. We improve the bound $\frac{\|f\|_p}{\|f\|_2} \le (p-1)^{s/2}$ for a polynomial $f$ of degree $s$ on the boolean cube $\{0,1\}^n$, which comes from hypercontractivity, replacing the right hand side of this inequality by an explicit bivariate function of $p$ and $s$, which is smaller than $(p-1)^{s/2}$ for ... more >>>

Tsuyoshi Ito, Thomas Vidick

We prove a strong limitation on the ability of entangled provers to collude in a multiplayer game. Our main result is the first nontrivial lower bound on the class MIP* of languages having multi-prover interactive proofs with entangled provers; namely MIP* contains NEXP, the class of languages decidable in non-deterministic ... more >>>

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) ...
more >>>

Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar

A code $C \colon \{0,1\}^k \to \{0,1\}^n$ is a $q$-locally decodable code ($q$-LDC) if one can recover any chosen bit $b_i$ of the message $b \in \{0,1\}^k$ with good confidence by randomly querying the encoding $x = C(b)$ on at most $q$ coordinates. Existing constructions of $2$-LDCs achieve $n = ... more >>>

Suryajith Chillara, Christian Engels, Nutan Limaye, Srikanth Srinivasan

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.

We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that ... more >>>

Mark Bun, Justin Thaler

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

Richard Beigel, Lance Fortnow, William Gasarch

We show that any 1-round 2-server Private Information

Retrieval Protocol where the answers are 1-bit long must ask questions

that are at least $n-2$ bits long, which is nearly equal to the known

$n-1$ upper bound. This improves upon the approximately $0.25n$ lower

bound of Kerenidis and de Wolf while ...
more >>>

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin

We prove that with high probability over the choice of a random graph $G$ from the Erd\H{o}s-R\'enyi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$.

This yields a nearly tight ...
more >>>

Edward Hirsch

Recently there was a significant progress in

proving (exponential-time) worst-case upper bounds for the

propositional satisfiability problem (SAT).

MAX-SAT is an important generalization of SAT.

Several upper bounds were obtained for MAX-SAT and

its NP-complete subproblems.

In particular, Niedermeier and Rossmanith recently

...
more >>>

Ryan Williams

We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>>

Ilias Diakonikolas, Daniel Kane

We study problems in distribution property testing:

Given sample access to one or more unknown discrete distributions,

we want to determine whether they have some global property or are $\epsilon$-far

from having the property in $\ell_1$ distance (equivalently, total variation distance, or ``statistical distance'').

In this work, we give a ...
more >>>

Xin Li

We study the problem of constructing affine extractors over $\mathsf{GF(2)}$. Previously the only known construction that can handle sources with arbitrarily linear entropy is due to Bourgain (and a slight modification by Yehudayoff), which relies heavily on the technique of Van der Corput differencing and a careful choice of a ... more >>>

Chaoping Xing, chen yuan

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

Nader Bshouty

We present a new approach to the composition

of learning algorithms (in various models) for

classes of constant VC-dimension into learning algorithms for

more complicated classes.

We prove that if a class $\CC$ is learnable

in time $t$ from a hypothesis class $\HH$ of constant VC-dimension

then the class ...
more >>>

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

We describe new constructions of error correcting codes, obtained by "degree-lifting" a short algebraic geometry (AG) base-code of block-length $q$ to a lifted-code of block-length $q^m$, for arbitrary integer $m$. The construction generalizes the way degree-$d$, univariate polynomials evaluated over the $q$-element field (also known as Reed-Solomon codes) are "lifted" ... more >>>

Iftach Haitner, Omer Reingold

Interactive hashing, introduced by Naor et al. [NOVY98], plays

an important role in many cryptographic protocols. In particular, it

is a major component in all known constructions of

statistically-hiding commitment schemes and of zero-knowledge

arguments based on general one-way permutations and on one-way

functions. Interactive hashing with respect to a ...
more >>>

Gábor Kun, Mario Szegedy

The well known dichotomy conjecture of Feder and

Vardi states that for every ﬁnite family Γ of constraints CSP(Γ) is

either polynomially solvable or NP-hard. Bulatov and Jeavons re-

formulated this conjecture in terms of the properties of the algebra

P ol(Γ), where the latter is ...
more >>>

Arnaldo Moura, Igor Carboni Oliveira

We propose a generalization of the traditional algorithmic space and

time complexities. Using the concept introduced, we derive an

unified proof for the deterministic time and space hierarchy

theorems, now stated in a much more general setting. This opens the

possibility for the unification and generalization of other results

that ...
more >>>

Himanshu Tyagi, Shun Watanabe

We present an information theoretic proof of the nonsignalling multiprover parallel repetition theorem, a recent extension of its two-prover variant that underlies many hardness of approximation results. The original proofs used de Finetti type decomposition for strategies. We present a new proof that is based on a technique we introduced ... more >>>

Iftach Haitner, Mohammad Mahmoody, David Xiao

We investigate the question of what languages can be decided efficiently with the help of a recursive collision-finding oracle. Such an oracle can be used to break collision-resistant hash functions or, more generally, statistically hiding commitments. The oracle we consider, $Sam_d$ where $d$ is the recursion depth, is based on ... more >>>

Jin-Yi Cai

We prove a new transference theorem in the geometry of numbers,

giving optimal bounds relating the successive minima of a lattice

with the minimal length of generating vectors of its dual.

It generalizes the transference theorem due to Banaszczyk.

We also prove a stronger bound for the special class of ...
more >>>

Madhu Sudan, Noga Ron-Zewi

Over a finite field $\F_q$ the $(n,d,q)$-Reed-Muller code is the code given by evaluations of $n$-variate polynomials of total degree at most $d$ on all points (of $\F_q^n$). The task of testing if a function $f:\F_q^n \to \F_q$ is close to a codeword of an $(n,d,q)$-Reed-Muller code has been of ... more >>>

Miklos Ajtai

We prove that for all positive integer $k$ and for all

sufficiently small $\epsilon >0$ if $n$ is sufficiently large

then there is no Boolean (or $2$-way) branching program of size

less than $2^{\epsilon n}$ which for all inputs

$X\subseteq \lbrace 0,1,...,n-1\rbrace $ computes in time $kn$

the parity of ...
more >>>

Pavel Pudlak

We shall prove a lower bound on the number of edges in some bounded

depth graphs. This theorem is stronger than lower bounds proved on

bounded depth superconcentrators and enables us to prove a lower bound

on certain bounded depth circuits for which we cannot use

superconcentrators: we prove that ...
more >>>

Sofya Raskhodnikova, Adam Smith

We show that in the bounded degree model for graph property testing,

adaptivity is essential. An algorithm is *non-adaptive* if it makes all queries to the input before receiving any answers. We call a property *non-trivial* if it does not depend only on the degree distribution of the nodes. We ...
more >>>

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

We show a generic, simple way to amplify the error-tolerance of locally decodable codes.

Specifically, we show how to transform a locally decodable code that can tolerate a constant fraction of errors

to a locally decodable code that can recover from a much higher error-rate. We also show how to ...
more >>>

Uriel Feige, Marek Karpinski, Michael Langberg

We design a $0.795$ approximation algorithm for the Max-Bisection problem

restricted to regular graphs. In the case of three regular graphs our

results imply an approximation ratio of $0.834$.

Shay Moran, Amir Yehudayoff

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize

the expected number of comparisons. We generalize Fredman's algorithm which

is a variant of insertion sort and provide a basically tight upper bound: If \mu is

more >>>

T.C. Vijayaraghavan

Recently in [Vij09, Corollary 3.7] the complexity class ModL has been shown to be closed under complement assuming NL = UL. In this note we continue to show many other closure properties of ModL which include the following.

1. ModL is closed under $\leq ^L_m$ reduction, $\vee$(join) and $\leq ^{UL}_m$ ... more >>>

Luca Trevisan

We describe a deterministic algorithm that, for constant k,

given a k-DNF or k-CNF formula f and a parameter e, runs in time

linear in the size of f and polynomial in 1/e and returns an

estimate of the fraction of satisfying assignments for f up to ...
more >>>

Xiaoyang Gu

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

Parikshit Gopalan

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.

more >>>Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>

Eric Allender, Azucena Garvia Bosshard, Amulya Musipatla

This paper focuses on a variant of the circuit minimization problem (MCSP), denoted MKTP, which studies resource-bounded Kolmogorov complexity in place of circuit size. MCSP is not known to be hard for any complexity class under any kind of m-reducibility, but recently MKTP was shown to be hard for DET ... more >>>

Michael Viderman

Inspired by recent construction of high-rate locally correctable codes with sublinear query complexity due to

Kopparty, Saraf and Yekhanin (2010) we address the similar question for locally testable codes (LTCs).

In this note we show a construction of high-rate LTCs with sublinear query complexity.

More formally, we show that for ...
more >>>

Marek Karpinski, Rustam Mubarakzjanov

We prove that the error-free (Las Vegas) randomized OBDDs

are computationally equivalent to the deterministic OBDDs.

In contrast, it is known the same is not true for the

Las Vegas read-once branching programs.

Andrzej Lingas

A monotone Boolean circuit is a restriction of a Boolean circuit

allowing for the use of disjunctions, conjunctions, the Boolean

constants, and the input variables. A monotone Boolean circuit is

multilinear if for any AND gate the two input functions have no

variable in common. We ...
more >>>

Pavel Hrubes, Pavel Pudlak

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

Yanyi Liu, Rafael Pass

We show equivalence between the existence of one-way

functions and the existence of a \emph{sparse} language that is

hard-on-average w.r.t. some efficiently samplable ``high-entropy''

distribution.

In more detail, the following are equivalent:

- The existentence of a $S(\cdot)$-sparse language $L$ that is

hard-on-average with respect to some samplable ...
more >>>

Nir Bitansky, Vinod Vaikuntanathan

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

Amit Chakrabarti

The deterministic space complexity of approximating the length of the longest increasing subsequence of

a stream of $N$ integers is known to be $\widetilde{\Theta}(\sqrt N)$. However, the randomized

complexity is wide open. We show that the technique used in earlier work to establish the $\Omega(\sqrt

N)$ deterministic lower bound fails ...
more >>>

Stasys Jukna

A syntactic read-k times branching program has the restriction

that no variable occurs more than k times on any path (whether or not

consistent). We exhibit an explicit Boolean function f which cannot

be computed by nondeterministic syntactic read-k times branching programs

of size less than exp(\sqrt{n}}k^{-2k}), ...
more >>>

Matthias Krause

It is shown that decomposition via Chinise Remainder does not

yield polynomial size depth 3 threshold circuits for iterated

multiplication of n-bit numbers. This result is achieved by

proving that, in contrast to multiplication of two n-bit

numbers, powering, division, and other related problems, the

...
more >>>

Pavel Hrubes

We show that the semantic cutting planes proof system has feasible interpolation via monotone real circuits. This gives an exponential lower bound on proof length in the system.

We also pose the following problem: can every multivariate non-decreasing function be expressed as a composition of non-decreasing functions in two ... more >>>

Jelani Nelson

In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for ... more >>>

Denis Xavier Charles

We show that there are infinitely many primes $p$, such

that the subgroup membership problem for PSL(2,p) belongs

to $\NP \cap \coNP$.

Avraham Ben-Aroya, Igor Shinkar

A subspace-evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>>

Xi Chen, Yu Cheng, Bo Tang

In this note, we study the recursive teaching dimension(RTD) of concept classes of low VC-dimension. Recall that the VC-dimension of $C \subseteq \{0,1\}^n$, denoted by $VCD(C)$, is the maximum size of a shattered subset of $[n]$, where $Y\subseteq [n]$ is shattered if for every binary string $\vec{b}$ of length $|Y|$, ... more >>>

Ahuva Mu'alem

This work initiates the study of algorithms

for the testing of monotonicity of mechanisms.

Such testing algorithms are useful for

searching dominant strategy mechanisms.

An $\e$-tester for monotonicity

is given a query access to a mechanism,

accepts if monotonicity is satisfied,

and rejects with high probability if more than $\e$-fraction

more >>>

N. V. Vinodchandran

In this short note we show that for any integer k, there are

languages in the complexity class PP that do not have Boolean

circuits of size $n^k$.

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis

The following two decision problems capture the complexity of

comparing integers or rationals that are succinctly represented in

product-of-exponentials notation, or equivalently, via arithmetic

circuits using only multiplication and division gates, and integer

inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>

Till Tantau

Deciding whether a vertex in a graph is reachable from another

vertex has been studied intensively in complexity theory and is

well understood. For common types of graphs like directed graphs,

undirected graphs, dags or trees it takes a (possibly

nondeterministic) logspace machine to decide the reachability

problem, and ...
more >>>

Noam Nisan

We present a very simple reduction that when given a graph G and an integer k produces a game that has an evolutionary stable strategy if and only if the maximum clique size of G is not exactly k. Formally this shows that existence of evolutionary stable strategies is hard ... more >>>

Arnab Bhattacharyya

Given a boolean function, let epsilon_M(f) denote the smallest distance between f and a monotone function on {0,1}^n. Let delta_M(f) denote the fraction of hypercube edges where f violates monotonicity. We give an alternative proof of the tight bound: delta_M(f) >= 2/n eps_M(f) for any boolean function f. This was ... more >>>

Siddharth Bhandari, Prahladh Harsha

Recently, Cohen, Haeupler and Schulman gave an explicit construction of binary tree codes over polylogarithmic-sized output alphabet based on Pudl\'{a}k's construction of maximum-distance-separable (MDS) tree codes using totally-non-singular triangular matrices. In this short note, we give a unified and simpler presentation of Pudl\'{a}k and Cohen-Haeupler-Schulman's constructions.

more >>>Meena Mahajan, V Vinay

In this note, we consider the problem of computing the

coefficients of the characteristic polynomial of a given

matrix, and the related problem of verifying the

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, ...
more >>>

Pavol Duris

In this paper we deal with one-way multi-head data-independent finite automata. A $k$-head finite automaton $A$ is data-independent, if the position of every head $i$ after step $t$ in the computation on an input $w$ is a function that depends only on the length of the input $w$, on $i$ ... more >>>

Roei Tell

The quantified derandomization problem of a circuit class $\mathcal{C}$ with a function $B:\mathbb{N}\rightarrow\mathbb{N}$ is the following: Given an input circuit $C\in\mathcal{C}$ over $n$ bits, deterministically distinguish between the case that $C$ accepts all but $B(n)$ of its inputs and the case that $C$ rejects all but $B(n)$ of its inputs. ... more >>>

Stasys Jukna

In 1957 Markov proved that every circuit in $n$ variables

can be simulated by a circuit with at most $\log(n+1)$ negations.

In 1974 Fischer has shown that this can be done with only

polynomial increase in size.

In this note we observe that some explicit monotone functions ... more >>>

Stasys Jukna

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

Till Tantau

A language is called k-membership comparable if there exists a

polynomial-time algorithm that excludes for any k words one of

the 2^k possibilities for their characteristic string.

It is known that all membership comparable languages can be

reduced to some P-selective language with polynomially many

adaptive queries. We show however ...
more >>>

Pavel Hrubes

Koiran's real $\tau$-conjecture asserts that if a non-zero real polynomial can be written as $f=\sum_{i=1}^{p}\prod_{j=1}^{q}f_{ij},$

where each $f_{ij}$ contains at most $k$ monomials, then the number of distinct real roots of $f$ is polynomial in $pqk$. We show that the conjecture implies quite a strong property of the ...
more >>>

Ragesh Jaiswal

Given an unpredictable Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$, the standard Yao's XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in [k]}f(x_i)$ given $x_1, ..., x_k \in \{0, 1\}^n$, whereas the Selective XOR lemma is a statement about the unpredictability of computing $\oplus_{i \in S}f(x_i)$ ... more >>>

Pavel Pudlak

We consider computations of linear forms over {\bf R} by

circuits with linear gates where the absolute values

coefficients are bounded by a constant. Also we consider a

related concept of restricted rigidity of a matrix. We prove

some lower bounds on the size of such circuits and the

more >>>

Roei Tell

A tolerant tester with one-sided error for a property is a tester that accepts every input that is close to the property, with probability 1, and rejects every input that is far from the property, with positive probability. In this note we show that such testers require a linear number ... more >>>

Marek Karpinski, Yakov Nekrich

We consider the problem of traversing skew (unbalanced) Merkle

trees and design an algorithm for traversing a skew Merkle tree

in time O(log n/log t) and space O(log n (t/log t)), for any choice

of parameter t\geq 2.

This algorithm can be of special interest in situations when

more >>>

Eric Allender

A very recent paper by Caussinus, McKenzie, Therien, and Vollmer

[CMTV] shows that ACC^0 is properly contained in ModPH, and TC^0

is properly contained in the counting hierarchy. Thus, [CMTV] shows

that there are problems in ModPH that require superpolynomial-size

uniform ACC^0 ...
more >>>

Prasad Raghavendra

Locally Decodable codes(LDC) support decoding of any particular symbol of the input message by reading constant number of symbols of the codeword, even in presence of constant fraction of errors.

In a recent breakthrough, Yekhanin designed $3$-query LDCs that hugely improve over earlier constructions. Specifically, for a Mersenne prime $p ... more >>>

Henry Yuen

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.

...
more >>>

Iftach Haitner

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

Justin Holmgren, Ran Raz

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann ... more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

Andrew Drucker

We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, ... more >>>

Luke Schaeffer

Several cellular automata (CA) are known to be universal in the sense that one can simulate arbitrary computations (e.g., circuits or Turing machines) by carefully encoding the computational device and its input into the cells of the CA. In this paper, we consider a different kind of universality proposed by ... more >>>

Mrinal Kumar, Ben Lee Volk

We show that there is a defining equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}(x_{1, 1}, \ldots, x_{n, n})$ of degree ... more >>>

Valentine Kabanets, Daniel Kane, Zhenjian Lu

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

Klaus Jansen, Marek Karpinski, Andrzej Lingas

The Max-Bisection and Min-Bisection are the problems of finding

partitions of the vertices of a given graph into two equal size subsets so as

to maximize or minimize, respectively, the number of edges with exactly one

endpoint in each subset.

In this paper we design the first ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

We design a polynomial time approximation scheme (PTAS) for

the problem of Metric MIN-BISECTION of dividing a given finite metric

space into two halves so as to minimize the sum of distances across

that partition. The method of solution depends on a new metric placement

partitioning ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that the subdense instances of MAX-CUT of average

degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS).

We extend this result also to show that the instances of general 2-ary

maximum constraint satisfaction problems (MAX-CSP) of the same average

density have PTASs. Our results ...
more >>>

Jiri Sima, Stanislav Zak

The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>>

John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann

Presented is an algorithm (for learning a subclass of erasing regular

pattern languages) which

can be made to run with arbitrarily high probability of

success on extended regular languages generated by patterns

$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$

for unknown $m$ but known $c$,

more >>>

Mark Jerrum, Eric Vigoda

We present a fully-polynomial randomized approximation scheme

for computing the permanent of an arbitrary matrix

with non-negative entries.

Falk Unger

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>

Petr Savicky

Branching programs are a model for representing Boolean

functions. For general branching programs, the

satisfiability and nonequivalence tests are NP-complete.

For read-once branching programs, which can test each

variable at most once in each computation, the satisfiability

test is trivial and there is also a probabilistic polynomial

time test ...
more >>>

Leonid Gurvits

Consider a homogeneous polynomial $p(z_1,...,z_n)$ of degree $n$ in $n$ complex variables .

Assume that this polynomial satisfies the property : \\

$|p(z_1,...,z_n)| \geq \prod_{1 \leq i \leq n} Re(z_i)$ on the domain $\{(z_1,...,z_n) : Re(z_i) \geq 0 , 1 \leq i \leq n \}$ . \\

We prove that ... more >>>

Zubayir Kazi

Abstract The Union Closed Set Conjecture states that if a set system X\subseteq\mathcal{P}([n]) is closed under pairwise unions, then there exists a\in[n] in at least half of the sets of X. We show that there is a very natural generalization of the union closed set conjecture which gives a lower ... more >>>

Shachar Lovett

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.

Yehuda Lindell, Benny Pinkas

In the mid 1980's, Yao presented a constant-round protocol for

securely computing any two-party functionality in the presence of

semi-honest adversaries (FOCS 1986). In this paper, we provide a

complete description of Yao's protocol, along with a rigorous

proof of security. Despite the importance of Yao's protocol to the

field ...
more >>>

Michael Forbes, Amir Shpilka

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

Miklos Ajtai, Cynthia Dwork

We present a probabilistic public key cryptosystem which is

secure unless the following worst-case lattice problem can be solved in

polynomial time:

"Find the shortest nonzero vector in an n dimensional lattice

L where the shortest vector v is unique in the sense that any other

vector whose ...
more >>>

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

We show that any Algebraic Branching Program (ABP) computing the polynomial $\sum_{i = 1}^n x_i^n$ has at least $\Omega(n^2)$ vertices. This improves upon the lower bound of $\Omega(n\log n)$, which follows from the classical result of Baur and Strassen [Str73, BS83], and extends the results by Kumar [Kum19], which showed ... more >>>

Mrinal Kumar

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

Amos Beimel, Tal Malkin

Secure computation is one of the most fundamental cryptographic tasks.

It is known that all functions can be computed securely in the

information theoretic setting, given access to a black box for some

complete function such as AND. However, without such a black box, not

all functions can be securely ...
more >>>

Scott Aaronson, Daniel Grier, Luke Schaeffer

We present a trichotomy theorem for the quantum query complexity of regular languages. Every regular language has quantum query complexity $\Theta(1)$, $\tilde{\Theta}(\sqrt n)$, or $\Theta(n)$. The extreme uniformity of regular languages prevents them from taking any other asymptotic complexity. This is in contrast to even the context-free languages, which we ... more >>>

Thomas Watson, Dieter van Melkebeek

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

Ewin Tang

A recommendation system suggests products to users based on data about user preferences. It is typically modeled by a problem of completing an $m\times n$ matrix of small rank $k$. We give the first classical algorithm to produce a recommendation in $O(\text{poly}(k)\text{polylog}(m,n))$ time, which is an exponential improvement on previous ... more >>>

Suguru Tamaki, Yuichi Yoshida

Long Code testing is a fundamental problem in the area of property

testing and hardness of approximation.

Long Code is a function of the form $f(x)=x_i$ for some index $i$.

In the Long Code testing, the problem is, given oracle access to a

collection of Boolean functions, to decide whether ...
more >>>

Jonathan A. Kelner, Daniel A. Spielman

We present the first randomized polynomial-time simplex algorithm for linear programming. Like the other known polynomial-time algorithms for linear programming, its running time depends polynomially on the number of bits used to represent its input.

We begin by reducing the input linear program to a special form in which we ... more >>>

Avi Wigderson, David Xiao

In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter, in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is ... more >>>

Massimo Lauria

Ramsey Theorem is a cornerstone of combinatorics and logic. In its

simplest formulation it says that there is a function $r$ such that

any simple graph with $r(k,s)$ vertices contains either a clique of

size $k$ or an independent set of size $s$. We study the complexity

of proving upper ...
more >>>

Christian Glaßer, Stephen Travers, Klaus W. Wagner

We introduce the polynomial-time tree reducibility

(ptt-reducibility). Our main result states that for

languages $B$ and $C$ it holds that

$B$ ptt-reduces to $C$ if and only if

the unbalanced leaf-language class of $B$ is robustly contained in

the unbalanced leaf-language class of $C$.

...
more >>>

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

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

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

two-source extractors with small error for sources with arbitrarily

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

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

Jan Krajicek

We give a general reduction of lengths-of-proofs lower bounds for

constant depth Frege systems in DeMorgan language augmented by

a connective counting modulo a prime $p$

(the so called $AC^0[p]$ Frege systems)

to computational complexity

lower bounds for search tasks involving search trees branching upon

values of linear maps on ...
more >>>

Siddharth Bhaskar

For a function $t : 2^\star \to 1^\star$, let $C_t$ be the set of problems decidable on input $x$ in time at most $t(x)$ almost everywhere. The Union Theorem of Meyer and McCreight asserts that any union $\bigcup_{i < \omega} C_{t_i}$ for a uniformly recursive sequence of bounds $t_i$ is ... more >>>

Hanlin Ren, Rahul Santhanam

Meta-complexity studies the complexity of computational problems about complexity theory, such as the Minimum Circuit Size Problem (MCSP) and its variants. We show that a relativization barrier applies to many important open questions in meta-complexity. We give relativized worlds where:

* MCSP can be solved in deterministic polynomial time, but ... more >>>

Günter Hotz

We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>>

Periklis Papakonstantinou, Guang Yang

Every pseudorandom generator is in particular a one-way function. If we only consider part of the output of the

pseudorandom generator is this still one-way? Here is a general setting formalizing this question. Suppose

$G:\{0,1\}^n\rightarrow \{0,1\}^{\ell(n)}$ is a pseudorandom generator with stretch $\ell(n)> n$. Let $M_R\in\{0,1\}^{m(n)\times \ell(n)}$ be a linear ...
more >>>

Srikanth Srinivasan

Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of ... more >>>

Oded Goldreich

We consider the problem of estimating the average of a huge set of values.

That is,

given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,

we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$

upto an additive error of $\epsilon$.

We are allowed to employ a randomized algorithm which may ...
more >>>

Emanuele Viola

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

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

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

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

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

Kazuhisa Seto, Suguru Tamaki

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis.

For formulas of size at most $cn$, our algorithm runs in time $2^{(1-\mu_c)n}$ for some constant $\mu_c>0$.

As a byproduct of the running time analysis of our algorithm,

we get strong ...
more >>>

Suguru Tamaki

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

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

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

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

Stephen Cook, Antonina Kolokolova

We introduce a second-order system V_1-Horn of bounded arithmetic

formalizing polynomial-time reasoning, based on Graedel's

second-order Horn characterization of P. Our system has

comprehension over P predicates (defined by Graedel's second-order

Horn formulas), and only finitely many function symbols. Other

systems of polynomial-time reasoning either ...
more >>>

Eli Ben-Sasson, iddo Ben-Tov, Ariel Gabizon, Michael Riabzev

Probabilistically Checkable Proofs (PCPs) [Babai et al. FOCS 90; Arora et al. JACM 98] can be used to construct asymptotically efficient cryptographic zero knowledge arguments of membership in any language in NEXP, with minimal communication complexity and computational effort on behalf of both prover and verifier [Babai et al. STOC ... more >>>

Pavol Duris, Juraj Hromkovic, Katsushi Inoue

The investigation of the computational power of randomized computations

is one of the central tasks of current complexity and algorithm theory.

In this paper for the first time a "strong" separation between the power

of determinism, Las Vegas randomization, and nondeterminism for a compu-

ting model is proved. The computing ...
more >>>

Dmytro Gavinsky, Alexander A. Sherstov

We prove that NP$\ne$coNP and coNP$\nsubseteq$MA in the number-on-forehead model of multiparty communication complexity for up to $k=(1-\epsilon)\log n$ players, where $\epsilon>0$ is any constant. Specifically, we construct a function $F:(\zoon)^k\to\zoo$ with co-nondeterministic

complexity $O(\log n)$ and Merlin-Arthur

complexity $n^{\Omega(1)}$.

The problem was open for $k\geq3$.

Ilario Bonacina, Neil Thapen

Recently it was shown that PLS is not contained in PPADS (ECCC report TR22-058). We show that this separation already implies that PLS is not contained in PPP. These separations are shown for the decision tree model of TFNP and imply similar separations in the type-2, relativized model.

Important note. ... more >>>

Detlef Sieling

For (1,+k)-branching programs and read-k-times branching

programs syntactic and nonsyntactic variants can be distinguished. The

nonsyntactic variants correspond in a natural way to sequential

computations with restrictions on reading the input while lower bound

proofs are easier or only known for the syntactic variants. In this

paper it is shown ...
more >>>

Michal Koucky, Vojtech Rodl, Navid Talebanfard

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph on $m$ edges with bounded vertex degree has a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. ... more >>>

Pratik Worah

This brief survey gives a (roughly) self-contained overview of some complexity theoretic results about semi-algebraic proof systems and related hierarchies and the strong connections between them. The article is not intended to be a detailed survey on "Lift and Project" type optimization hierarchies (cf. Chlamtac and Tulsiani) or related proof ... more >>>

Daniel Kane, Osamu Watanabe

Consider any Boolean function $F(X_1,\ldots,X_N)$ that has more than $2^{-N^{d}}$ satisfying assignments and that can be expressed by a CNF formula with at most $N^{1+e}$ clauses for some $d>0$ and $e>0$ such that $d+e$ is less than $1$ (*). Then how many variables do we need to fix in order ... more >>>

Hasan Abasi, Nader Bshouty

We develop a new algebraic technique that gives a simple randomized algorithm for the simple $k$-path problem with the same complexity $O^*(1.657^k)$ as in [A. Bj\"orklund. Determinant Sums for Undirected Hamiltonicity. FOCS 2010, pp. 173--182, (2010). A. Bj\"orklund, T. Husfeldt, P. Kaski, M. Koivisto. Narrow sieves for parameterized paths and ... more >>>

Charanjit Jutla

Cristopher Moore, Alexander Russell

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

A simple extension of standard neural network models is introduced that

provides a model for neural computations that involve both firing rates and

firing correlations. Such extension appears to be useful since it has been

shown that firing correlations play a significant computational role in

many biological neural systems. Standard ...
more >>>

Alexander Razborov

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.

The aim of this note is to present a simplified version of his proof.

Noam Ta-Shma

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

more >>>Lieuwe Vinkhuijzen, André Deutz

In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if $\text{QMA}=\text{PP}$ then $\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using ... more >>>

Holger Dell

Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a simple proof of this result.

An AND-compression is ... more >>>

Halley Goldberg, Valentine Kabanets

We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in ... more >>>

Jakob Nordström

We present a greatly simplified proof of the length-space

trade-off result for resolution in Hertel and Pitassi (2007), and

also prove a couple of other theorems in the same vein. We point

out two important ingredients needed for our proofs to work, and

discuss possible conclusions to be drawn regarding ...
more >>>

Ankur Moitra

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m \times n$ is at most $r$ which runs in time $(nm)^{O(r^2)}$. This is the first exact algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

Eli Ben-Sasson, Jakob Nordström

The k-DNF resolution proof systems are a family of systems indexed by

the integer k, where the kth member is restricted to operating with

formulas in disjunctive normal form with all terms of bounded arity k

(k-DNF formulas). This family was introduced in [Krajicek 2001] as an

extension of the ...
more >>>

Xinyu Wu

After presentations of the oracle separation of BQP and PH result by Raz and Tal [ECCC TR18-107], several people

(e.g. Ryan O’Donnell, James Lee, Avishay Tal) suggested that the proof may be simplified by

stochastic calculus. In this short note, we describe such a simplification.

Ilya Volkovich

In the seminal work of \cite{Babai85}, Babai have introduced \emph{Arthur-Merlin Protocols} and in particular the complexity classes $MA$ and $AM$ as randomized extensions of the class $NP$. While it is easy to see that $NP \subseteq MA \subseteq AM$, it has been a long standing open question whether these classes ... more >>>

Bjørn Kjos-Hanssen

We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event $\mathcal A$ such that if $X\in\mathcal A$ then $X$ has an infinite ... more >>>

Ran Raz

Reason: This paper has been remove on the author's behalf. Please note that TR10-142 is the corrected version.

Ran Raz, Ricky Rosen

The parallel repetition theorem states that for any Two

Prover Game with value at most $1-\epsilon$ (for $\epsilon<1/2$),

the value of the game repeated $n$ times in parallel is at most

$(1-\epsilon^3)^{\Omega(n/s)}$, where $s$ is the length of the

answers of the two provers. For Projection

Games, the bound on ...
more >>>

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a ... more >>>

Marcel Dall'Agnol, Tom Gur, Oded Lachish

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 ... more >>>

Cassio P. de Campos, Georgios Stamoulis, Dennis Weyland

Weighted counting problems are a natural generalization of counting problems where a weight is associated with every computational path and the goal is to compute the sum of the weights of all paths (instead of computing the number of accepting paths). We present a structured view on weighted counting by ... more >>>

Nader Bshouty

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning

algorithm for polynomial size

DNF using equivalence queries only. In particular, DNF

is PAC-learnable in subexponential time under any distribution.

This is the first subexponential time

PAC-learning algorithm for DNF under any distribution.

Stanislav Zak

Branching programs (b.p.s) or binary decision diagrams are a

general graph-based model of sequential computation. The b.p.s of

polynomial size are a nonuniform counterpart of LOG. Lower bounds

for different kinds of restricted b.p.s are intensively

investigated. The restrictions based on the number of tests of

more >>>

Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

Shalev Ben-David

We construct a total Boolean function $f$ satisfying

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

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

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

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

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

but does not ...
more >>>

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

We consider arithmetic formulas consisting of alternating layers of addition $(+)$ and multiplication $(\times)$ gates such that the fanin of all the gates in any fixed layer is the same. Such a formula $\Phi$ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree ... more >>>

Theodoros Papamakarios

We show a quadratic separation between resolution and cut-free sequent calculus width. We use this gap to get, for the first time, first, a super-polynomial separation between resolution and cut-free sequent calculus for refuting CNF formulas, and secondly, a quadratic separation between resolution width and monomial space in polynomial calculus ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We show an $\widetilde{\Omega}(n^{2.5})$ lower bound for general depth four arithmetic circuits computing an explicit $n$-variate degree $\Theta(n)$ multilinear polynomial over any field of characteristic zero. To our knowledge, and as stated in the survey by Shpilka and Yehudayoff (FnT-TCS, 2010), no super-quadratic lower bound was known for depth four ... more >>>

Stephen Cook, Bruce Kapron

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

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

Dieter van Melkebeek

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

Andreas Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi

Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness perspectives, with emphasis on new techniques and potential future research directions.

more >>>Clement Canonne

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

Dmytro Gavinsky, Shachar Lovett, Michael Saks, Srikanth Srinivasan

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_1,\ldots,Y_r$ are arbitrary Boolean functions of independent random variables $X_1,\ldots,X_m$, modulo a restriction that every $X_i$ influences at most $k$ of the variables $Y_1,\ldots,Y_r$.

more >>>Ron Rothblum

Trapdoor permutations (TDPs) are among the most widely studied

building blocks of cryptography. Despite the extensive body of

work that has been dedicated to their study, in many setting and

applications (enhanced) trapdoor permutations behave

unexpectedly. In particular, a TDP may become easy to invert when

the inverter is given ...
more >>>

Oded Goldreich, Brendan Juba, Madhu Sudan

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

Venkatesan Guruswami, Daniel Lewin and Madhu Sudan, Luca Trevisan

It is known that there exists a PCP characterization of NP

where the verifier makes 3 queries and has a {\em one-sided}

error that is bounded away from 1; and also that 2 queries

do not suffice for such a characterization. Thus PCPs with

3 ...
more >>>

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

Iftach Haitner, Yonatan Karidi-Heller

In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83],

the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate ...
more >>>

Andris Ambainis, Krisjanis Prusis

Sensitivity, certificate complexity and block sensitivity are widely used Boolean function complexity measures. A longstanding open problem, proposed by Nisan and Szegedy, is whether sensitivity and block sensitivity are polynomially related. Motivated by the constructions of functions which achieve the largest known separations, we study the relation between 1-certificate complexity ... more >>>

Itay Berman, Iftach Haitner, Eliad Tsfadia

Parallel repetition is known to reduce the soundness error of some special cases of interactive arguments: three-message protocols and public-coin protocols. However, it does not do so in the general case.

Haitner [FOCS '09, SiCOMP '13] presented a simple method for transforming any interactive argument $\pi$ into a slightly modified ... more >>>

Masaki Yamamoto

In [IPL2005],

Frandsen and Miltersen improved bounds on the circuit size $L(n)$ of the hardest Boolean function on $n$ input bits:

for some constant $c>0$:

\[

\left(1+\frac{\log n}{n}-\frac{c}{n}\right)

\frac{2^n}{n}

\leq

L(n)

\leq

\left(1+3\frac{\log n}{n}+\frac{c}{n}\right)

\frac{2^n}{n}.

\]

In this note,

we announce a modest ...
more >>>

Ran Raz

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

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

Henning Fernau

In this paper, we show how to systematically

improve on parameterized algorithms and their

analysis, focusing on search-tree based algorithms

for d-Hitting Set, especially for d=3.

We concentrate on algorithms which are easy to implement,

in contrast with the highly sophisticated algorithms

which have been elsewhere designed to ...
more >>>

Neil Thapen

We describe a family of CNF formulas in $n$ variables, with small initial width, which have polynomial length resolution refutations. By a result of Ben-Sasson and Wigderson it follows that they must also have narrow resolution refutations, of width $O(\sqrt {n \log n})$. We show that, for our formulas, this ... more >>>

Agostino Capponi

Communication complexity is concerned with the question: how much information do the participants of a communication system need to exchange in order to perform certain tasks? The minimum number of bits that must be communicated is the deterministic communication complexity of $f$. This complexity measure was introduced by Yao \cite{1} ... more >>>

Ran Canetti

Building on known definitions, we present a unified general framework for

defining and analyzing security of cryptographic protocols. The framework

allows specifying the security requirements of a large number of

cryptographic tasks, such as signature, encryption, authentication, key

exchange, commitment, oblivious transfer, zero-knowledge, secret sharing,

general function evaluation, and ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira

The study of the interplay between the testability of properties of Boolean functions and the invariances acting on their domain which preserve the property was initiated by Kaufman and Sudan (STOC 2008). Invariance with respect to F_2-linear transformations is arguably the most common symmetry exhibited by natural properties of Boolean ... more >>>

Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh

The advent of data science has spurred interest in estimating properties of discrete distributions over large alphabets. Fundamental symmetric properties such as support size, support coverage, entropy, and proximity to uniformity, received most attention, with each property estimated using a different technique and often intricate analysis tools.

Motivated by the ... more >>>

Andreas Krebs, Nutan Limaye, Michael Ludwig

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

Colin Jia Zheng, Salil Vadhan

We present a new, more constructive proof of von Neumann's Min-Max Theorem for two-player zero-sum game --- specifically, an algorithm that builds a near-optimal mixed strategy for the second player from several best-responses of the second player to mixed strategies of the first player. The algorithm extends previous work of ... more >>>

Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Lucier Brendan, Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as $MPH$ (Maximum over Positive Hypergraphs).

Levels of the hierarchy correspond to the degree of complementarity in a given function.

The highest level of the hierarchy, $MPH$-$m$ (where $m$ is the total number of items) captures all ...
more >>>

Kooshiar Azimian, Javad Mohajeri, Mahmoud Salmasizadeh, Siamak Fayyaz

In this paper, firstly we propose two new concepts concerning the notion of key escrow encryption schemes: provable partiality and independency. Roughly speaking we say that a scheme has provable partiality if existing polynomial time algorithm for recovering the secret knowing escrowed information implies a polynomial time algorithm that can ... more >>>

Beate Bollig

Branching programs are a well-established computation

model for boolean functions, especially read-once

branching programs (BP1s) have been studied intensively.

A very simple function $f$ in $n^2$ variables is

exhibited such that both the function $f$ and its negation

$\neg f$ can be computed by $\Sigma^3_p$-circuits,

the ...
more >>>

Alessandro Chiesa, Michael Forbes, Nicholas Spooner

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

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

Thomas Watson

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

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

C. Seshadhri, Deeparnab Chakrabarty

Given oracle access to a Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$, we design a randomized tester that takes as input a parameter $\eps>0$, and outputs {\sf Yes} if the function is monotone, and outputs {\sf No} with probability $>2/3$, if the function is $\eps$-far from monotone. That is, $f$ needs to ... more >>>

Elad Haramaty, Noga Ron-Zewi, Madhu Sudan

In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of "affine-invariant'' codes. Affine-invariant codes are codes whose coordinates are associated with a vector space and are invariant under affine transformations of the coordinate space. Affine-invariant linear codes ... more >>>

Emanuele Viola

We prove that for every distribution $D$ on $n$ bits with Shannon

entropy $\ge n-a$ at most $O(2^{d}a\log^{d+1}g)/\gamma{}^{5}$ of

the bits $D_{i}$ can be predicted with advantage $\gamma$ by an

AC$^{0}$ circuit of size $g$ and depth $d$ that is a function of

all the bits of $D$ except $D_{i}$. ...
more >>>

Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal

Minimum Circuit Size Problem (MCSP) asks to decide if a given truth table of an $n$-variate boolean function has circuit complexity less than a given parameter $s$. We prove that MCSP is hard for constant-depth circuits with mod $p$ gates, for any prime $p\geq 2$ (the circuit class $AC^0[p])$. Namely, ... more >>>

Claus-Peter Schnorr

Given an LLL-basis $B$ of dimension $n= hk$ we accelerate slide-reduction with blocksize $k$ to run under a reasonable assjmption in \

$\frac1{6} \, n^2 h \,\log_{1+\varepsilon} \, \alpha $ \

local SVP-computations in dimension $k$, where $\alpha \ge \frac 43$

measures the quality of the ...
more >>>

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

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

Elad Hazan, C. Seshadhri

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of testing monotonicity

of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention

recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester

of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence

of $f$. We give an adaptive tester whose running ...
more >>>

Amit Deshpande, Santosh Vempala

We prove that any real matrix $A$ contains a subset of at most

$4k/\eps + 2k \log(k+1)$ rows whose span ``contains" a matrix of

rank at most $k$ with error only $(1+\eps)$ times the error of the

best rank-$k$ approximation of $A$. This leads to an algorithm to

find such ...
more >>>

Richard Beigel, William Gasarch, Ming Li, Louxin Zhang

We demonstrate the use of Kolmogorov complexity in average case

analysis of algorithms through a classical example: adding two $n$-bit

numbers in $\ceiling{\log_2{n}}+2$ steps on average. We simplify the

analysis of Burks, Goldstine, and von Neumann in 1946 and

(in more complete forms) of Briley and of Schay.

Xi Chen, Igor Carboni Oliveira, Rocco Servedio

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

Daniel Dewey

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>

Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov

$\mathbf{Separations:}$ We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite ... more >>>

Scott Aaronson, Andrew Drucker

We study the power of classical and quantum algorithms equipped with nonuniform advice, in the form of a coin whose bias encodes useful information. This question takes on particular importance in the quantum case, due to a surprising result that we prove: a quantum finite automaton with just two states ... more >>>

Thomas Watson

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $D$ that is $\delta$-dense in a distribution that is ... more >>>

Eli Ben-Sasson, Swastik Kopparty

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>

Xuangui Huang, Peter Ivanov, Emanuele Viola

We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.

Our construction is ...
more >>>

Jean Bourgain, Zeev Dvir, Ethan Leeman

We describe a construction of explicit affine extractors over large finite fields with exponentially small error and linear output length. Our construction relies on a deep theorem of Deligne giving tight estimates for exponential sums over smooth varieties in high dimensions.

more >>>Neeraj Kayal

An $m$-variate polynomial $f$ is said to be an affine projection of some $n$-variate polynomial $g$ if there exists an $n \times m$ matrix $A$ and an $n$-dimensional vector $b$ such that $f(x) = g(A x + b)$. In other words, if $f$ can be obtained by replacing each variable ... more >>>

Amir Shpilka

In this paper we introduce a new model for computing=20

polynomials - a depth 2 circuit with a symmetric gate at the top=20

and plus gates at the bottom, i.e the circuit computes a=20

symmetric function in linear functions -

$S_{m}^{d}(\ell_1,\ell_2,...,\ell_m)$ ($S_{m}^{d}$ is the $d$'th=20

elementary symmetric polynomial in $m$ ...
more >>>

Baris Aydinlioglu, Eric Bach

We strengthen existing evidence for the so-called "algebrization barrier". Algebrization --- short for algebraic relativization --- was introduced by Aaronson and Wigderson (AW) in order to characterize proofs involving arithmetization, simulation, and other "current techniques". However, unlike relativization, eligible statements under this notion do not seem to have basic closure ... more >>>

Divesh Aggarwal, Kaave Hosseini, Shachar Lovett

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

Aloni Cohen, Shafi Goldwasser, Vinod Vaikuntanathan

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

Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker

Aggregates are a computational model similar to circuits, but the

underlying graph is not necessarily acyclic. Logspace-uniform

polynomial-size aggregates decide exactly the languages in PSPACE;

without uniformity condition they decide the languages in

PSPACE/poly. As a measure of similarity to boolean circuits we

introduce the parameter component size. We ...
more >>>

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\epsilon)$ of the examples, it is $\mathrm{NP}$-hard to find a halfspace that is correct on $(1/2+\epsilon)$ of the examples, for arbitrary constants $\epsilon ... more >>>

We consider learning on multi-layer neural nets with piecewise polynomial

activation functions and a fixed number k of numerical inputs. We exhibit

arbitrarily large network architectures for which efficient and provably

successful learning algorithms exist in the rather realistic refinement of

Valiant's model for probably approximately correct learning ("PAC-learning")

where ...
more >>>

Yotam Dikstein, Irit Dinur

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test.

Previous work has shown that high dimensional expansion ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

Daniel Král

Ordered binary decision diagrams (OBDDs) and parity ordered binary

decision diagrams have proved their importance as data structures

representing Boolean functions. In addition to parity OBDDs we study

their generalization which we call parity AOBDDs, give the algebraic

characterization theorem and compare their minimal size to the size

more >>>

Benny Applebaum, Shachar Lovett

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

Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most $k$ is Zariski-closed, an important property in ... more >>>

Zeyu Guo, Nitin Saxena, Amit Sinhababu

Testing whether a set $\mathbf{f}$ of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). The best complexity known is NP$^{\#\rm P}$ (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). ... more >>>

Ankit Gupta

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we ... more >>>

Robert Andrews

We show that lower bounds for explicit constant-variate polynomials over fields of characteristic $p > 0$ are sufficient to derandomize polynomial identity testing over fields of characteristic $p$. In this setting, existing work on hardness-randomness tradeoffs for polynomial identity testing requires either the characteristic to be sufficiently large or the ... more >>>

Malte Beecken, Johannes Mittmann, Nitin Saxena

Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. Polynomials $\{f_1,\ldots, f_m\} \subset \mathbb{F}[x_1,\ldots, x_n]$ are called algebraically independent if there is no non-zero polynomial $F$ such that $F(f_1, \ldots, f_m) = 0$. The transcendence degree, $\mbox{trdeg}\{f_1,\ldots, f_m\}$, is the maximal ... more >>>

Johannes Mittmann, Nitin Saxena, Peter Scheiblechner

A set of multivariate polynomials, over a field of zero or large characteristic, can be tested for algebraic independence by the well-known Jacobian criterion. For fields of other characteristic $p>0$, there is no analogous characterization known. In this paper we give the first such criterion. Essentially, it boils down to ... more >>>

Rafail Ostrovsky, William Skeith

In cryptography, there has been tremendous success in building

primitives out of homomorphic semantically-secure encryption

schemes, using homomorphic properties in a black-box way. A few

notable examples of such primitives include items like private

information retrieval schemes and collision-resistant hash functions. In this paper, we illustrate a general

methodology for ...
more >>>

Toniann Pitassi, Iddo Tzameret

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

Dima Grigoriev, Edward Hirsch

We introduce two algebraic propositional proof systems F-NS

and F-PC. The main difference of our systems from (customary)

Nullstellensatz and Polynomial Calculus is that the polynomials

are represented as arbitrary formulas (rather than sums of

monomials). Short proofs of Tseitin's tautologies in the

constant-depth version of F-NS provide ...
more >>>

Iddo Tzameret

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege--yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analogue of Frege proofs, different from that given in Buss ... more >>>

Tali Kaufman, Madhu Sudan

We argue that the symmetries of a property being tested play a

central role in property testing. We support this assertion in the

context of algebraic functions, by examining properties of functions

mapping a vector space $\K^n$ over a field $\K$ to a subfield $\F$.

We consider $\F$-linear properties that ...
more >>>

Venkatesan Guruswami

This paper is concerned with a new family of error-correcting codes

based on algebraic curves over finite fields, and list decoding

algorithms for them. The basic goal in the subject of list decoding is

to construct error-correcting codes $C$ over some alphabet $\Sigma$

which have good rate $R$, and at ...
more >>>

Scott Aaronson, Avi Wigderson

Any proof of P!=NP will have to overcome two barriers: relativization

and natural proofs. Yet over the last decade, we have seen circuit

lower bounds (for example, that PP does not have linear-size circuits)

that overcome both barriers simultaneously. So the question arises of

whether there ...
more >>>

Oded Goldreich, Dana Ron

In this paper we consider two refined questions regarding

the query complexity of testing graph properties

in the adjacency matrix model.

The first question refers to the relation between adaptive

and non-adaptive testers, whereas the second question refers to

testability within complexity that

is inversely proportional to ...
more >>>

Michael Elberfeld, Andreas Jakoby, Till Tantau

An algorithmic meta theorem for a logic and a class $C$ of structures states that all problems expressible in this logic can be solved efficiently for inputs from $C$. The prime example is Courcelle's Theorem, which states that monadic second-order (MSO) definable problems are linear-time solvable on graphs of bounded ... more >>>

Stephan Kreutzer

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a

structural component, that is they are results of the form:

"every computational problem that can be formalised in a given logic L ...
more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree ... more >>>

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, A. Shankar

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found nu- merous applications in both math and computer ... more >>>

Bruno Pasqualotto Cavalar, Zhenjian Lu

Comparator circuits are a natural circuit model for studying bounded fan-out computation whose power sits between nondeterministic branching programs and general circuits. Despite having been studied for nearly three decades, the first superlinear lower bound against comparator circuits was proved only recently by Gál and Robere (ITCS 2020), who established ... more >>>

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

Neeraj Kayal

Given a multivariate polynomial f(x) in F[x] as an arithmetic circuit we would like to efficiently determine:

(i) [Identity Testing.] Is f(x) identically zero?

(ii) [Degree Computation.] Is the degree of the

polynomial f(x) at most a given integer d.

(iii) [Polynomial Equivalence.] Upto an ...
more >>>

Martin Furer, Shiva Prasad Kasiviswanathan

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting ... more >>>

Joshua Grochow, Youming Qiao

The isomorphism problem for groups given by multiplication tables (GpI) is well-known to be solvable in n^O(log n) time, but only recently has there been significant progress towards polynomial time. For example, in 2012 Babai et al. (ICALP 2012) gave a polynomial-time algorithm for groups with no abelian normal subgroups. ... more >>>

Shankar Kalyanaraman, Chris Umans

We study multiplayer games in which the participants have access to

only limited randomness. This constrains both the algorithms used to

compute equilibria (they should use little or no randomness) as well

as the mixed strategies that the participants are capable of playing

(these should be sparse). We frame algorithmic ...
more >>>

Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

We survey recent algorithms for the propositional

satisfiability problem, in particular algorithms

that have the best current worst-case upper bounds

on their complexity. We also discuss some related

issues: the derandomization of the algorithm of

Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani

Lemma, and random walk ...
more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We present a simple randomized algorithm for SAT and prove an upper

bound on its running time. Given a Boolean formula F in conjunctive

normal form, the algorithm finds a satisfying assignment for F

(if any) by repeating the following: Choose an assignment A at

random and ...
more >>>

Zhixiang Chen, Bin Fu, Yang Liu, Robert Schweller

This paper is our second step towards developing a theory of

testing monomials in multivariate polynomials. The central

question is to ask whether a polynomial represented by an

arithmetic circuit has some types of monomials in its sum-product

expansion. The complexity aspects of this problem and its variants

have been ...
more >>>

Nader Bshouty, Hanna Mazzawi

The coin weighing problem is the following: Given $n$ coins for which $m$ of them are counterfeit with the same weight. The problem is to detect the counterfeit coins with minimal number of weighings. This problem has many applications in compressed sensing, multiple access adder channels, etc. The problem was ... more >>>

Marco Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Circuit analysis algorithms such as learning, SAT, minimum circuit size, and compression imply circuit lower bounds. We show a generic implication in the opposite direction: natural properties (in the sense of Razborov and Rudich) imply randomized learning and compression algorithms. This is the first such implication outside of the derandomization ... more >>>

Igor Oliveira

Different techniques have been used to prove several transference theorems of the form "nontrivial algorithms for a circuit class C yield circuit lower bounds against C". In this survey we revisit many of these results. We discuss how circuit lower bounds can be obtained from derandomization, compression, learning, and satisfiability ... more >>>

Eric Blais, Clement Canonne, Tom Gur

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [BBM12], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method ... more >>>

Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

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

Noam Livne

In 1984 Levin put forward a suggestion for a theory of {\em average

case complexity}. In this theory a problem, called a {\em

distributional problem}, is defined as a pair consisting of a

decision problem and a probability distribution over the instances.

Introducing adequate notions of simple distributions and average

more >>>

Dorit Dor, Shay Halperin, Uri Zwick

Let G=(V,E) be an unweighted undirected graph on n vertices. A simple

argument shows that computing all distances in G with an additive

one-sided error of at most 1 is as hard as Boolean matrix

multiplication. Building on recent work of Aingworth, Chekuri and

Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time

more >>>

Uri Zwick

We present two new algorithms for solving the {\em All

Pairs Shortest Paths\/} (APSP) problem for weighted directed

graphs. Both algorithms use fast matrix multiplication algorithms.

The first algorithm

solves the APSP problem for weighted directed graphs in which the edge

weights are integers of small absolute value in ...
more >>>

Valentine Kabanets

Andreev et al.~\cite{ABCR97} give constructions of Boolean

functions (computable by polynomial-size circuits) that require large

read-once branching program (1-b.p.'s): a function in P that requires

1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial

time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a

function in LINSPACE ...
more >>>

Noga Alon, Oded Goldreich, Yishay Mansour

We say that a distribution over $\{0,1\}^n$

is almost $k$-wise independent

if its restriction to every $k$ coordinates results in a

distribution that is close to the uniform distribution.

A natural question regarding almost $k$-wise independent

distributions is how close they are to some $k$-wise

independent distribution. We show ...
more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

Olivier Powell

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... more >>>

morris yau

In "An Almost Cubic Lower Bound for $\sum\prod\sum$ circuits in VP", [BLS16] present an infinite family of polynomials, $\{P_n\}_{n \in \mathbb{Z}^+}$, with $P_n$

on $N = \Theta(n polylog(n))$

variables with degree $N$ being in VP such that every

$\sum\prod\sum$ circuit computing $P_n$ is of size $\Omega\big(\frac{N^3}{2^{\sqrt{\log N}}}\big)$.

We ...
more >>>

Shachar Lovett, Sasha Sodin

It is well known that $\R^N$ has subspaces of dimension

proportional to $N$ on which the $\ell_1$ norm is equivalent to the

$\ell_2$ norm; however, no explicit constructions are known.

Extending earlier work by Artstein--Avidan and Milman, we prove that

such a subspace can be generated using $O(N)$ random bits.

Venkatesan Guruswami, James R. Lee, Alexander Razborov

We give an explicit (in particular, deterministic polynomial time)

construction of subspaces $X

\subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,

$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$

If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits

and ...
more >>>

Noga Alon, Shachar Lovett

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

Charanjit Jutla

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not

be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of

such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.

Canetti et ...
more >>>

Raghu Meka

The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known constructions of linear embeddings that satisfy the Johnson-Lindenstrauss property involve randomness. We address the question of explicitly constructing such embedding families and provide a construction ... more >>>

Sai Sandeep

Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. ... more >>>

Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Zhao Song, Huacheng Yu

We give an almost quadratic $n^{2-o(1)}$ lower bound on the space consumption of any $o(\sqrt{\log n})$-pass streaming algorithm solving the (directed) $s$-$t$ reachability problem. This means that any such algorithm must essentially store the entire graph. As corollaries, we obtain almost quadratic space lower bounds for additional fundamental problems, including ... more >>>

Nader Bshouty

We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Classes, such as $k$-Junta, $k$-Linear Function, $s$-Term DNF, $s$-Term Monotone DNF, $r$-DNF, Decision List, $r$-Decision List, size-$s$ Decision Tree, size-$s$ Boolean Formula, size-$s$ Branching ... more >>>

Daniele Micciancio

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

Andris Ambainis

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

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

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

Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov

We show that the size of any regular resolution refutation of Tseitin formula $T(G,c)$ based on a graph $G$ is at least $2^{\Omega(tw(G)/\log n)}$, where $n$ is the number of vertices in $G$ and $tw(G)$ is the treewidth of $G$. For constant degree graphs there is known upper bound $2^{O(tw(G))}$ ... more >>>

Lijie Chen, Xin Lyu, Ryan Williams

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>

Pasin Manurangsi

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., ... more >>>

Krishnamoorthy Dinesh, Jayalal Sarma

The well-known Sensitivity Conjecture regarding combinatorial complexity measures on Boolean functions states that for any Boolean function $f:\{0,1\}^n \to \{0,1\}$, block sensitivity of $f$ is polynomially related to sensitivity of $f$ (denoted by $\mathbf{sens}(f)$). From the complexity theory side, the XOR Log-Rank Conjecture states that for any Boolean function, $f:\{0,1\}^n ... more >>>

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

Robert Robere, Jeroen Zuiddam

We study the amortized circuit complexity of boolean functions.

Given a circuit model $\mathcal{F}$ and a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, the $\mathcal{F}$-amortized circuit complexity is defined to be the size of the smallest circuit that outputs $m$ copies of $f$ (evaluated on the same input), ...
more >>>

Omri Weinstein, Huacheng Yu

This paper develops a new technique for proving amortized, randomized cell-probe lower bounds on dynamic

data structure problems. We introduce a new randomized nondeterministic four-party communication model

that enables "accelerated", error-preserving simulations of dynamic data structures.

We use this technique to prove an $\Omega(n\left(\log n/\log\log n\right)^2)$ cell-probe ... more >>>

Ofer Grossman, Dana Moshkovitz

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

The ... more >>>

Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

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

Thomas Watson

We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our ... more >>>

Eric Allender, Michal Koucky

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>

Mario Szegedy

Mario Szegedy

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

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

more >>>

Diptarka Chakraborty, Raghunath Tewari

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

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f:\{0,1\}^n \to \{0,1\}$ the tester makes $O(n \log(n)/\epsilon)$ adaptive queries to the function. The tester always accepts a unate function, and rejects with probability at least 0.9 any function that is $\epsilon$-far from being unate.

more >>>

Young Ko, Omri Weinstein

In 2010, Patrascu proposed a dynamic set-disjointness problem, known as the Multiphase problem, as a candidate for proving $polynomial$ lower bounds on the operational time of dynamic data structures. Patrascu conjectured that any data structure for the Multiphase problem must make $n^\epsilon$ cell-probes in either the update or query phase, ... more >>>

Clement Canonne, Tom Gur

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

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

For a {0,1}-valued matrix $M$ let CC($M$) denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC($M$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>

Christoph Meinel, Anna Slobodova

Reducibility concepts are fundamental in complexity theory.

Usually, they are defined as follows: A problem P is reducible

to a problem S if P can be computed using a program or device

for S as a subroutine. However, in the case of such restricted

models as ...
more >>>

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg

We obtain a characterization of feasible, Bayesian, multi-item multi-bidder mechanisms with independent, additive bidders as distributions over hierarchical mechanisms. Combined with cyclic-monotonicity our results provide a complete characterization of feasible, Bayesian Incentive Compatible mechanisms for this setting.

Our characterization is enabled by a novel, constructive proof of Border's theorem [Border ... more >>>

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

In this note, we prove that there is an explicit polynomial in VP such that any $\Sigma\Pi\Sigma$ arithmetic circuit computing it must have size at least $n^{3-o(1)}$. Up to $n^{o(1)}$ factors, this strengthens a recent result of Kayal, Saha and Tavenas (ICALP 2016) which gives a polynomial in VNP with ... more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

We show an $\Omega \left(\frac{n^3}{(\ln n)^2}\right)$ lower bound on the size of any depth three ($\SPS$) arithmetic circuit computing an explicit multilinear polynomial in $n$ variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson.

more >>>Nitin Saxena, C. Seshadhri

We show that the rank of a depth-3 circuit (over any field) that is simple,

minimal and zero is at most O(k^3\log d). The previous best rank bound known was

2^{O(k^2)}(\log d)^{k-2} by Dvir and Shpilka (STOC 2005).

This almost resolves the rank question first posed by ...
more >>>

Mrinal Kumar, Ben Lee Volk

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

Roei Tell

We provide an alternative proof for a known result stating that $\Omega(k)$ queries are needed to test $k$-sparse linear Boolean functions. Similar to the approach of Blais and Kane (2012), we reduce the proof to the analysis of Hamming weights of vectors in affi ne subspaces of the Boolean hypercube. ... more >>>

Dana Moshkovitz

We show a non-inductive proof of the Schwartz-Zippel lemma. The lemma bounds the number of zeros of a multivariate low degree polynomial over a finite field.

more >>>Oliver Kullmann

A basic property of minimally unsatisfiable clause-sets F is that

c(F) >= n(F) + 1 holds, where c(F) is the number of clauses, and

n(F) the number of variables. Let MUSAT(k) be the class of minimally

unsatisfiable clause-sets F with c(F) <= n(F) + k.

Poly-time decision algorithms are known ... more >>>

Tomoyuki Yamakami, Harumichi Nishimura

Quantum finite automata have been studied intensively since

their introduction in late 1990s as a natural model of a

quantum computer with finite-dimensional quantum memory space.

This paper seeks their direct application

to interactive proof systems in which a mighty quantum prover

communicates with a ...
more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Dana Moshkovitz

The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in ... more >>>

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a

given graph $G$ such that the maximum difference between the numbers

of adjacent vertices is minimal. The problem has a long history and

is known to be NP-complete Papadimitriou [Pa76]. Only few special

cases ...
more >>>

André Lanka, Andreas Goerdt

Assuming 3-SAT formulas are hard to refute

on average, Feige showed some approximation hardness

results for several problems like min bisection, dense

$k$-subgraph, max bipartite clique and the 2-catalog segmentation

problem. We show a similar result for

max bipartite clique, but under the assumption, 4-SAT formulas

are hard to refute ...
more >>>

Benjamin Rossman, Rocco Servedio, Li-Yang Tan

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

Johan Håstad

We extend the recent hierarchy results of Rossman, Servedio and

Tan \cite{rst15} to any $d \leq \frac {c \log n}{\log {\log n}}$

for an explicit constant $c$.

To be more precise, we prove that for any such $d$ there is a function

$F_d$ that is computable by a read-once formula ...
more >>>

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

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

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

Rüdiger Reischuk, Thomas Zeugmann

A new algorithm for learning one-variable pattern languages from positive data

is proposed and analyzed with respect to its average-case behavior.

We consider the total learning time that takes into account all

operations till convergence to a correct hypothesis is achieved.

For almost all meaningful distributions

defining how ...
more >>>

Zhenjian Lu, Igor Carboni Oliveira

A probabilistic representation of a string $x \in \{0,1\}^n$ is given by the code of a randomized algorithm that outputs $x$ with high probability [Oliveira, ICALP 2019]. We employ probabilistic representations to establish the first unconditional Coding Theorem in time-bounded Kolmogorov complexity. More precisely, we show that if a distribution ... more >>>

Joe Kilian, Erez Petrank

We consider noninteractive zero-knowledge proofs in the shared random

string model proposed by Blum, Feldman and Micali \cite{bfm}. Until

recently there was a sizable polynomial gap between the most

efficient noninteractive proofs for {\sf NP} based on general

complexity assumptions \cite{fls} versus those based on specific

algebraic assumptions \cite{Da}. ...
more >>>

Or Meir

One of the important challenges in circuit complexity is proving strong

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

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

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

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

more >>>

Noga Alon, Oded Schwartz, Asaf Shapira

We describe a short and easy to analyze construction of

constant-degree expanders. The construction relies on the

replacement-product, which we analyze using an elementary

combinatorial argument. The construction applies the replacement

product (only twice!) to turn the Cayley expanders of \cite{AR},

whose degree is polylog n, into constant degree

expanders.

Evgeny Demenkov, Alexander Kulikov

A Boolean function $f \colon \mathbb{F}^n_2 \rightarrow \mathbb{F}_2$ is called an affine disperser for sources of dimension $d$, if $f$ is not constant on any affine subspace of $\mathbb{F}^n_2$ of dimension at least $d$. Recently Ben-Sasson and Kopparty gave an explicit construction of an affine disperser for $d=o(n)$. The main ... more >>>

Shachar Lovett

Recently there has been much interest in polynomial threshold functions in the context of learning theory, structural results and pseudorandomness. A crucial ingredient in these works is the understanding of the distribution of low-degree multivariate polynomials evaluated over normally distributed inputs. In particular, the two important properties are exponential tail ... more >>>

Nikolay Vereshchagin

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,

we usually do not specify how to encode instances by binary strings.

This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$''

more >>>

Tom Gur, Igor Shinkar

A (k,\eps)-non-malleable extractor is a function nmExt : {0,1}^n x {0,1}^d -> {0,1} that takes two inputs, a weak source X~{0,1}^n of min-entropy k and an independent uniform seed s in {0,1}^d, and outputs a bit nmExt(X, s) that is \eps-close to uniform, even given the seed s and the ... more >>>

Venkatesan Guruswami, Ameya Velingker

We prove a lower estimate on the increase in entropy when two copies of a conditional random variable $X | Y$, with $X$ supported on $\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$. Specifically, given two i.i.d. copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of random variables $(X,Y)$, with $X$ ... more >>>

Nikolay Vereshchagin

We present a simplified proof of Solovay-Calude-Coles theorem

stating that there is an enumerable undecidable set with the

following property: prefix

complexity of its initial segment of length n is bounded by prefix

complexity of n (up to an additive constant).

Luca Trevisan

Cryan and Miltersen recently considered the question

of whether there can be a pseudorandom generator in

NC0, that is, a pseudorandom generator such that every

bit of the output depends on a constant number k of bits

of the seed. They show that for k=3 there ...
more >>>

Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

Jan Krajicek

We prove an exponential lower bound on the size of proofs

in the proof system operating with ordered binary decision diagrams

introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound

applies to semantic derivations operating with sets defined by OBDDs.

We do not assume ...
more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Agrawal and Vinay (FOCS 2008) have recently shown that an exponential lower bound for depth four homogeneous circuits with bottom layer of $\times$ gates having sublinear fanin translates to an exponential lower bound for a general arithmetic circuit computing the permanent. Motivated by this, we examine the complexity of computing ... more >>>

Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan

We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas. That is, we give

an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with $0, 1$-coefficients such that

for any representation of ...
more >>>

Mrinal Kumar, Ramprasad Saptharishi

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

Neeraj Kayal

In this work we consider representations of multivariate polynomials in $F[x]$ of the form $ f(x) = Q_1(x)^{e_1} + Q_2(x)^{e_2} + ... + Q_s(x)^{e_s},$ where the $e_i$'s are positive integers and the $Q_i$'s are arbitary multivariate polynomials of bounded degree. We give an explicit $n$-variate polynomial $f$ of degree $n$ ... more >>>

Dima Grigoriev, Marek Karpinski, A. C. Yao

We prove an exponential lower bound on the size of any

fixed-degree algebraic decision tree for solving MAX, the

problem of finding the maximum of $n$ real numbers. This

complements the $n-1$ lower bound of Rabin \cite{R72} on

the depth of ...
more >>>

Omar Alrabiah, Venkatesan Guruswami

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a ... more >>>

Jan Krajicek, Pavel Pudlak, Alan Woods

We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$

$\epsilon_d>0,$ on the length of proofs of an explicit sequence of

tautologies, based on the Pigeonhole Principle, in proof systems

using formulas of depth $d,$ for any constant $d.$ This is the

largest lower bound for the strongest proof system, for which ...
more >>>

Tom Gur, Ron D. Rothblum, Yang P. Liu

Non-interactive proofs of proximity allow a sublinear-time verifier to check that

a given input is close to the language, given access to a short proof. Two natural

variants of such proof systems are MA-proofs of Proximity (MAP), in which the proof

is a function of the input only, and AM-proofs ...
more >>>

Michael Alekhnovich, Jan Johannsen, Alasdair Urquhart

This paper gives two distinct proofs of an exponential separation

between regular resolution and unrestricted resolution.

The previous best known separation between these systems was

quasi-polynomial.

Martin Schwarz

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

Philipp Hertel

Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and diagnosis problems. The main reason for the success is due to highly optimized algorithms for SAT based on resolution. The most successful of these ... more >>>

Anup Rao

A construction of Bourgain gave the first 2-source

extractor to break the min-entropy rate 1/2 barrier. In this note,

we write an exposition of his result, giving a high level way to view

his extractor construction.

We also include a proof of a generalization of Vazirani's XOR lemma

that seems ...
more >>>

Shachar Lovett

The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom ... more >>>

Zeev Dvir, Amir Shpilka

Mergers are functions that transform k (possibly dependent) random sources into a single random source, in a way that ensures that if one of the input sources has min-entropy rate $\delta$ then the output has min-entropy rate close to $\delta$. Mergers have proven to be a very useful tool in ... more >>>

Arkadev Chattopadhyay

Let m,q > 1 be two integers that are co-prime and A be any subset of Z_m. Let P be any multi-linear polynomial of degree d in n variables over Z_m. We show that the MOD_q boolean function on n variables has correlation at most exp(-\Omega(n/(m2^{m-1})^d)) with the boolean function ... more >>>

Boris Bukh, Venkatesan Guruswami

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

Zander Kelley

We prove a new derandomization of Håstad's switching lemma, showing how to efficiently generate restrictions satisfying the switching lemma for DNF or CNF formulas of size $m$ using only $\widetilde{O}(\log m)$ random bits. Derandomizations of the switching lemma have been useful in many works as a key building-block for constructing ... more >>>

Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari

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

... more >>>Andrew Drucker

"Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some $[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>>

Martin Sauerhoff

One of the great challenges of complexity theory is the problem of

analyzing the dependence of the complexity of Boolean functions on the

resources nondeterminism and randomness. So far, this problem could be

solved only for very few models of computation. For so-called

partitioned binary decision diagrams, which are a ...
more >>>

Benjamin Rossman

Previous work of the author [39] showed that the Homomorphism Preservation Theorem of classical model theory remains valid when its statement is restricted to finite structures. In this paper, we give a new proof of this result via a reduction to lower bounds in circuit complexity, specifically on the AC$^0$ ... more >>>

Nikos Leonardos

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>>

Evgeny Dantsin, Alexander Wolpert

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

Tong Qin, Osamu Watanabe

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

more >>>Edward Hirsch, Dmitry Itsykson

We assume the existence of a function f that is computable in polynomial time but its inverse function is not computable in randomized average-case polynomial time. The cryptographic setting is, however, different: even for a weak one-way function, every possible adversary should fail on a polynomial fraction of inputs. Nevertheless, ... more >>>

Mark Braverman, Ankur Moitra

We prove an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. There has been considerable recent interest in proving unconditional lower bounds against any linear program. Fiorini et al proved that there is no polynomial sized linear program for traveling salesman. ... more >>>

Mark Braverman, Omri Weinstein

We introduce a novel technique which enables two players to maintain an estimate of the internal information cost of their conversation in an online fashion without revealing much extra information. We use this construction to obtain new results about communication complexity and information-theoretically secure computation.

As a first corollary, ... more >>>

Prahladh Harsha, Adam Klivans, Raghu Meka

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly

chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$

formed by the intersection of $k$ halfspaces, we prove that

$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ...
more >>>

Andrei Krokhin, Jakub Opršal

The study of the complexity of the constraint satisfaction problem (CSP), centred around the Feder-Vardi Dichotomy Conjecture, has been very prominent in the last two decades. After a long concerted effort and many partial results, the Dichotomy Conjecture has been proved in 2017 independently by Bulatov and Zhuk.

At about ... more >>>

Yijia Chen, Martin Grohe

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

more >>>Manindra Agrawal, Eric Allender

We show that all sets complete for NC$^1$ under AC$^0$

reductions are isomorphic under AC$^0$-computable isomorphisms.

Although our proof does not generalize directly to other

complexity classes, we do show that, for all complexity classes C

closed under NC$^1$-computable many-one reductions, the sets ...
more >>>

Vladimir Trifonov

We present a deterministic O(log n log log n) space algorithm for

undirected s,t-connectivity. It is based on the deterministic EREW

algorithm of Chong and Lam (SODA 93) and uses the universal

exploration sequences for trees constructed by Kouck\'y (CCC 01).

Our result improves the O(log^{4/3} n) bound of Armoni ...
more >>>

Alexander Razborov, Sergey Yekhanin

A two server private information retrieval (PIR) scheme

allows a user U to retrieve the i-th bit of an

n-bit string x replicated between two servers while each

server individually learns no information about i. The main

parameter of interest in a PIR scheme is its communication

complexity, namely the ...
more >>>

Andrei Romashchenko, Marius Zimand

We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings

$x$ and $y$ is equal, up to logarithmic precision, to the length of the longest shared secret key that

two parties, one having $x$ and the complexity profile of the pair and the ...
more >>>

Meghal Gupta, Naren Manoj

Given query access to a monotone function $f\colon\{0,1\}^n\to\{0,1\}$ with certificate complexity $C(f)$ and an input $x^{\star}$, we design an algorithm that outputs a size-$C(f)$ subset of $x^{\star}$ certifying the value of $f(x^{\star})$. Our algorithm makes $O(C(f) \cdot \log n)$ queries to $f$, which matches the information-theoretic lower bound for this ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

For positive integers $n, d$, consider the hypergrid $[n]^d$ with the coordinate-wise product partial ordering denoted by $\prec$.

A function $f: [n]^d \mapsto \mathbb{N}$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$.

A function $f$ is $\varepsilon$-far from monotone if at least an $\varepsilon$-fraction of values must ...
more >>>

Amit Chakrabarti, Oded Regev

We prove an optimal $\Omega(n)$ lower bound on the randomized

communication complexity of the much-studied

Gap-Hamming-Distance problem. As a consequence, we

obtain essentially optimal multi-pass space lower bounds in the

data stream model for a number of fundamental problems, including

the estimation of frequency moments.

The Gap-Hamming-Distance problem is a ... more >>>

Amit Chakrabarti, Oded Regev

We consider the approximate nearest neighbour search problem on the

Hamming Cube $\b^d$. We show that a randomised cell probe algorithm that

uses polynomial storage and word size $d^{O(1)}$ requires a worst case

query time of $\Omega(\log\log d/\log\log\log d)$. The approximation

factor may be as loose as $2^{\log^{1-\eta}d}$ for any ...
more >>>

Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>

Nader Bshouty

A Boolean function $f:\{0,1\}^n\to \{0,1\}$ is $k$-linear if it returns the sum (over the binary field $F_2$) of $k$ coordinates of the input. In this paper, we study property testing of the classes $k$-Linear, the class of all $k$-linear functions, and $k$-Linear$^*$, the class $\cup_{j=0}^kj$-Linear.

We give a non-adaptive distribution-free ...
more >>>

C.P. Schnorr, Carsten Rössner

Ronald de Haan

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

Tayfun Pay, James Cox

We review some semantic and syntactic complexity classes that were introduced to better understand the relationship between complexity classes P and NP. We also define several new complexity classes, some of which are associated with Mersenne numbers, and show their location in the complexity hierarchy.

more >>>Alexander Razborov

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

Salil Vadhan

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist.

We establish several new characterizations of ZK, and use these characterizations to ... more >>>

Pavel Pudlak, Jiri Sgall

We prove an unexpected upper bound on a communication game proposed

by Jeff Edmonds and Russell Impagliazzo as an approach for

proving lower bounds for time-space tradeoffs for branching programs.

Our result is based on a generalization of a construction of Erdos,

Frankl and Rodl of a large 3-hypergraph ...
more >>>

Alex Samorodnitsky

Let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$ and let $q \ge 1$. We upper bound the $\ell_q$ norm of $T_{\epsilon} f$ by the average $\ell_q$ norm of conditional expectations of $f$, given sets of roughly ... more >>>

Michele Zito

We prove that, with high probability, the space complexity of refuting

a random unsatisfiable boolean formula in $k$-CNF on $n$

variables and $m = \Delta n$ clauses is

$O(n \cdot \Delta^{-\frac{1}{k-2}})$.

Gautam Kamath, Christos Tzamos

We investigate distribution testing with access to non-adaptive conditional samples.

In the conditional sampling model, the algorithm is given the following access to a distribution: it submits a query set $S$ to an oracle, which returns a sample from the distribution conditioned on being from $S$.

In the non-adaptive setting, ...
more >>>

Eduardo D. Sontag

We consider recurrent analog neural nets where the output of each

gate is subject to Gaussian noise, or any other common noise

distribution that is nonzero on a large set.

We show that many regular languages cannot be recognized by

networks of this type, and

more >>>

Günter Hotz, Gero Vierke, Bjoern Schieffer

In this paper the $R$-machines defined by Blum, Shub and Smale

are generalized by allowing infinite convergent computations.

The description of real numbers is infinite.

Therefore, considering arithmetic operations on real numbers should

also imply infinite computations on {\em analytic machines}.

We prove that $\R$-computable functions are $\Q$-analytic.

We show ...
more >>>

Zeev Dvir, Ran Raz

random sources into a single random source, in a way that ensures

that if one of the input sources has min-entropy rate $\delta$

then the output has min-entropy rate close to $\delta$. Mergers

have proven to be a very useful tool in ...
more >>>

Silas Richelson, Sourya Roy

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).

We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.

The problem of property testing $\mathcal{P}$ was introduced in ...
more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler

The central goal of data stream algorithms is to process massive streams of data using sublinear storage space. Motivated by work in the database community on outsourcing database and data stream processing, we ask whether the space usage of such algorithms can be further reduced by enlisting a more powerful ... more >>>

Oded Goldreich, David Zuckerman

We provide another proof of the Sipser--Lautemann Theorem

by which $BPP\subseteq MA$ ($\subseteq PH$).

The current proof is based on strong

results regarding the amplification of $BPP$, due to Zuckerman.

Given these results, the current proof is even simpler than previous ones.

Furthermore, extending the proof leads ...
more >>>

Frank Neumann, Carsten Witt

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

Amir Yehudayoff

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing ... more >>>

Adam Bouland, Scott Aaronson

In 1994, Reck et al. showed how to realize any linear-optical unitary transformation using a product of beamsplitters and phaseshifters. Here we show that any single beamsplitter that nontrivially mixes two modes, also densely generates the set of m by m unitary transformations (or orthogonal transformations, in the real case) ... more >>>

Raghav Kulkarni, Youming Qiao, Xiaoming Sun

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,

Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ...
more >>>

Boris Bukh, Karthik C. S., Bhargav Narayanan

In this paper, we show how one may (efficiently) construct two types of extremal combinatorial objects whose existence was previously conjectural.

(*) Panchromatic Graphs: For fixed integer k, a k-panchromatic graph is, roughly speaking, a balanced bipartite graph with one partition class equipartitioned into k colour classes in ...
more >>>

Beate Bollig, Ingo Wegener

Many BDD (binary decision diagram) models are motivated

by CAD applications and have led to complexity theoretical

problems and results. Motivated by applications in genetic

programming Krause, Savick\'y, and Wegener (1999) have shown

that for the inner product function IP$_n$ and the direct

storage access function DSA$_n$ ...
more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A constraint satisfaction problem (CSP), Max-CSP$({\cal F})$, is specified by a finite set of constraints ${\cal F} \subseteq \{[q]^k \to \{0,1\}\}$ for positive integers $q$ and $k$. An instance of the problem on $n$ variables is given by $m$ applications of constraints from ${\cal F}$ to subsequences of the $n$ ... more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

We give a polynomial time approximation scheme (PTAS) for dense

instances of the NEAREST CODEWORD problem.

Piotr Berman, Marek Karpinski

We prove that the problems of minimum bisection on k-uniform

hypergraphs are almost exactly as hard to approximate,

up to the factor k/3, as the problem of minimum bisection

on graphs. On a positive side, our argument gives also the

first approximation ...
more >>>

Jan Arpe, Bodo Manthey

Given a set of monomials, the Minimum AND-Circuit problem asks for a

circuit that computes these monomials using AND-gates of fan-in two and

being of minimum size. We prove that the problem is not polynomial time

approximable within a factor of less than 1.0051 unless P = NP, even if

more >>>

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>

Vikraman Arvind, Venkatesh Raman

We give a randomized approximation algorithm taking

$O(k^{O(k)}n^{b+O(1)})$ time to count the number of copies of a

$k$-vertex graph with treewidth at most $b$ in an $n$ vertex graph

$G$ with approximation ratio $1/k^{O(k)}$ and error probability

inverse exponential in $n$. This algorithm is based on ...
more >>>

Mark Bun, Justin Thaler

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are basic complexity measures of Boolean functions that arise in learning theory, communication complexity, and circuit complexity. Each of these measures might exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth two have polynomial complexity under the ... more >>>

Andrej Bogdanov

We give a new proof that the approximate degree of the AND function over $n$ inputs is $\Omega(\sqrt{n})$. Our proof extends to the notion of weighted degree, resolving a conjecture of Kamath and Vasudevan. As a consequence we confirm that the approximate degree of any read-once depth-2 De Morgan formula ... more >>>

Andrej Bogdanov, Nikhil Mande, Justin Thaler, Christopher Williamson

The $\epsilon$-approximate degree $\widetilde{\text{deg}}_\epsilon(f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $\epsilon$. The approximate degree of $f$ is at least $k$ iff there exists a pair of probability distributions, also known as a dual polynomial, that are perfectly ... more >>>

Xuangui Huang, Emanuele Viola

We prove that the Or function on $n$ bits can be point-wise approximated with error $\eps$ by a polynomial of degree $O(k)$ and weight $2^{O(n \log (1/\eps)/k)}$, for any $k \geq \sqrt{n \log 1/\eps}$. This result is tight for all $k$. Previous results were either not tight or had $\eps ... more >>>

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

Venkatesan Guruswami, Sai Sandeep

A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. This conjecture was couched in a broader setting by Aharoni and Zerbib who proposed a hypergraph version of this ... more >>>

Alexander A. Sherstov

Let A_1,...,A_n be events in a probability space. The

approximate inclusion-exclusion problem, due to Linial and

Nisan (1990), is to estimate Pr[A_1 OR ... OR A_n] given

Pr[AND_{i\in S}A_i] for all |S|<=k. Kahn et al. (1996) solve

this problem optimally for each k. We study the following more

general question: ...
more >>>

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.

The logarithm of the nonnegative rank is known to ...
more >>>

Jack H. Lutz, Brad Shutters

The Tile Assembly Model is a Turing universal model that Winfree introduced in order to study the nanoscale self-assembly of complex (typically aperiodic) DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant of the Cartesian plane with specially labeled tiles appearing at exactly the positions of points in ... more >>>

Talya Eden, Amit Levi, Dana Ron

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

Piotr Indyk, Reut Levi, Ronitt Rubinfeld

A discrete distribution $p$, over $[n]$, is a $k$-histogram if its probability distribution function can be

represented as a piece-wise constant function with $k$ pieces. Such a function

is

represented by a list of $k$ intervals and $k$ corresponding values. We consider

the following problem: given a collection of samples ...
more >>>

Oded Goldreich, Dana Ron

Inspired by Feige ({\em 36th STOC}, 2004),

we initiate a study of sublinear randomized algorithms

for approximating average parameters of a graph.

Specifically, we consider the average degree of a graph

and the average distance between pairs of vertices in a graph.

Since our focus is on sublinear algorithms, ...
more >>>

Eric Blais, Li-Yang Tan

We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function.

In the first direction, our main positive results are the first non-trivial universal upper bounds on ...
more >>>

Marek Karpinski

We present some of the recent results on computational complexity

of approximating bounded degree combinatorial optimization problems. In

particular, we present the best up to now known explicit nonapproximability

bounds on the very small degree optimization problems which are of

particular importance on the intermediate stages ...
more >>>

Venkatesan Guruswami, Yuan Zhou

A theorem of Håstad shows that for every constraint satisfaction problem (CSP) over a fixed size domain, instances where each variable appears in at most $O(1)$ constraints admit a non-trivial approximation algorithm, in the sense that one can beat (by an additive constant) the approximation ratio achieved by the naive ... more >>>

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

In the buy-at-bulk $k$-Steiner tree (or rent-or-buy

$k$-Steiner tree) problem we are given a graph $G(V,E)$ with a set

of terminals $T\subseteq V$ including a particular vertex $s$ called

the root, and an integer $k\leq |T|$. There are two cost functions

on the edges of $G$, a buy cost $b:E\longrightarrow ...
more >>>

Tobias Friedrich, Jun He, Nils Hebbinghaus, Frank Neumann, Carsten Witt

The main aim of randomized search heuristics is to produce good approximations of optimal solutions within a small amount of time. In contrast to numerous experimental results, there are only a few theoretical results on this subject.

We consider the approximation ability of randomized search for the class of ...
more >>>

Subhash Khot, Rishi Saket

This paper studies how well the standard LP relaxation approximates a $k$-ary constraint satisfaction problem (CSP) on label set $[L]$. We show that, assuming the Unique Games Conjecture, it achieves an approximation within $O(k^3\cdot \log L)$ of the optimal approximation factor. In particular we prove the following hardness result: let ... more >>>

Irit Dinur, Guy Kindler, Shmuel Safra

This paper shows finding the closest vector in a lattice

to be NP-hard to approximate to within any factor up to

$2^{(\log{n})^{1-\epsilon}}$ where

$\epsilon = (\log\log{n})^{-\alpha}$

and $\alpha$ is any positive constant $<{1\over 2}$.

Marek Karpinski, Alexander Zelikovsky

We study dense instances of several covering problems. An instance of

the set cover problem with $m$ sets is dense if there is $\epsilon>0$

such that any element belongs to at least $\epsilon m$ sets. We show

that the dense set cover problem can be approximated with ...
more >>>

Piotr Berman, Marek Karpinski, Yakov Nekrich

In this paper we present some new results on the approximate parallel

construction of Huffman codes. Our algorithm achieves linear work

and logarithmic time, provided that the initial set of elements

is sorted. This is the first parallel algorithm for that problem

with the optimal time and ...
more >>>

Peter Auer, Philip M. Long, Aravind Srinivasan

The PAC learning of rectangles has been studied because they have

been found experimentally to yield excellent hypotheses for several

applied learning problems. Also, pseudorandom sets for rectangles

have been actively studied recently because (i) they are a subproblem

common to the derandomization of depth-2 (DNF) ...
more >>>

Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma

Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear algebraic primitive with myriad applications in computer science. Of particular interest is the problem's space complexity as it constitutes the main route towards resolving the $\mathbf{BPL}$ vs. $\mathbf{L}$ problem. The seminal work by Saks and Zhou (FOCS 1995) ... more >>>

Gil Cohen, Dean Doron, Ori Sberlo

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>

Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson

We study constraint satisfaction problems on the domain $\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form $\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$ for some positive integer weights $w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>>

Andreas Björklund, Thore Husfeldt, Sanjeev Khanna

We investigate the hardness of approximating the longest path and

the longest cycle in directed graphs on $n$ vertices. We show that

neither of these two problems can be polynomial time approximated

within $n^{1-\epsilon}$ for any $\epsilon>0$ unless

$\text{P}=\text{NP}$. In particular, the result holds for

more >>>

Piotr Berman, Marek Karpinski

We consider the following optimization problem:

given a system of m linear equations in n variables over a certain field,

a feasible solution is any assignment of values to the variables, and the

minimized objective function is the number of equations that are not

satisfied. For ...
more >>>

Zhixiang Chen, Bin Fu

This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ polynomial.

We first prove ...
more >>>

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm ... more >>>

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

A model for parallel and distributed programs, the dynamic process graph (DPG),

is investigated under graph-theoretic and complexity aspects.

Such graphs embed constructors for parallel programs,

synchronization mechanisms as well as conditional branches.

They are capable of representing all possible executions of a

parallel or distributed program ...
more >>>

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

We show that given oracle access to a subroutine which

returns approximate closest vectors in a lattice, one may find in

polynomial-time approximate shortest vectors in a lattice.

The level of approximation is maintained; that is, for any function

$f$, the following holds:

Suppose that the subroutine, on input a ...
more >>>

Irit Dinur

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate

to within any factor up to $n^{1/\log\log n}$. This improves on the

best previous result \cite{ABSS} that showed quasi-NP-hardness for

smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant

$\epsilon>0$. We show a direct reduction from SAT to these

problems, that ...
more >>>

Alexander A. Sherstov

The approximate degree of a Boolean function $f$ is the least degree of a real polynomial

that approximates $f$ within $1/3$ at every point. We prove that the function $\bigwedge_{i=1}^{n}\bigvee_{j=1}^{n}x_{ij}$,

known as the AND-OR tree, has approximate degree $\Omega(n).$ This lower bound is tight

and closes a ...
more >>>

Mark Braverman, Young Kun Ko, Omri Weinstein

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game

initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.

We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social ... more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

We design a nonadaptive algorithm that, given a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. Furthermore, we show that for any constant $\kappa > ... more >>>

Mickey Brautbar, Alex Samorodnitsky

We consider the problem of approximating the entropy of a discrete distribution P on a domain of size q, given access to n independent samples from the distribution. It is known that n > q is necessary, in general, for a good additive estimate of the entropy. A problem of ... more >>>

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

We consider the problem of approximating the minmax value of a multiplayer game in strategic form. We argue that in 3-player games with 0-1 payoffs, approximating the minmax value within an additive constant smaller than $\xi/2$, where $\xi = \frac{3-\sqrt5}{2} \approx 0.382$, is not possible by a polynomial time algorithm. ... more >>>

Piotr Berman, Bhaskar DasGupta

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>>

Jin-Yi Cai, Ajay Nerurkar

Recently Ajtai showed that

to approximate the shortest lattice vector in the $l_2$-norm within a

factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large

constant $k$, is NP-hard under randomized reductions.

We improve this result to show that

to approximate a shortest lattice vector within a

factor $(1+ \mbox{dim}^{-\epsilon})$, for any

$\epsilon>0$, ...
more >>>

Piotr Berman, Bhaskar DasGupta, Marek Karpinski

We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

We present a c.k/2^k approximation algorithm for the Max k-CSP problem (where c > 0.44 is an absolute constant). This result improves the previously best known algorithm by Hast, which has an approximation guarantee of Omega(k/(2^k log k)). Our approximation guarantee matches the upper bound of Samorodnitsky and Trevisan up ... more >>>

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

The max-bisection problem is to find a partition of the vertices of a

graph into two equal size subsets that maximizes the number of edges with

endpoints in both subsets.

We obtain new improved approximation ratios for the max-bisection problem on

the low degree $k$-regular graphs for ...
more >>>

Luca Trevisan

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove existence of approximation schemes for instances of MAX-CUT with $\Omega(\frac{n^2}{\Delta})$ edges which work in $2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$ time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with $\Omega(\frac{n^2}{\operatorname{polylog} n})$ edges. The result depends on new sampling method for smoothed linear programs that ... more >>>

Meera Sitharam

We develop an analytic framework based on

linear approximation and point out how a number of complexity

related questions --

on circuit and communication

complexity lower bounds, as well as

pseudorandomness, learnability, and general combinatorics

of Boolean functions --

fit neatly into this framework. ...
more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

We study approximation hardness and satisfiability of bounded

occurrence uniform instances of SAT. Among other things, we prove

the inapproximability for SAT instances in which every clause has

exactly 3 literals and each variable occurs exactly 4 times,

and display an explicit ...
more >>>

Janka Chlebíková, Miroslav Chlebik

The paper contributes to the systematic study (started by Berman and

Karpinski) of explicit approximability lower bounds for small occurrence optimization

problems. We present parametrized reductions for some packing and

covering problems, including 3-Dimensional Matching, and prove the best

known inapproximability results even for highly restricted versions of ...
more >>>

Piotr Berman, Marek Karpinski

We consider bounded occurrence (degree) instances of a minimum

constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for

graphs. MIN-LIN2 is an optimization problem for a given system of linear

equations mod 2 to construct a solution that satisfies the minimum number

of them. E3-OCC-MIN-E3-LIN2 ...
more >>>

Marek Karpinski, Richard Schmied

We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott

We prove approximation hardness of short symmetric instances

of MAX-3SAT in which each literal occurs exactly twice, and

each clause is exactly of size 3. We display also an explicit

approximation lower bound for that problem. The bound two on

the number ...
more >>>

Lars Engebretsen, Marek Karpinski

The general asymmetric (and metric) TSP is known to be approximable

only to within an O(log n) factor, and is also known to be

approximable within a constant factor as soon as the metric is

bounded. In this paper we study the asymmetric and symmetric TSP

problems with bounded metrics ...
more >>>

Stasys Jukna, Hannes Seiwert

We develop general lower bound arguments for approximating tropical

(min,+) and (max,+) circuits, and use them to prove the

first non-trivial, even super-polynomial, lower bounds on the size

of such circuits approximating some explicit optimization

problems. In particular, these bounds show that the approximation

powers of pure dynamic programming algorithms ...
more >>>

Martin Sauerhoff

This paper deals with the number of monochromatic combinatorial

rectangles required to approximate a Boolean function on a constant

fraction of all inputs, where each rectangle may be defined with

respect to its own partition of the input variables. The main result

of the paper is that the number of ...
more >>>

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>>

Siu On Chan

We show optimal (up to constant factor) NP-hardness for Max-k-CSP over any domain,

whenever k is larger than the domain size. This follows from our main result concerning predicates

over abelian groups. We show that a predicate is approximation resistant if it contains a subgroup that

is ...
more >>>

Sangxia Huang

In this paper, we study the approximability of Max CSP($P$) where $P$ is a Boolean predicate. We prove that assuming Khot's $d$-to-1 Conjecture, if the set of accepting inputs of $P$ strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP($P$) better than ... more >>>

Per Austrin, Elchanan Mossel

We study the approximability of predicates on $k$ variables from a

domain $[q]$, and give a new sufficient condition for such predicates

to be approximation resistant under the Unique Games Conjecture.

Specifically, we show that a predicate $P$ is approximation resistant

if there exists a balanced pairwise independent distribution over

more >>>

Chandra Chekuri, Sanjeev Khanna

We present the first approximation schemes for minimizing weighted flow time

on a single machine with preemption. Our first result is an algorithm that

computes a $(1+\eps)$-approximate solution for any instance of weighted flow

time in $O(n^{O(\ln W \ln P/\eps^3)})$ time; here $P$ is the ratio ...
more >>>

Shahar Dobzinski, Noam Nisan

We consider computationally-efficient incentive-compatible

mechanisms that use the VCG payment scheme, and study how well they

can approximate the social welfare in auction settings. We obtain a

$2$-approximation for multi-unit auctions, and show that this is

best possible, even though from a purely computational perspective

an FPTAS exists. For combinatorial ...
more >>>

Matthias Krause, Petr Savicky, Ingo Wegener

Ordered binary decision diagrams (OBDDs) and their variants

are motivated by the need to represent Boolean functions

in applications. Research concerning these applications leads

also to problems and results interesting from theoretical

point of view. In this paper, methods from communication

complexity and ...
more >>>

Venkatesan Guruswami, Andrii Riazanov, Min Ye

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha > 0$. We construct, for any sufficiently small $\delta > 0$, binary linear codes of block length $O(1/\delta^{2+\alpha})$ and rate $I(W)-\delta$ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. ... more >>>

Emanuele Viola

Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\begin{itemize}

\item There are explicit $AC^0$ circuits of ...
more >>>

Clement Canonne

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

Guy Rothblum, Salil Vadhan

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla

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

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete

optimization problem, and argue that in many practical situations

only sufficiently stable instances are of interest. The question

then arises whether stable instances of NP--hard problems are

easier to solve. In particular, whether there exist algorithms

that solve correctly ...
more >>>

Eric Allender, Asa Goodwillie

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

more >>>Pranjal Dutta, Gorav Jindal, Anurag Pandey, Amit Sinhababu

Given polynomials $f,g,h\,\in \mathbb{F}[x_1,\ldots,x_n]$ such that $f=g/h$, where both $g$ and $h$ are computable by arithmetic circuits of size $s$, we show that $f$ can be computed by a circuit of size $\poly(s,\deg(h))$. This solves a special case of division elimination for high-degree circuits (Kaltofen'87 \& WACT'16). The result ... more >>>

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove

super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :

$\bullet$ As ... more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>

Mrinal Kumar, Shubhangi Saraf

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

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

Meena Mahajan, B. V. Raghavendra Rao

Functions in arithmetic NC1 are known to have equivalent constant

width polynomial degree circuits, but the converse containment is

unknown. In a partial answer to this question, we show that syntactic

multilinear circuits of constant width and polynomial degree can be

depth-reduced, though the resulting circuits need not be ...
more >>>

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

We show that, over $\mathbb{C}$, if an $n$-variate polynomial of degree $d = n^{O(1)}$ is computable by an arithmetic circuit of size $s$ (respectively by an algebraic branching program of size $s$) then it can also be computed by a depth three circuit (i.e. a $\Sigma \Pi \Sigma$-circuit) of size ... more >>>

Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Benny Applebaum, Jonathan Avron, Christina Brzuska

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

Hubie Chen

The boolean circuit complexity classes

AC^0 \subseteq AC^0[m] \subseteq TC^0 \subseteq NC^1 have been studied

intensely. Other than NC^1, they are defined by constant-depth

circuits of polynomial size and unbounded fan-in over some set of

allowed gates. One reason for interest in these classes is that they

contain the ...
more >>>

Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

The parallel complexity class NC^1 has many equivalent models such as

polynomial size formulae and bounded width branching

programs. Caussinus et al. \cite{CMTV} considered arithmetizations of

two of these classes, #NC^1 and #BWBP. We further this study to

include arithmetization of other classes. In particular, we show that

counting paths ...
more >>>

Venkatesan Chakaravarthy, Sambuddha Roy

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.

Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ...
more >>>

Ran Raz, Gábor Tardos, Oleg Verbitsky, Nikolay Vereshchagin

It is well known that probabilistic boolean decision trees

cannot be much more powerful than deterministic ones (N.~Nisan, SIAM

Journal on Computing, 20(6):999--1007, 1991). Motivated by a question

if randomization can significantly speed up a nondeterministic

computation via a boolean decision tree, we address structural

properties of Arthur-Merlin games ...
more >>>

Tom Gur, Ran Raz

We study the power of Arthur-Merlin probabilistic proof systems in the data stream model. We show a canonical $\mathcal{AM}$ streaming algorithm for a wide class of data stream problems. The algorithm offers a tradeoff between the length of the proof and the space complexity that is needed to verify it.

... more >>>Venkatesan Guruswami

Algebraic codes that achieve list decoding capacity were recently

constructed by a careful ``folding'' of the Reed-Solomon code. The

``low-degree'' nature of this folding operation was crucial to the list

decoding algorithm. We show how such folding schemes conducive to list

decoding arise out of the Artin-Frobenius automorphism at primes ...
more >>>

Raghu Meka, Avi Wigderson

Finding cliques in random graphs and the closely related ``planted'' clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = ... more >>>

Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor

We show that the asymmetric $k$-center problem is

$\Omega(\log^* n)$-hard to approximate unless

${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$.

Since an $O(\log^* n)$-approximation algorithm is known

for this problem, this essentially resolves the approximability

of this problem. This is the first natural problem

whose approximability threshold does not polynomially ...
more >>>

Beate Bollig, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the

most common dynamic data structure or representation type

for Boolean functions. Among the many areas of application

are verification, model checking, and computer aided design.

For many functions it is easy to estimate the OBDD ...
more >>>

Claus-Peter Schnorr, Horst Helmut Hoerner

We introduce new algorithms for lattice basis reduction that are

improvements of the LLL-algorithm. We demonstrate the power of

these algorithms by solving random subset sum problems of

arbitrary density with 74 and 82 many weights, by breaking the

Chor-Rivest cryptoscheme in dimensions 103 and 151 ...
more >>>

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon

We study attribute efficient learning in the PAC learning model with

membership queries. First, we give an {\it attribute efficient}

PAC-learning algorithm for DNF with membership queries under the

uniform distribution. Previous algorithms for DNF have sample size

polynomial in the number of attributes $n$. Our algorithm is the

first ...
more >>>

Rocco Servedio, Li-Yang Tan, Justin Thaler

We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$ decision lists over $n$ Boolean variables. When the allowed running time is relatively high, our new ... more >>>

Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna de Rezende

We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula $F$, it is NP-hard to find a refutation of $F$ in the Nullstellensatz, Polynomial Calculus, or Sherali--Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a ... more >>>

Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula $F$,

(1) it is NP-hard to find a CP refutation of $F$ in time polynomial in the length of the shortest such refutation; and

(2) unless Gap-Hitting-Set admits a nontrivial algorithm, one cannot find a ... more >>>

Dmitry Itsykson, Artur Riazanov

We prove that the proof system OBDD(and, weakening) is not automatable unless P = NP. The proof is based upon the celebrated result of Atserias and Muller [FOCS 2019] about the hardness of automatability for resolution. The heart of the proof is lifting with a multi-output indexing gadget from resolution ... more >>>

Zoë Bell

We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF ... more >>>

Susanna de Rezende

We show that tree-like resolution is not automatable in time $n^{o(\log n)}$ unless ETH is false. This implies that, under ETH, the algorithm given by Beame and Pitassi (FOCS 1996) that automates tree-like resolution in time $n^{O(\log n)}$ is optimal. We also provide a simpler proof of the result of ... more >>>

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

John Hitchcock, Hadi Shafei

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following:

- For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible ... more >>>

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

We identify a new notion of pseudorandomness for randomness sources, which we call the average bias. Given a distribution $Z$ over $\{0,1\}^n$, its average bias is: $b_{\text{av}}(Z) =2^{-n} \sum_{c \in \{0,1\}^n} |\mathbb{E}_{z \sim Z}(-1)^{\langle c, z\rangle}|$. A source with average bias at most $2^{-k}$ has min-entropy at least $k$, and ... more >>>

Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook

An approximate computation of a Boolean function by a circuit or switching network is a computation which computes the function correctly on the majority of the inputs (rather than on all inputs). Besides being interesting in their own right, lower bounds for approximate computation have proved useful in many subareas ... more >>>

Andrej Bogdanov, Luca Trevisan

We survey the theory of average-case complexity, with a

focus on problems in NP.

Birgit Schelm

Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>>

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

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

Lijie Chen, Shuichi Hirahara, Neekon Vafa

What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness ... more >>>

Shuichi Hirahara

A long-standing and central open question in the theory of average-case complexity is to base average-case hardness of NP on worst-case hardness of NP. A frontier question along this line is to prove that PH is hard on average if UP requires (sub-)exponential worst-case complexity. The difficulty of resolving this ... more >>>

Hunter Monroe

We consolidate two widely believed conjectures about tautologies---no optimal proof system exists, and most require superpolynomial size proofs in any system---into a $p$-isomorphism-invariant condition satisfied by all paddable $\textbf{coNP}$-complete languages or none. The condition is: for any Turing machine (TM) $M$ accepting the language, $\textbf{P}$-uniform input families requiring superpolynomial time ... more >>>

Johannes Köbler, Rainer Schuler

We use the assumption that all sets in NP (or other levels

of the polynomial-time hierarchy) have efficient average-case

algorithms to derive collapse consequences for MA, AM, and various

subclasses of P/poly. As a further consequence we show for

C in {P(PP), PSPACE} that ...
more >>>

Neeraj Kayal, vineet nair, Chandan Saha

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>

Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan

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

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

Ilan Komargodski, Ran Raz

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same ... more >>>

Per Austrin, Kilian Risse

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree $\Omega(n/\log n)$ in the Polynomial ... more >>>

Xuangui Huang, Emanuele Viola

It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently ... more >>>

Sebastian Müller, Iddo Tzameret

Separating different propositional proof systems---that is, demonstrating that one proof system cannot efficiently simulate another proof system---is one of the main goals of proof complexity. Nevertheless, all known separation results between non-abstract proof systems are for specific families of hard tautologies: for what we know, in the average case all ... more >>>

Eric Allender

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one

considers *resource-bounded* Kolmogorov complexity. ...
more >>>