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

**O**

__
TR14-071
| 7th May 2014
__

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe#### O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem

__
TR18-149
| 25th August 2018
__

Craig Gentry, Charanjit Jutla#### Obfuscation using Tensor Products

__
TR24-049
| 7th March 2024
__

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich#### Oblivious Classes Revisited: Lower Bounds and Hierarchies

__
TR10-028
| 4th March 2010
__

Miklos Ajtai#### Oblivious RAMs without Cryptographic Assumptions

Revisions: 1

__
TR17-118
| 20th July 2017
__

Xiaotie Deng, Zhe Feng, Rucha Kulkarni#### Octahedral Tucker is PPA-Complete

Revisions: 1

__
TR09-139
| 17th December 2009
__

Mohammad Mahmoody, David Xiao#### On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

__
TR14-004
| 30th November 2013
__

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty#### On $r$-Simple $k$-Path

__
TR18-016
| 25th January 2018
__

Naomi Kirshner, Alex Samorodnitsky#### On $\ell_4$ : $\ell_2$ ratio of functions with restricted Fourier support

Revisions: 1

__
TR19-034
| 5th March 2019
__

Pavel Hrubes#### On $\epsilon$-sensitive monotone computations

Revisions: 1

__
TR22-001
| 28th December 2021
__

Yogesh Dahiya, Meena Mahajan#### On (Simple) Decision Tree Rank

Revisions: 1

__
TR05-077
| 15th July 2005
__

Zenon Sadowski#### On a D-N-optimal acceptor for TAUT

__
TR11-130
| 25th September 2011
__

Sergei Lozhkin, Alexander Shiganov#### On a Modification of Lupanov's Method with More Uniform Distribution of Fan-out

__
TR10-024
| 21st February 2010
__

Henning Wunderlich, Stefan Arnold#### On a singular value method in quantum communication complexity

Comments: 1

__
TR12-144
| 6th November 2012
__

Rocco Servedio, Emanuele Viola#### On a special case of rigidity

__
TR06-014
| 20th December 2005
__

Argimiro Arratia, Carlos E. Ortiz#### On a syntactic approximation to logics that capture complexity classes

__
TR10-086
| 17th May 2010
__

Henning Wunderlich#### On a Theorem of Razborov

__
TR17-034
| 21st February 2017
__

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam#### On algebraic branching programs of small width

Revisions: 1

__
TR23-135
| 14th September 2023
__

Prerona Chatterjee, Anamay Tengse#### On Annihilators of Explicit Polynomial Maps

__
TR02-046
| 16th July 2002
__

Marek Karpinski#### On Approximability of Minimum Bisection Problem

__
TR22-061
| 30th April 2022
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: I

__
TR23-055
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: II

Revisions: 1

__
TR23-054
| 20th April 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable $k$-CSPs: III

__
TR23-112
| 30th July 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable k-CSPs: IV

__
TR24-129
| 27th August 2024
__

Amey Bhangale, Subhash Khot, Dor Minzer#### On Approximability of Satisfiable k-CSPs: V

__
TR95-016
| 2nd February 1995
__

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern#### On approximately fair cost allocation in Euclidean TSP games

__
TR99-039
| 24th September 1999
__

Johan Håstad#### On approximating CSP-B

__
TR07-011
| 19th December 2006
__

Bodo Manthey#### On Approximating Restricted Cycle Covers

__
TR16-120
| 1st August 2016
__

Dean Doron, Amir Sarid, Amnon Ta-Shma#### On approximating the eigenvalues of stochastic matrices in probabilistic logspace

Revisions: 1

__
TR10-160
| 28th October 2010
__

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan#### On Approximating the Entropy of Polynomial Mappings

__
TR05-094
| 9th August 2005
__

Michal Parnas, Dana Ron#### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms

Revisions: 1

__
TR11-078
| 9th May 2011
__

Dana Ron, Gilad Tsur#### On Approximating the Number of Relevant Variables in a Function

__
TR98-024
| 28th April 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On Approximation Hardness of Dense TSP and other Path Problems

__
TR97-041
| 18th September 1997
__

Marek Karpinski, Juergen Wirtgen#### On Approximation Hardness of the Bandwidth Problem

__
TR98-014
| 6th February 1998
__

Gunter Blache, Marek Karpinski, Juergen Wirtgen#### On Approximation Intractability of the Bandwidth Problem

__
TR12-008
| 30th January 2012
__

Marek Karpinski, Richard Schmied#### On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

__
TR04-039
| 21st April 2004
__

Andrzej Lingas, Martin Wahlén#### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems

__
TR06-066
| 5th May 2006
__

Vitaly Feldman#### On Attribute Efficient and Non-adaptive Learning of Parities and DNF Expressions

Revisions: 1

__
TR17-110
| 22nd June 2017
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Axis-Parallel Tests for Tensor Product Codes

__
TR06-015
| 1st February 2006
__

Tomas Feder, Carlos Subi#### On Barnette's conjecture

__
TR20-095
| 24th June 2020
__

Mikito Nanashima#### On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions

Revisions: 1

__
TR14-108
| 10th August 2014
__

Andrej Bogdanov, Christina Brzuska#### On Basing Size-Verifiable One-Way Functions on NP-Hardness

Revisions: 1

__
TR09-006
| 19th January 2009
__

David Xiao#### On basing ZK != BPP on the hardness of PAC learning

__
TR10-186
| 2nd December 2010
__

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola#### On beating the hybrid argument

__
TR15-072
| 23rd April 2015
__

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

Revisions: 4

__
TR07-019
| 10th March 2007
__

Jin-Yi Cai, Pinyan Lu#### On Block-wise Symmetric Signatures for Matchgates

__
TR22-137
| 26th September 2022
__

Daniel Avraham , Amir Yehudayoff#### On blocky ranks of matrices

__
TR98-030
| 9th June 1998
__

Stasys Jukna, Stanislav Zak#### On Branching Programs With Bounded Uncertainty

__
TR03-041
| 29th May 2003
__

Albert Atserias, Maria Luisa Bonet, Jordi Levy#### On Chvatal Rank and Cutting Planes Proofs

__
TR18-210
| 30th November 2018
__

Karthik C. S., Pasin Manurangsi#### On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

__
TR04-024
| 26th March 2004
__

Thomas Thierauf, Thanh Minh Hoang#### On Closure Properties of GapL

Revisions: 1
,
Comments: 1

__
TR23-158
| 1st November 2023
__

Oded Goldreich#### On coarse and fine approximate counting of $t$-cliques

__
TR17-177
| 16th November 2017
__

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff#### On Communication Complexity of Classification Problems

Revisions: 1

__
TR05-051
| 18th March 2005
__

Predrag Tosic#### On Complexity of Counting Fixed Points in Certain Classes of Graph Automata

Revisions: 2

__
TR05-074
| 8th June 2005
__

Li-Sha Huang, Xiaotie Deng#### On Complexity of Market Equilibria with Maximum Social Welfare

__
TR08-085
| 19th June 2008
__

Farid Ablayev, Airat Khasianov, Alexander Vasiliev#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

__
TR99-044
| 30th September 1999
__

Farid Ablayev#### On Complexity of Regular $(1,+k)$-Branching Programs

__
TR00-038
| 24th May 2000
__

#### On Computation with Pulses

__
TR11-107
| 22nd July 2011
__

Pavol Duris#### On Computational Power of Partially Blind Automata

__
TR20-032
| 12th March 2020
__

Suryajith Chillara#### On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Revisions: 2

__
TR17-193
| 31st December 2017
__

Oded Goldreich, Avishay Tal#### On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions

__
TR95-029
| 15th June 1995
__

Oded Goldreich, Leonid Levin, Noam Nisan#### On Constructing 1-1 One-Way Functions

__
TR03-017
| 27th March 2003
__

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener#### On Converting CNF to DNF

__
TR09-040
| 20th April 2009
__

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak#### On convex complexity measures

__
TR22-092
| 2nd July 2022
__

Peter Ivanov, Liam Pavlovic, Emanuele Viola#### On correlation bounds against polynomials

__
TR18-023
| 4th February 2018
__

Eran Iceland, Alex Samorodnitsky#### On coset leader graphs of structured linear codes

Revisions: 1

__
TR98-020
| 10th April 1998
__

Andris Ambainis, David Mix Barrington, Huong LeThanh#### On Counting $AC^0$ Circuits with Negative Constants

__
TR20-104
| 12th July 2020
__

Oded Goldreich#### On Counting $t$-Cliques Mod 2

Revisions: 3

__
TR05-121
| 17th October 2005
__

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson#### On counting homomorphisms to directed acyclic graphs

__
TR95-062
| 14th December 1995
__

Amir M. Ben-Amram, Zvi Galil#### On Data Structure Tradeoffs and an Application to Union-Find

Comments: 1

__
TR06-113
| 25th August 2006
__

Peter Buergisser#### On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity

__
TR17-146
| 1st October 2017
__

Or Meir#### On Derandomized Composition of Boolean Functions

Revisions: 4

__
TR13-152
| 7th November 2013
__

Oded Goldreich, Avi Wigderson#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

__
TR02-009
| 17th January 2002
__

Petr Savicky#### On determinism versus unambiquous nondeterminism for decision trees

__
TR22-173
| 3rd December 2022
__

Paul Beame, Sajin Koroth#### On Disperser/Lifting Properties of the Index and Inner-Product Functions

Revisions: 1

__
TR05-064
| 26th June 2005
__

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani#### On earthmover distance, metric labeling, and 0-extension

__
TR22-022
| 18th February 2022
__

Vikraman Arvind, Pushkar Joglekar#### On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Revisions: 3

__
TR15-086
| 28th May 2015
__

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

__
TR16-066
| 19th April 2016
__

Oded Goldreich, Maya Leshkowitz#### On Emulating Interactive Proofs with Public Coins

__
TR03-043
| 14th May 2003
__

Elchanan Mossel, Amir Shpilka, Luca Trevisan#### On epsilon-Biased Generators in NC0

__
TR04-013
| 10th February 2004
__

Oded Goldreich, Dana Ron#### On Estimating the Average Degree of a Graph.

__
TR97-013
| 13th February 1997
__

Bernd Borchert, Dietrich Kuske, Frank Stephan#### On Existentially First-Order Definable Languages and their Relation to NP

__
TR06-028
| 21st February 2006
__

Jonathan Katz, Chiu-Yuen Koo#### On Expected Constant-Round Protocols for Byzantine Agreement

__
TR06-099
| 17th August 2006
__

Oded Goldreich#### On Expected Probabilistic Polynomial-Time Adversaries -- A suggestion for restricted definitions and their benefits

Revisions: 1

__
TR19-169
| 21st November 2019
__

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev#### On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds

Revisions: 2

__
TR17-174
| 13th November 2017
__

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao#### On Expressing Majority as a Majority of Majorities

__
TR95-058
| 20th November 1995
__

Amnon Ta-Shma#### On Extracting Randomness From Weak Random Sources

__
TR22-009
| 17th January 2022
__

C. Ramya, Anamay Tengse#### On Finer Separations between Subclasses of Read-once Oblivious ABPs

__
TR15-069
| 21st April 2015
__

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

Revisions: 1

__
TR13-168
| 29th November 2013
__

Raghav Kulkarni, Avishay Tal#### On Fractional Block Sensitivity

Revisions: 1
,
Comments: 1

__
TR98-061
| 29th September 1998
__

Robert H. Sloan, Ken Takata, György Turán#### On frequent sets of Boolean matrices

__
TR04-005
| 19th January 2004
__

Stasys Jukna#### On Graph Complexity

Revisions: 1
,
Comments: 1

__
TR21-153
| 9th November 2021
__

Ronen Shaltiel, Emanuele Viola#### On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

Revisions: 1

__
TR15-013
| 28th January 2015
__

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

__
TR15-067
| 21st April 2015
__

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

__
TR22-106
| 21st July 2022
__

Suryajith Chillara, Coral Grichener, Amir Shpilka#### On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

__
TR06-131
| 6th October 2006
__

Konstantin Pervyshev#### On Heuristic Time Hierarchies

__
TR19-119
| 9th September 2019
__

Dean Doron, Amnon Ta-Shma, Roei Tell#### On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

__
TR11-147
| 2nd November 2011
__

Michael Forbes, Amir Shpilka#### On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing

__
TR24-007
| 25th December 2023
__

Karthik C. S., Pasin Manurangsi#### On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results

Revisions: 1

__
TR16-124
| 12th August 2016
__

Subhash Khot#### On Independent Sets, $2$-to-$2$ Games and Grassmann Graphs

Revisions: 1
,
Comments: 1

__
TR23-131
| 8th September 2023
__

Meghal Gupta, Rachel Zhang#### On Interactive Coding Schemes with Adaptive Termination

__
TR22-124
| 9th September 2022
__

Oded Goldreich, Guy Rothblum, Tal Skverer#### On Interactive Proofs of Proximity with Proof-Oblivious Queries

Revisions: 4

__
TR01-046
| 2nd July 2001
__

Oded Goldreich, Salil Vadhan, Avi Wigderson#### On Interactive Proofs with a Laconic Prover

__
TR13-180
| 17th December 2013
__

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian#### On Interactivity in Arthur-Merlin Communication and Stream Computation

Revisions: 1

__
TR15-164
| 13th October 2015
__

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

__
TR08-077
| 23rd May 2008
__

Felix Brandt, Felix Fischer, Markus Holzer#### On Iterated Dominance, Matrix Elimination, and Matched Paths

__
TR05-023
| 16th February 2005
__

Robert H. Sloan, Balázs Szörényi, György Turán#### On k-term DNF with largest number of prime implicants

__
TR14-029
| 4th March 2014
__

Oded Goldreich, Dana Ron#### On Learning and Testing Dynamic Environments

Revisions: 3

__
TR96-009
| 17th January 1996
__

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio#### On Learning Branching Programs and Small Depth Circuits

__
TR01-098
| 19th November 2001
__

Ke Yang#### On Learning Correlated Boolean Functions Using Statistical Query

__
TR00-066
| 14th July 2000
__

Peter Auer#### On Learning from Ambiguous Information

__
TR01-006
| 18th October 2000
__

Rocco Servedio#### On Learning Monotone DNF under Product Distributions

__
TR00-014
| 16th February 2000
__

Matthias Krause, Stefan Lucks#### On Learning versus Distinguishing and the Minimal Hardware Complexity of Pseudorandom Function Generators

__
TR14-058
| 20th April 2014
__

Ilya Volkovich#### On Learning, Lower Bounds and (un)Keeping Promises

__
TR23-122
| 9th August 2023
__

Vikraman Arvind, Abhranil Chatterjee#### On Lifting Lower Bounds for Noncommutative Circuits using Automata

__
TR13-065
| 21st April 2013
__

Yijia Chen, Joerg Flum#### On Limitations of the Ehrenfeucht-Fraisse-method in Descriptive Complexity

__
TR23-004
| 13th January 2023
__

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang#### On linear-algebraic notions of expansion

__
TR22-012
| 2nd February 2022
__

Anup Rao, Oscar Sprumont#### On List Decoding Transitive Codes From Random Errors

__
TR19-080
| 1st June 2019
__

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas#### On List Recovery of High-Rate Tensor Codes

__
TR19-070
| 14th May 2019
__

Alessandro Chiesa, Peter Manohar, Igor Shinkar#### On Local Testability in the Non-Signaling Setting

Revisions: 1

__
TR97-012
| 19th March 1997
__

Luca Trevisan#### On Local versus Global Satisfiability

__
TR09-073
| 6th September 2009
__

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan#### On Lower Bounds for Constant Width Arithmetic Circuits

__
TR22-111
| 1st August 2022
__

Robert Andrews#### On Matrix Multiplication and Polynomial Identity Testing

__
TR09-134
| 10th December 2009
__

Zeev Dvir#### On matrix rigidity and locally self-correctable codes

Revisions: 1

__
TR05-070
| 6th July 2005
__

Mahdi Cheraghchi#### On Matrix Rigidity and the Complexity of Linear Forms

__
TR17-183
| 28th November 2017
__

Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin#### On Maximally Recoverable Local Reconstruction Codes

__
TR09-100
| 16th October 2009
__

Jakob Nordström, Alexander Razborov#### On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

__
TR20-079
| 15th May 2020
__

Hermann Gruber , Markus Holzer, Simon Wolfsteiner#### On Minimizing Regular Expressions Without Kleene Star

__
TR15-011
| 22nd January 2015
__

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

__
TR01-049
| 11th July 2001
__

Stasys Jukna, Georg Schnitger#### On Multi-Partition Communication Complexity of Triangle-Freeness

Comments: 2

__
TR16-051
| 7th April 2016
__

Ronald Cramer, Chaoping Xing, chen yuan#### On Multi-Point Local Decoding of Reed-Muller Codes

Revisions: 4

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR01-066
| 28th September 2001
__

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger#### On Multipartition Communication Complexity

__
TR16-138
| 3rd September 2016
__

Alexander A. Sherstov#### On multiparty communication with large versus unbounded error

__
TR13-067
| 2nd May 2013
__

Oded Goldreich#### On Multiple Input Problems in Property Testing

Revisions: 1

__
TR96-034
| 28th March 1996
__

Vasken Bohossian, Jehoshua Bruck#### On Neural Networks with Minimal Weights

__
TR05-058
| 24th May 2005
__

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra#### On Non-Approximability for Quadratic Programs

__
TR13-094
| 13th June 2013
__

Brendan Juba#### On Non-automatizability in PAC-Semantics

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR19-025
| 28th February 2019
__

Shuichi Hirahara, Osamu Watanabe#### On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets

Revisions: 1

__
TR97-030
| 25th August 1997
__

Martin Sauerhoff#### On Nondeterminism versus Randomness for Read-Once Branching Programs

__
TR19-001
| 5th January 2019
__

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov#### On OBDD-based algorithms and proof systems that dynamically change order of variables

__
TR06-128
| 5th October 2006
__

Shankar Kalyanaraman, Chris Umans#### On obtaining pseudorandomness from error-correcting codes.

__
TR02-020
| 13th March 2002
__

Elizaveta Okol'nishnikova#### On one lower bound for branching programs

__
TR22-104
| 18th July 2022
__

Nader Bshouty#### On One-Sided Testing Affine Subspaces

Revisions: 1

__
TR20-052
| 14th April 2020
__

Yanyi Liu, Rafael Pass#### On One-way Functions and Kolmogorov Complexity

Revisions: 2

__
TR23-103
| 12th July 2023
__

Yanyi Liu, Rafael Pass#### On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity

Revisions: 1

__
TR21-059
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### On One-way Functions from NP-Complete Problems

Revisions: 2

__
TR00-006
| 26th January 2000
__

E.A. Okol'nishnikiva#### On operations of geometrical projection and monotone extension

__
TR10-193
| 5th December 2010
__

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal#### On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography

__
TR11-170
| 16th December 2011
__

Constantinos Daskalakis, S. Matthew Weinberg#### On Optimal Multi-Dimensional Mechanism Design

__
TR10-008
| 13th January 2010
__

Yijia Chen, Joerg Flum#### On optimal proof systems and logics for PTIME

Revisions: 1

__
TR24-113
| 4th July 2024
__

Nikhil Vyas, Ryan Williams#### On Oracles and Algorithmic Methods for Proving Lower Bounds

__
TR97-023
| 3rd June 1997
__

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener#### On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

__
TR04-074
| 26th August 2004
__

Emanuele Viola#### On Parallel Pseudorandom Generators

Revisions: 1

__
TR15-039
| 16th March 2015
__

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

__
TR07-106
| 10th September 2007
__

Yijia Chen, Martin Grohe, Magdalena Grüber#### On Parameterized Approximability

__
TR09-067
| 18th August 2009
__

Hanna Mazzawi, Nader Bshouty#### On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

__
TR20-119
| 1st August 2020
__

Nikhil Mande, Swagato Sanyal#### On parity decision trees for Fourier-sparse Boolean functions

__
TR15-132
| 13th August 2015
__

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

Revisions: 2

__
TR08-067
| 4th June 2008
__

Scott Aaronson#### On Perfect Completeness for QMA

__
TR24-017
| 23rd January 2024
__

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun#### On Pigeonhole Principles and Ramsey in TFNP

Revisions: 1

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR16-068
| 28th April 2016
__

Prahladh Harsha, Srikanth Srinivasan#### On Polynomial Approximations to $\mathrm{AC}^0$

Revisions: 1

__
TR98-054
| 26th August 1998
__

Igor E. Shparlinski#### On Polynomial Representations of Boolean Functions Related to Some Number Theoretic Problems

__
TR96-043
| 16th August 1996
__

Edmund Ihler#### On polynomial time approximation schemes and approximation preserving reductions

__
TR21-149
| 5th November 2021
__

Sevag Gharibian, Dorian Rudolph#### On polynomially many queries to NP or QMA oracles

__
TR04-031
| 22nd March 2004
__

Troy Lee, Andrei Romashchenko#### On Polynomially Time Bounded Symmetry of Information

__
TR16-156
| 12th October 2016
__

Eli Ben-Sasson, Alessandro Chiesa, Michael Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner#### On Probabilistic Checking in Perfect Zero Knowledge

Revisions: 1

__
TR05-137
| 21st November 2005
__

Emanuele Viola#### On Probabilistic Time versus Alternating Time

__
TR06-136
| 22nd October 2006
__

Mihir Bellare, Oded Goldreich#### On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

__
TR05-018
| 6th February 2005
__

Oded Goldreich#### On Promise Problems (a survey in memory of Shimon Even [1935-2004])

__
TR20-034
| 12th March 2020
__

Erfan Khaniki#### On Proof complexity of Resolution over Polynomial Calculus

Revisions: 3

__
TR22-013
| 5th February 2022
__

Nader Bshouty, Oded Goldreich#### On properties that are non-trivial to test

__
TR13-097
| 25th June 2013
__

Mikolas Janota, Joao Marques-Silva#### On Propositional QBF Expansions and Q-Resolution

__
TR94-006
| 12th December 1994
__

Alexander Razborov#### On provably disjoint NP-pairs

__
TR19-176
| 4th December 2019
__

Gal Arnon, Guy Rothblum#### On Prover-Efficient Public-Coin Emulation of Interactive Proofs

Revisions: 4

__
TR08-041
| 10th April 2008
__

Oded Goldreich, Dana Ron#### On Proximity Oblivious Testing

__
TR00-056
| 20th July 2000
__

Oded Goldreich, Avi Wigderson#### On Pseudorandomness with respect to Deterministic Observers.

__
TR15-094
| 10th June 2015
__

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

__
TR21-123
| 25th August 2021
__

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani#### On public-coin zero-error randomized communication complexity

Revisions: 2

__
TR16-043
| 23rd February 2016
__

Mikolas Janota#### On Q-Resolution and CDCL QBF Solving

__
TR21-115
| 6th August 2021
__

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming#### On quantum versus classical query complexity

Revisions: 2

__
TR05-007
| 15th December 2004
__

Vadim Lyubashevsky#### On Random High Density Subset Sums

__
TR98-068
| 12th November 1998
__

Petr Savicky#### On Random Orderings of Variables for Parity OBDDs

__
TR22-074
| 20th May 2022
__

Michael Saks, Rahul Santhanam#### On Randomized Reductions to the Random Strings

__
TR95-021
| 20th April 1995
__

Marek Karpinski, Rutger Verbeek#### On Randomized Versus Deterministic Computation

__
TR15-003
| 3rd January 2015
__

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

__
TR94-001
| 12th December 1994
__

Noam Nisan, Avi Wigderson#### On Rank vs. Communication Complexity

__
TR24-125
| 19th July 2024
__

Pavel Hrubes, Pushkar Joglekar#### On read-$k$ projections of the determinant

__
TR01-044
| 14th June 2001
__

Pavel Pudlak#### On reducibility and symmetry of disjoint NP-pairs

__
TR19-141
| 22nd October 2019
__

Mark Braverman, Subhash Khot, Dor Minzer#### On Rich $2$-to-$1$ Games

__
TR12-133
| 21st October 2012
__

Noga Alon, Gil Cohen#### On Rigid Matrices and Subspace Polynomials

Revisions: 1

__
TR13-109
| 11th August 2013
__

Oded Goldreich, Dana Ron#### On Sample-Based Testers

Revisions: 1

__
TR98-028
| 28th May 1998
__

Paul Beame, Faith Fich#### On Searching Sorted Lists: A Near-Optimal Lower Bound

__
TR21-090
| 14th June 2021
__

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro#### On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

__
TR01-022
| 15th February 2001
__

Rahul Santhanam#### On segregators, separators and time versus space

__
TR22-003
| 4th January 2022
__

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere#### On Semi-Algebraic Proofs and Algorithms

Revisions: 1

__
TR98-002
| 8th January 1998
__

Jayram S. Thathachar#### On Separating the Read-k-Times Branching Program Hierarchy

__
TR22-066
| 4th May 2022
__

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy#### On sketching approximations for symmetric Boolean CSPs

__
TR15-090
| 1st June 2015
__

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

Revisions: 1

__
TR23-042
| 3rd April 2023
__

Johan Håstad#### On small-depth Frege proofs for PHP

__
TR17-142
| 21st September 2017
__

Johan Håstad#### On small-depth Frege proofs for Tseitin for grids

Revisions: 1

__
TR22-070
| 8th May 2022
__

Pranav Bisht, Ilya Volkovich#### On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

__
TR98-029
| 27th May 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results

__
TR98-065
| 6th November 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results, Further Improvements

__
TR16-184
| 16th November 2016
__

Alexander Razborov#### On Space and Depth in Resolution

__
TR03-023
| 12th February 2003
__

Anna Palbom#### On Spanning Cacti and Asymmetric TSP

__
TR13-070
| 4th May 2013
__

Iddo Tzameret#### On Sparser Random 3SAT Refutation Algorithms and Feasible Interpolation

Revisions: 1

__
TR03-014
| 28th February 2003
__

Avrim Blum, Ke Yang#### On Statistical Query Sampling and NMR Quantum Computing

__
TR11-079
| 9th May 2011
__

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan#### On Sums of Locally Testable Affine Invariant Properties

__
TR11-067
| 25th April 2011
__

Noga Alon, Amir Shpilka, Chris Umans#### On Sunflowers and Matrix Multiplication

Comments: 1

__
TR18-034
| 15th February 2018
__

Young Kun Ko#### On Symmetric Parallel Repetition : Towards Equivalence of MAX-CUT and UG

__
TR06-135
| 22nd October 2006
__

Jin-Yi Cai, Pinyan Lu#### On Symmetric Signatures in Holographic Algorithms

__
TR95-023
| 16th May 1995
__

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani#### On Syntactic versus Computational views of Approximability

__
TR16-140
| 9th September 2016
__

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan#### On SZK and PP

Revisions: 3

__
TR97-016
| 29th April 1997
__

Manindra Agrawal, Eric Allender, Samir Datta#### On TC^0, AC^0, and Arithmetic Circuits

__
TR23-034
| 24th March 2023
__

Oded Goldreich#### On teaching the approximation method for circuit lower bounds

Revisions: 1

__
TR13-166
| 28th November 2013
__

Arnab Bhattacharyya#### On testing affine-invariant properties

__
TR20-118
| 5th August 2020
__

Oded Goldreich#### On Testing Asymmetry in the Bounded Degree Graph Model

Revisions: 4

__
TR13-089
| 17th June 2013
__

Abhishek Bhrushundi#### On testing bent functions

Revisions: 1

__
TR10-061
| 10th April 2010
__

Oded Goldreich#### On Testing Computability by Small Width OBDDs

Revisions: 2

__
TR00-020
| 27th March 2000
__

Oded Goldreich, Dana Ron#### On Testing Expansion in Bounded-Degree Graphs

__
TR23-214
| 31st December 2023
__

Oded Goldreich, Laliv Tauber#### On Testing Group Properties

Revisions: 1

__
TR20-109
| 19th July 2020
__

Oded Goldreich#### On Testing Hamiltonicity in the Bounded Degree Graph Model

Revisions: 2

__
TR14-145
| 4th November 2014
__

Yuan Li, Alexander Razborov, Benjamin Rossman#### On the $AC^0$ Complexity of Subgraph Isomorphism

__
TR19-096
| 23rd July 2019
__

Aditya Potukuchi#### On the $\text{AC}^0[\oplus]$ complexity of Andreev's Problem

__
TR22-030
| 18th February 2022
__

Aniruddha Biswas, Palash Sarkar#### On The ''Majority is Least Stable'' Conjecture.

Revisions: 1

__
TR21-141
| 28th September 2021
__

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz#### On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

Revisions: 1

__
TR03-085
| 28th November 2003
__

Ke Yang#### On the (Im)possibility of Non-interactive Correlation Distillation

__
TR01-057
| 15th August 2001
__

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang#### On the (Im)possibility of Obfuscating Programs

__
TR03-015
| 20th March 2003
__

Yael Tauman Kalai#### On the (In)security of the Fiat-Shamir Paradigm

__
TR14-164
| 30th November 2014
__

Cody Murray, Ryan Williams#### On the (Non) NP-Hardness of Computing Circuit Complexity

__
TR07-104
| 15th September 2007
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### On the Advantage over Random for Maximum Acyclic Subgraph

__
TR00-017
| 3rd March 2000
__

Valentin E. Brimkov, Stefan S. Dantchev#### On the Algebraic Complexity of Integer Programming

__
TR21-071
| 16th May 2021
__

Samuel Epstein#### On the Algorithmic Content of Quantum Measurements

__
TR11-019
| 5th February 2011
__

Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni#### On the Approximability of a Geometric Set Cover Problem

__
TR96-015
| 12th December 1995
__

Edoardo Amaldi, Viggo Kann#### On the approximability of some NP-hard minimization problems for linear systems

__
TR96-046
| 27th August 1996
__

Luca Trevisan#### On the Approximability of the Multi-dimensional Euclidean TSP

Revisions: 1

__
TR06-031
| 27th February 2006
__

Li-Sha Huang, Shang-Hua Teng#### On the Approximation and Smoothed Complexity of Leontief Market Equilibria

__
TR20-096
| 22nd June 2020
__

Igor Sergeev#### On the asymptotic complexity of sorting

__
TR09-014
| 7th February 2009
__

Soren Riis#### On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

__
TR09-035
| 26th March 2009
__

Nicola Galesi, Massimo Lauria#### On the Automatizability of Polynomial Calculus

__
TR02-010
| 21st January 2002
__

Albert Atserias, Maria Luisa Bonet#### On the Automatizability of Resolution and Related Propositional Proof Systems

__
TR02-056
| 19th September 2002
__

Todd Ebert, Wolfgang Merkle, Heribert Vollmer#### On the Autoreducibility of Random Sequences

__
TR07-057
| 11th July 2007
__

Oded Goldreich#### On the Average-Case Complexity of Property Testing

Revisions: 1

__
TR15-190
| 2nd November 2015
__

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

__
TR12-093
| 1st July 2012
__

Charanjit Jutla, Vijay Kumar, Atri Rudra#### On the Circuit Complexity of Composite Galois Field Transformations

__
TR96-041
| 24th July 1996
__

Oded Goldreich, Avi Wigderson#### On the Circuit Complexity of Perfect Hashing

Revisions: 1
,
Comments: 2

__
TR24-021
| 29th January 2024
__

Prasad Chaugule, Nutan Limaye#### On the closures of monotone algebraic classes and variants of the determinant

__
TR13-073
| 14th May 2013
__

Oded Goldreich#### On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing

Revisions: 2

__
TR16-055
| 11th April 2016
__

Tim Roughgarden, Omri Weinstein#### On the Communication Complexity of Approximate Fixed Points

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

__
TR06-037
| 10th February 2006
__

Xi Chen, Xiaotie Deng#### On the Complexity of 2D Discrete Fixed Point Problem

__
TR22-053
| 24th April 2022
__

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap#### On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs

Revisions: 3
,
Comments: 1

__
TR24-115
| 14th July 2024
__

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam#### On the Complexity of Avoiding Heavy Elements

__
TR09-048
| 29th May 2009
__

Parikshit Gopalan, Shachar Lovett, Amir Shpilka#### On the Complexity of Boolean Functions in Different Characteristics

__
TR11-004
| 10th January 2011
__

Oded Goldreich, Salil Vadhan#### On the complexity of computational problems regarding distributions (a survey)

Comments: 1

__
TR19-036
| 5th March 2019
__

Pavel Hrubes#### On the complexity of computing a random Boolean function over the reals

Revisions: 1

__
TR00-086
| 26th September 2000
__

Michael Schmitt#### On the Complexity of Computing and Learning with Multiplicative Neural Networks

__
TR21-128
| 4th September 2021
__

Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang#### On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games

__
TR12-069
| 23rd March 2012
__

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry#### On the complexity of computing minimal unsatisfiable LTL formulas

__
TR12-019
| 2nd March 2012
__

Eric Miles, Emanuele Viola#### On the complexity of constructing pseudorandom functions (especially when they don't exist)

__
TR08-084
| 16th June 2008
__

Sanjeeb Dash#### On the complexity of cutting plane proofs using split cuts

__
TR23-134
| 14th September 2023
__

Oded Goldreich#### On the complexity of enumerating ordered sets

__
TR19-088
| 16th June 2019
__

Oded Goldreich#### On the Complexity of Estimating the Effective Support Size

Revisions: 1

__
TR18-084
| 24th April 2018
__

Iftach Haitner, Nikolaos Makriyannis, Eran Omri#### On the Complexity of Fair Coin Flipping

__
TR99-038
| 27th August 1999
__

Peter Jonsson, Paolo Liberatore#### On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction

__
TR00-050
| 13th July 2000
__

Peter Auer, Philip M. Long, Gerhard J. Woeginger#### On the Complexity of Function Learning

__
TR11-052
| 4th April 2011
__

Fabian Wagner#### On the Complexity of Group Isomorphism

Revisions: 4
,
Comments: 3

__
TR01-076
| 24th October 2001
__

Robert Albin Legenstein#### On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets

__
TR97-049
| 22nd October 1997
__

Michael Schmitt#### On the Complexity of Learning for Spiking Neurons with Temporal Coding

__
TR02-012
| 3rd February 2002
__

Ran Raz#### On the Complexity of Matrix Product

__
TR15-004
| 4th January 2015
__

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

__
TR05-037
| 8th April 2005
__

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen#### On the Complexity of Numerical Analysis

Revisions: 1
,
Comments: 1

__
TR13-041
| 14th March 2013
__

Igor Sergeev#### On the complexity of parallel prefix circuits

__
TR01-054
| 12th April 2001
__

Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir#### On the Complexity of Positional Sequencing by Hybridization

__
TR14-148
| 8th November 2014
__

Vitaly Feldman, Will Perkins, Santosh Vempala#### On the Complexity of Random Satisfiability Problems with Planted Solutions

Revisions: 1

__
TR06-100
| 17th July 2006
__

Meena Mahajan, Jayalal Sarma#### On the Complexity of Rank and Rigidity

__
TR24-126
| 17th June 2024
__

Takashi Ishizuka#### On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König

__
TR04-001
| 11th December 2003
__

Lance Fortnow, Russell Impagliazzo, Chris Umans#### On the complexity of succinct zero-sum games

__
TR12-067
| 6th May 2012
__

Xiaohui Bei, Ning Chen, Shengyu Zhang#### On the Complexity of Trial and Error

Revisions: 1

__
TR14-034
| 3rd March 2014
__

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram#### On the complexity of trial and error for constraint satisfaction problems

__
TR21-124
| 17th August 2021
__

Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia#### On the Complexity of Two-Party Differential Privacy

Revisions: 1

__
TR23-099
| 8th July 2023
__

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh#### On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

__
TR06-022
| 17th February 2006
__

Danny Harnik, Moni Naor#### On the Compressibility of NP Instances and Cryptographic Applications

Revisions: 1

__
TR08-059
| 20th May 2008
__

Farid Ablayev, Alexander Vasiliev#### On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting

Revisions: 1

__
TR16-034
| 7th March 2016
__

Mohamed El Halaby#### On the Computational Complexity of MaxSAT

Revisions: 1

__
TR96-033
| 6th March 1996
__

Bernd Borchert, Desh Ranjan, Frank Stephan#### On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions

__
TR04-116
| 18th November 2004
__

PERRET ludovic#### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields

__
TR99-027
| 17th July 1999
__

Marek Karpinski, Igor E. Shparlinski#### On the computational hardness of testing square-freeness of sparse polynomials

__
TR94-023
| 12th December 1994
__

Matthias Krause, Pavel Pudlak#### On the Computational Power of Depth 2 Circuits with Threshold and Modulo Gates

__
TR98-038
| 9th July 1998
__

Marek Karpinski#### On the Computational Power of Randomized Branching Programs

__
TR02-022
| 12th April 2002
__

Henry Markram#### On the Computational Power of Recurrent Circuits of Spiking Neurons

__
TR00-032
| 31st May 2000
__

#### On the Computational Power of Winner-Take-All

__
TR12-045
| 22nd April 2012
__

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer#### On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs

Revisions: 3

__
TR13-148
| 26th October 2013
__

Irit Dinur, Igor Shinkar#### On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

__
TR95-052
| 4th October 1995
__

Douglas R. Stinson#### On the Connections Between Universal Hashing, Combinatorial Designs and Error-Correcting Codes

__
TR09-143
| 22nd December 2009
__

Noam Livne#### On the Construction of One-Way Functions from Average Case Hardness

__
TR97-005
| 17th February 1997
__

Moni Naor, Omer Reingold#### On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

__
TR24-109
| 29th June 2024
__

Oded Goldreich#### On the Cook-Mertz Tree Evaluation procedure

Revisions: 1

__
TR12-137
| 1st November 2012
__

Johan Håstad#### On the correlation of parity and small-depth circuits

Revisions: 1

__
TR15-001
| 2nd January 2015
__

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

Revisions: 1

__
TR98-052
| 5th August 1998
__

Boris Hemkemeier, Frank Vallentin#### On the decomposition of lattices

Revisions: 1

__
TR06-142
| 26th October 2006
__

Olaf Beyersdorff#### On the Deduction Theorem and Complete Disjoint NP-Pairs

__
TR23-177
| 18th November 2023
__

Kiran Kedlaya, Swastik Kopparty#### On the degree of polynomials computing square roots mod p

Revisions: 1

__
TR10-039
| 10th March 2010
__

Gil Cohen, Amir Shpilka#### On the degree of symmetric functions on the Boolean cube

Comments: 1

__
TR11-002
| 9th January 2011
__

Gil Cohen, Amir Shpilka, Avishay Tal#### On the Degree of Univariate Polynomials Over the Integers

__
TR12-157
| 12th November 2012
__

Andrej Bogdanov, Chin Ho Lee#### On the depth complexity of homomorphic encryption schemes

Revisions: 2

__
TR00-081
| 5th September 2000
__

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe#### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems

__
TR00-044
| 26th June 2000
__

Tzvika Hartman, Ran Raz#### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

__
TR17-101
| 8th June 2017
__

Oded Goldreich#### On the doubly-efficient interactive proof systems of GKR

Revisions: 1

__
TR97-051
| 11th November 1997
__

Pekka Orponen#### On the Effect of Analog Noise in Discrete-Time Analog Computations

__
TR12-012
| 9th February 2012
__

Oded Goldreich#### On the Effect of the Proximity Parameter on Property Testers

__
TR08-064
| 11th July 2008
__

Or Meir#### On the Efficiency of Non-Uniform PCPP Verifiers

__
TR97-001
| 8th January 1997
__

Marco Cesati, Luca Trevisan#### On the Efficiency of Polynomial Time Approximation Schemes

__
TR15-129
| 7th August 2015
__

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

Revisions: 1

__
TR02-016
| 30th January 2002
__

Alina Beygelzimer, Mitsunori Ogihara#### On the Enumerability of the Determinant and the Rank

__
TR05-061
| 15th June 2005
__

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma#### On the Error Parameter of Dispersers

__
TR20-063
| 29th April 2020
__

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse#### On the Existence of Algebraically Natural Proofs

Revisions: 2

__
TR98-001
| 17th December 1997
__

Detlef Sieling#### On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization

Revisions: 1

__
TR98-021
| 7th April 1998
__

Shai Ben-David, Anna Gringauze.#### On the Existence of Propositional Proof Systems and Oracle-relativized Propositional Logic.

Revisions: 1

__
TR23-210
| 22nd December 2023
__

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach#### On the Existence of Seedless Condensers: Exploring the Terrain

Revisions: 1

__
TR22-120
| 24th August 2022
__

Jan Krajicek#### On the existence of strong proof complexity generators

Revisions: 1
,
Comments: 1

__
TR05-112
| 12th September 2005
__

Eran Ofek#### On the expansion of the giant component in percolated $(n,d,\lambda)$ graphs

Revisions: 1

__
TR15-141
| 26th August 2015
__

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

__
TR16-056
| 8th April 2016
__

Shafi Goldwasser, Dhiraj Holden#### On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances

__
TR19-045
| 19th February 2019
__

Jiawei Gao#### On the Fine-grained Complexity of Least Weight Subsequence in Graphs

Revisions: 1

__
TR95-032
| 6th April 1995
__

Nader Bshouty, Christino Tamon#### On the Fourier spectrum of monotone functions

__
TR21-178
| 3rd December 2021
__

Srinivasan Arunachalam, Oded Regev, Penghui Yao#### On the Gaussian surface area of spectrahedra

__
TR00-073
| 28th August 2000
__

Venkatesan Guruswami, Sanjeev Khanna#### On the Hardness of 4-coloring a 3-colorable Graph

__
TR18-026
| 7th February 2018
__

Lijie Chen#### On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product

Revisions: 1

__
TR03-020
| 27th March 2003
__

Elad Hazan, Shmuel Safra, Oded Schwartz#### On the Hardness of Approximating k-Dimensional Matching

__
TR99-015
| 25th April 1999
__

Irit Dinur, S. Safra#### On the hardness of approximating label cover

__
TR04-119
| 8th December 2004
__

Uriel Feige, Daniel Reichman#### On The Hardness of Approximating Max-Satisfy

__
TR20-146
| 24th September 2020
__

Scott Aaronson, Yosi Atia, Leonard Susskind#### On the Hardness of Detecting Macroscopic Superpositions

__
TR15-193
| 26th November 2015
__

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

__
TR05-113
| 12th September 2005
__

Bernhard Fuchs#### On the Hardness of Range Assignment Problems

__
TR19-123
| 12th September 2019
__

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell#### On the Hardness of Robust Classification

__
TR09-103
| 26th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### On the Hardness of the Noncommutative Determinant

__
TR06-067
| 12th April 2006
__

Heiner Ackermann, Heiko Röglin, Berthold Vöcking#### On the Impact of Combinatorial Structure on Congestion Games

__
TR03-045
| 8th June 2003
__

Oded Goldreich, Asaf Nussboim#### On the Implementation of Huge Random Objects

Revisions: 1

__
TR16-118
| 31st July 2016
__

Shachar Lovett, Jiapeng Zhang#### On the impossibility of entropy reversal, and its application to zero-knowledge proofs

__
TR15-209
| 29th December 2015
__

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

__
TR01-040
| 16th May 2001
__

Pierre Péladeau, Denis Thérien#### On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

__
TR05-028
| 12th February 2005
__

Elmar Böhler#### On the Lattice of Clones Below the Polynomial Time Functions

__
TR16-119
| 1st August 2016
__

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov#### On the Limits of Gate Elimination

Revisions: 1

__
TR97-031
| 9th September 1997
__

Oded Goldreich#### On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

__
TR11-131
| 29th September 2011
__

Rahul Santhanam, Srikanth Srinivasan#### On the Limits of Sparsification

__
TR20-070
| 4th May 2020
__

Ben Lund, Aditya Potukuchi#### On the list recoverability of randomly punctured codes

Revisions: 1

__
TR10-003
| 6th January 2010
__

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty#### On the List-Decodability of Random Linear Codes

__
TR11-100
| 20th July 2011
__

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin#### On the Locality of Codeword Symbols

__
TR21-175
| 6th December 2021
__

Oded Goldreich#### On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

__
TR16-003
| 2nd December 2015
__

Boris Brimkov, Illya Hicks#### On the logspace shortest path problem

__
TR09-091
| 23rd September 2009
__

Thanh Minh Hoang#### On the Matching Problem for Special Graph Classes

Revisions: 1

__
TR96-018
| 23rd February 1996
__

Oded Goldreich, Johan Håstad#### On the Message Complexity of Interactive Proof Systems

Revisions: 2

__
TR10-178
| 17th November 2010
__

Amir Shpilka, Avishay Tal#### On the Minimal Fourier Degree of Symmetric Boolean Functions

__
TR14-167
| 11th November 2014
__

Beate Bollig#### On the Minimization of (Complete) Ordered Binary Decision Diagrams

__
TR18-072
| 19th April 2018
__

Avi Wigderson#### On the nature of the Theory of Computation (ToC)

__
TR08-056
| 22nd April 2008
__

Beate Bollig#### On the OBDD complexity of the most significant bit of integer multiplication

__
TR12-175
| 13th December 2012
__

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan#### On the One-Way Function Candidate Proposed by Goldreich

Revisions: 1

__
TR11-069
| 18th April 2011
__

Marius Zimand#### On the optimal compression of sets in PSPACE

__
TR09-124
| 24th November 2009
__

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi#### On the Optimality of a Class of LP-based Algorithms

Revisions: 1

__
TR15-127
| 7th August 2015
__

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

Revisions: 1

__
TR17-186
| 29th November 2017
__

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi#### On the Parameterized Complexity of Approximating Dominating Set

Revisions: 1

__
TR22-090
| 24th June 2022
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials

__
TR99-028
| 30th August 1999
__

Stefan Edelkamp, Ingo Wegener#### On the performance of WEAK-HEAPSORT

__
TR12-101
| 10th August 2012
__

Oded Goldreich, Shafi Goldwasser, Dana Ron#### On the possibilities and limitations of pseudodeterministic algorithms

__
TR21-056
| 22nd April 2021
__

Yanyi Liu, Rafael Pass#### On the Possibility of Basing Cryptography on $\EXP \neq \BPP$

__
TR21-012
| 9th February 2021
__

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson#### On the Power and Limitations of Branch and Cut

Revisions: 2

__
TR00-054
| 5th May 2000
__

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri#### On the power assignment problem in radio networks

__
TR24-054
| 13th March 2024
__

Karthik Gajulapalli, Alexander Golovnev, Samuel King#### On the Power of Adaptivity for Function Inversion

__
TR11-083
| 22nd May 2011
__

Eric Allender, Fengming Wang#### On the power of algebraic branching programs of width two

__
TR95-046
| 4th August 1995
__

Vince Grolmusz#### On the Power of Circuits with Gates of Low L_1 Norms

__
TR12-154
| 31st October 2012
__

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah#### On the Power of Conditional Samples in Distribution Testing

Revisions: 1

__
TR94-026
| 12th December 1994
__

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener#### On the Power of Different Types of Restricted Branching Programs

__
TR00-077
| 24th August 2000
__

Till Tantau#### On the Power of Extra Queries to Selective Languages

Revisions: 1

__
TR23-191
| 2nd December 2023
__

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### On the Power of Homogeneous Algebraic Formulas

__
TR14-045
| 7th April 2014
__

Mrinal Kumar, Shubhangi Saraf#### On the power of homogeneous depth 4 arithmetic circuits

Revisions: 2

__
TR09-024
| 26th February 2009
__

Raghav Kulkarni#### On the Power of Isolation in Planar Structures

__
TR97-029
| 20th August 1997
__

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger#### On the Power of Las Vegas for One-way Communication Complexity, Finite Automata, and Polynomial-time Computations

__
TR99-007
| 10th March 1999
__

Juraj Hromkovic, Georg Schnitger#### On the Power of Las Vegas II: Two-Way Finite Automata

__
TR08-091
| 10th September 2008
__

Vitaly Feldman#### On The Power of Membership Queries in Agnostic Learning

Revisions: 1

__
TR13-137
| 29th September 2013
__

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran#### On the Power of Public-key Encryption in Secure Computation

__
TR02-074
| 26th December 2002
__

Andrew Chi-Chih Yao#### On the Power of Quantum Fingerprinting

__
TR12-129
| 9th October 2012
__

Iftach Haitner, Eran Omri, Hila Zarosim#### On the Power of Random Oracles

Revisions: 3

__
TR95-054
| 24th November 1995
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Branching Programs

__
TR98-004
| 13th January 1998
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Ordered Branching Programs

__
TR23-102
| 13th July 2023
__

Chin Ho Lee, Edward Pyne, Salil Vadhan#### On the Power of Regular and Permutation Branching Programs

__
TR05-135
| 19th November 2005
__

Iftach Haitner, Danny Harnik, Omer Reingold#### On the Power of the Randomized Iterate

__
TR10-009
| 13th January 2010
__

A. Pavan, Raghunath Tewari, N. V. Vinodchandran#### On the Power of Unambiguity in Logspace

__
TR14-050
| 21st March 2014
__

Edward Hirsch, Dmitry Sokolov#### On the probabilistic closure of the loose unambiguous hierarchy

Revisions: 1

__
TR21-098
| 7th July 2021
__

Srikanth Srinivasan, S Venkitesh#### On the Probabilistic Degree of an $n$-variate Boolean Function

__
TR18-207
| 5th December 2018
__

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan#### On the Probabilistic Degree of OR over the Reals

__
TR19-138
| 6th October 2019
__

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh#### On the Probabilistic Degrees of Symmetric Boolean functions

__
TR10-054
| 30th March 2010
__

Jan Krajicek#### On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

__
TR02-019
| 20th March 2002
__

Nader Bshouty, Lynn Burroughs#### On the proper learning of axis parallel concepts

__
TR11-038
| 10th March 2011
__

Jiapeng Zhang#### On the query complexity for Showing Dense Model

__
TR05-082
| 3rd June 2005
__

Jorge Castro#### On the Query Complexity of Quantum Learners

__
TR14-031
| 16th February 2014
__

Joao Marques-Silva, Mikolas Janota#### On the Query Complexity of Selecting Few Minimal Sets

__
TR24-047
| 8th March 2024
__

Oded Goldreich#### On the query complexity of testing local graph properties in the bounded-degree graph model

Revisions: 1

__
TR23-193
| 3rd December 2023
__

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz#### On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity

Revisions: 1

__
TR07-015
| 1st March 2007
__

Oded Goldreich, Or Sheffet#### On the randomness complexity of property testing

__
TR22-048
| 4th April 2022
__

Hanlin Ren, Rahul Santhanam, Zhikun Wang#### On the Range Avoidance Problem for Circuits

__
TR23-154
| 12th October 2023
__

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer#### On the Rational Degree of Boolean Functions and Applications

__
TR07-061
| 12th July 2007
__

Or Meir#### On the Rectangle Method in proofs of Robustness of Tensor Products

Revisions: 4

__
TR10-036
| 8th March 2010
__

Amir Shpilka, Ilya Volkovich#### On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

__
TR15-186
| 24th November 2015
__

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

__
TR07-126
| 5th November 2007
__

Nathan Segerlind#### On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs

__
TR10-045
| 15th March 2010
__

Jakob Nordström#### On the Relative Strength of Pebbling and Resolution

Revisions: 1

__
TR24-078
| 19th April 2024
__

Oded Goldreich#### On the relaxed LDC of BGHSV: A survey that corrects the record

Revisions: 1

__
TR04-109
| 15th November 2004
__

Neeraj Kayal, Nitin Saxena#### On the Ring Isomorphism & Automorphism Problems

__
TR05-104
| 16th September 2005
__

Don Coppersmith, Atri Rudra#### On the Robust Testability of Product of Codes

__
TR14-062
| 22nd March 2014
__

Alexander Kozachinsky#### On the role of private coins in unbounded-round Information Complexity

__
TR15-137
| 22nd August 2015
__

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

__
TR99-005
| 21st December 1998
__

Michael Schmitt#### On the Sample Complexity for Nonoverlapping Neural Networks

__
TR04-033
| 23rd January 2004
__

Michael Schmitt#### On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions

__
TR06-104
| 25th August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On the Sample Complexity of MAX-CUT

__
TR00-045
| 23rd June 2000
__

Maria Isabel Gonzalez Vasco, Igor E. Shparlinski#### On the Security of Diffie--Hellman Bits

__
TR01-007
| 7th December 2000
__

Vered Rosen#### On the Security of Modular Exponentiation

Comments: 1

__
TR02-049
| 4th August 2002
__

Oded Goldreich, Vered Rosen#### On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators

__
TR97-027
| 29th April 1997
__

Johannes Merkle, Ralph Werchner#### On the Security of Server aided RSA protocols

Revisions: 1

__
TR16-062
| 18th April 2016
__

Avishay Tal#### On The Sensitivity Conjecture

__
TR16-132
| 23rd August 2016
__

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker#### On the Sensitivity Conjecture for Read-k Formulas

__
TR05-020
| 22nd November 2004
__

Sourav Chakraborty#### On the Sensitivity of Cyclically-Invariant Boolean Functions

__
TR13-043
| 25th March 2013
__

Oded Goldreich, Avi Wigderson#### On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions

Revisions: 1

__
TR15-181
| 13th November 2015
__

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

__
TR14-170
| 10th December 2014
__

Yael Tauman Kalai, Ran Raz#### On the Space Complexity of Linear Programming with Preprocessing

Revisions: 1

__
TR12-150
| 1st November 2012
__

Michael Elberfeld, Christoph Stockhusen, Till Tantau#### On the Space Complexity of Parameterized Problems

Revisions: 1

__
TR01-008
| 6th November 2000
__

Eldar Fischer#### On the strength of comparisons in property testing

__
TR21-182
| 30th December 2021
__

Ilario Bonacina, Maria Luisa Bonet#### On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

__
TR13-049
| 1st April 2013
__

Amir Shpilka, Ben Lee Volk, Avishay Tal#### On the Structure of Boolean Functions with Small Spectral Norm

Revisions: 1

__
TR09-080
| 19th September 2009
__

Elad Haramaty, Amir Shpilka#### On the Structure of Cubic and Quartic Polynomials

Revisions: 1

__
TR21-173
| 5th December 2021
__

Ninad Rajgopal, Rahul Santhanam#### On the Structure of Learnability beyond P/poly

__
TR15-101
| 15th June 2015
__

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

Revisions: 2

__
TR06-146
| 30th September 2006
__

Christoph Buchheim, Peter J Cameron, Taoyang Wu#### On the Subgroup Distance Problem

__
TR13-039
| 18th March 2013
__

Arturs Backurs, Mohammad Bavarian#### On the sum of $L1$ influences

Revisions: 2

__
TR10-189
| 8th December 2010
__

Neeraj Kayal, Chandan Saha#### On the Sum of Square Roots of Polynomials and related problems

__
TR18-164
| 18th September 2018
__

Nikhil Gupta, Chandan Saha#### On the symmetries of design polynomials

Revisions: 1

__
TR18-185
| 6th November 2018
__

Yonatan Nakar, Dana Ron#### On the Testability of Graph Partition Properties

__
TR06-018
| 8th February 2006
__

Jin-Yi Cai, Vinay Choudhary#### On the Theory of Matchgate Computations

__
TR99-021
| 8th April 1999
__

Igor E. Shparlinski#### ON THE UNIFORMITY OF DISTRIBUTION OF A CERTAIN PSEUDO-RANDOM FUNCTION

__
TR24-083
| 18th April 2024
__

Lijie Chen, Jiatu Li, Igor Carboni Oliveira#### On the Unprovability of Circuit Size Bounds in Intuitionistic $S^1_2$

__
TR08-024
| 26th February 2008
__

Paul Beame, Trinh Huynh#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

__
TR22-139
| 15th October 2022
__

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan#### On the VNP-hardness of Some Monomial Symmetric Polynomials

__
TR16-010
| 28th January 2016
__

Alexander Razborov#### On the Width of Semi-Algebraic Proofs and Algorithms

__
TR18-068
| 8th April 2018
__

Mrinal Kumar#### On top fan-in vs formal degree for depth-3 arithmetic circuits

Revisions: 1

__
TR19-020
| 4th February 2019
__

Ludmila Glinskih, Dmitry Itsykson#### On Tseitin formulas, read-once branching programs and treewidth

Revisions: 1

__
TR13-019
| 31st January 2013
__

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf#### On Two-Level Poset Games

__
TR01-039
| 18th May 2001
__

Stasys Jukna, Stanislav Zak#### On Uncertainty versus Size in Branching Programs

Revisions: 1

__
TR14-036
| 8th March 2014
__

Mikolas Janota, Leroy Chew, Olaf Beyersdorff#### On Unification of QBF Resolution-Based Calculi

Revisions: 1

__
TR22-105
| 18th July 2022
__

Ilario Bonacina, Nicola Galesi, Massimo Lauria#### On vanishing sums of roots of unity in polynomial calculus and sum-of-squares

__
TR17-087
| 9th May 2017
__

Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar#### On Weak-Space Complexity over Complex Numbers

__
TR21-161
| 16th November 2021
__

Shuichi Hirahara, Mikito Nanashima#### On Worst-Case Learning in Relativized Heuristica

__
TR05-015
| 27th January 2005
__

Andrej Bogdanov, Luca Trevisan#### On Worst-Case to Average-Case Reductions for NP Problems

__
TR95-050
| 15th October 1995
__

Oded Goldreich, Noam Nisan, Avi Wigderson#### On Yao's XOR-Lemma

Revisions: 2
,
Comments: 1

__
TR03-052
| 13th May 2003
__

Stanislav Busygin, Dmitrii V. Pasechnik#### On ~chi(G)-alpha(G)>0 gap recognition and alpha(G)-upper bounds

__
TR00-063
| 13th July 2000
__

Peter Auer#### On-line Learning of Rectangles in Noisy Environments

__
TR00-071
| 14th July 2000
__

Peter Auer, Nicolo Cesa-Bianchi#### On-line Learning with Malicious Noise and the Closure Algorithm

__
TR00-001
| 14th January 2000
__

Piotr Berman, Moses Charikar, Marek Karpinski#### On-Line Load Balancing for Related Machines

__
TR23-148
| 3rd October 2023
__

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz#### One Clean Qubit Suffices for Quantum Communication Advantage

__
TR99-014
| 30th May 1999
__

Alexander Razborov, Nikolay Vereshchagin#### One Property of Cross-Intersecting Families

__
TR14-091
| 22nd July 2014
__

Ryan O'Donnell, A. C. Cem Say#### One time-travelling bit is as good as logarithmically many

Revisions: 1

__
TR12-091
| 16th July 2012
__

Abuzer Yakaryilmaz#### One-counter verifiers for decidable languages

__
TR06-130
| 27th September 2006
__

Tanmoy Chakraborty, Samir Datta#### One-input-face MPCVP is Hard for L, but in LogDCFL

__
TR13-013
| 18th January 2013
__

Daniel Apon, Jonathan Katz, Alex Malozemoff#### One-Round Multi-Party Communication Complexity of Distinguishing Sums

Revisions: 1

__
TR16-173
| 5th November 2016
__

Egor Klenin, Alexander Kozachinsky#### One-sided error communication complexity of Gap Hamming Distance

Revisions: 2

__
TR20-068
| 3rd May 2020
__

Oded Goldreich, Dana Ron#### One-Sided Error Testing of Monomials and Affine Subspaces

Revisions: 2

__
TR20-103
| 9th July 2020
__

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida#### One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Revisions: 1

__
TR17-152
| 9th October 2017
__

Swagato Sanyal#### One-way Communication and Non-adaptive Decision Tree

Comments: 1

__
TR21-065
| 5th May 2021
__

Nikhil Mande, Swagato Sanyal#### One-way communication complexity and non-adaptive decision trees

Revisions: 1

__
TR23-157
| 31st October 2023
__

Vladimir Podolskii, Dmitrii Sluch#### One-Way Communication Complexity of Partial XOR Functions

Revisions: 1

__
TR03-083
| 21st November 2003
__

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz#### One-Way Communication Complexity of Symmetric Boolean Functions

__
TR23-152
| 14th October 2023
__

Yanyi Liu, Rafael Pass#### One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions

__
TR21-009
| 1st February 2021
__

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich#### One-way Functions and Partial MCSP

Revisions: 3
,
Comments: 1

__
TR24-136
| 4th September 2024
__

Shuichi Hirahara, Zhenjian Lu, Igor Oliveira#### One-Way Functions and pKt Complexity

__
TR09-019
| 10th March 2009
__

Agrawal Manindra, Osamu Watanabe#### One-Way Functions and the Isomorphism Conjecture

__
TR24-063
| 6th April 2024
__

Shuichi Hirahara, Mikito Nanashima#### One-Way Functions and Zero Knowledge

__
TR07-079
| 11th August 2007
__

Emanuele Viola, Avi Wigderson#### One-way multi-party communication lower bound for pointer jumping with applications

__
TR09-097
| 2nd September 2009
__

Rakesh Mohanty, N. S. Narayanaswamy#### Online Algorithms for Self-Organizing Sequential Search - A Survey

__
TR10-016
| 22nd December 2009
__

Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking#### Online Capacity Maximization in Wireless Networks

__
TR05-161
| 13th December 2005
__

John Hitchcock#### Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

__
TR21-088
| 23rd June 2021
__

Oded Goldreich#### Open Problems in Property Testing of Graphs

Revisions: 1

__
TR23-208
| 21st December 2023
__

Dean Doron, Edward Pyne, Roei Tell#### Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL

__
TR96-061
| 27th November 1996
__

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener#### Optimal attribute-efficient learning of disjunction, parity, and threshold functions

__
TR12-030
| 4th April 2012
__

C. Seshadhri, Deeparnab Chakrabarty#### Optimal bounds for monotonicity and Lipschitz testing over the hypercube

Revisions: 2

__
TR10-025
| 24th February 2010
__

Alexander A. Sherstov#### Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

__
TR95-041
| 28th June 1995
__

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim#### Optimal Bounds for the Approximation of Boolean Functions and Some Applications

__
TR12-104
| 8th August 2012
__

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman#### Optimal Coding for Streaming Authentication and Interactive Communication

Revisions: 1

__
TR22-056
| 18th April 2022
__

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand#### Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

__
TR10-106
| 17th June 2010
__

Yuichi Yoshida#### Optimal Constant-Time Approximation Algorithms and (Unconditional) Inapproximability Results for Every Bounded-Degree CSP

Revisions: 1

__
TR12-176
| 14th December 2012
__

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu#### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

__
TR20-069
| 4th May 2020
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Optimal Error Pseudodistributions for Read-Once Branching Programs

Revisions: 1

__
TR21-060
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Optimal Error Resilience of Adaptive Message Exchange

__
TR06-032
| 25th February 2006
__

Vitaly Feldman#### Optimal Hardness Results for Maximizing Agreements with Monomials

__
TR11-091
| 20th May 2011
__

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal#### Optimal heuristic algorithms for the image of an injective function

__
TR12-158
| 14th November 2012
__

Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan#### Optimal Hitting Sets for Combinatorial Shapes

__
TR20-130
| 30th August 2020
__

Amey Bhangale, Subhash Khot#### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

__
TR05-101
| 20th September 2005
__

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel#### Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

__
TR19-151
| 5th November 2019
__

Per Austrin, Jonah Brown-Cohen, Johan Håstad#### Optimal Inapproximability with Universal Factor Graphs

__
TR17-079
| 1st May 2017
__

Alexander A. Sherstov, Pei Wu#### Optimal Interactive Coding for Insertions, Deletions, and Substitutions

__
TR18-129
| 13th July 2018
__

Jelani Nelson, Huacheng Yu#### Optimal Lower Bounds for Distributed and Streaming Spanning Forest Computation

Revisions: 1

__
TR09-130
| 1st December 2009
__

Ryan O'Donnell, YI WU, Yuan Zhou#### Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

__
TR23-197
| 7th December 2023
__

Sepehr Assadi, Gillat Kol, Zhijun Zhang#### Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

__
TR96-022
| 15th March 1996
__

Martin Sauerhoff, Ingo Wegener, Ralph Werchner#### Optimal Ordered Binary Decision Diagrams for Tree-like Circuits

__
TR08-107
| 12th November 2008
__

Zenon Sadowski#### Optimal Proof Systems and Complete Languages

__
TR97-026
| 18th June 1997
__

Jochen Me\3ner, Jacobo Toran#### Optimal proof systems for Propositional Logic and complete sets

__
TR24-028
| 19th February 2024
__

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk#### Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields

__
TR24-039
| 20th February 2024
__

Shuichi Hirahara, Naoto Ohsaka#### Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration

__
TR24-065
| 6th April 2024
__

Meghal Gupta, Mihir Singhal, Hongxun Wu#### Optimal quantile estimation: beyond the comparison model

__
TR13-046
| 27th March 2013
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets

__
TR20-172
| 13th November 2020
__

Venkatesan Guruswami, Chaoping Xing#### Optimal rate list decoding over bounded alphabets using algebraic-geometric codes

__
TR16-166
| 1st November 2016
__

Mark Braverman, Ran Gelles, Michael A. Yitayew#### Optimal Resilience for Short-Circuit Noise in Formulas

Revisions: 1

__
TR96-044
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Optimal Search in Trees

Revisions: 1

__
TR09-061
| 2nd July 2009
__

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani#### Optimal Sherali-Adams Gaps from Pairwise Independence

__
TR20-140
| 14th September 2020
__

Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price#### Optimal Testing of Discrete Distributions with High Probability

__
TR11-059
| 15th April 2011
__

Elad Haramaty, Amir Shpilka, Madhu Sudan#### Optimal testing of multivariate polynomials over small prime fields

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR04-049
| 15th June 2004
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Optimal Trade-Off for Merkle Tree Traversal

__
TR17-049
| 14th March 2017
__

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri#### Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

__
TR18-169
| 18th September 2018
__

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev#### Optimality of Linear Sketching under Modular Updates

__
TR19-153
| 6th November 2019
__

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi#### Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

__
TR01-069
| 24th October 2001
__

Robert Albin Legenstein#### Optimizing the Layout of a Balanced Tree

Revisions: 1

__
TR18-107
| 31st May 2018
__

Ran Raz, Avishay Tal#### Oracle Separation of BQP and PH

__
TR95-015
| 6th February 1995
__

Bshouty, Cleve, Gavalda, Kannan, Tamon.#### Oracles and queries that are sufficient for exact learning

__
TR05-040
| 13th April 2005
__

Scott Aaronson#### Oracles Are Subtle But Not Malicious

__
TR98-039
| 14th July 1998
__

Christoph Meinel, Thorsten Theobald#### Ordered Binary Decision Diagrams and Their Significance in Computer-Aided Design of VLSI Circuits - a Survey

__
TR09-087
| 1st October 2009
__

Olga Tveretina, Carsten Sinz, Hans Zantema#### Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond

__
TR05-131
| 7th November 2005
__

Don Coppersmith, Lisa Fleischer, Atri Rudra#### Ordering by weighted number of wins gives a good ranking for weighted tournaments

__
TR16-053
| 6th April 2016
__

Jiawei Gao, Russell Impagliazzo#### Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

__
TR11-132
| 2nd September 2011
__

Ludwig Staiger#### Oscillation-free Chaitin $h$-random sequences

Revisions: 1

__
TR20-176
| 26th November 2020
__

Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona#### Outcome Indistinguishability

__
TR13-189
| 21st December 2013
__

Periklis Papakonstantinou, Dominik Scheder, Hao Song#### Overlays and Limited Memory Communication Mode(l)s

__
TR17-102
| 9th June 2017
__

Oded Goldreich#### Overview of the doubly-efficient interactive proof systems of RRR

Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe

We show an O(sqrt(n))-space and polynomial-time algorithm for solving the planar directed graph reachability problem. Imai et al. showed in CCC 2013 that the problem is solvable in O(n^{1/2+eps})-space and polynomial-time by using separators for planar graphs, and it has been open whether the space bound can be improved to ... more >>>

Craig Gentry, Charanjit Jutla

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove ... more >>>

Karthik Gajulapalli, Zeyong Li, Ilya Volkovich

In this work we study oblivious complexity classes. Among our results:

1) For each $k \in \mathbb{N}$, we construct an explicit language $L_k \in O_2P$ that cannot be computed by circuits of size $n^k$.

2) We prove a hierarchy theorem for $O_2TIME$. In particular, for any function $t:\mathbb{N} \rightarrow \mathbb{N}$ ...
more >>>

Miklos Ajtai

Abstract. We show that oblivious on-line simulation with only

polylogarithmic increase in the time and space requirements is possible

on a probabilistic (coin flipping) RAM without using any cryptographic

assumptions. The simulation will fail with a negligible probability.

If $n$ memory locations are used, then the probability of failure is ...
more >>>

Xiaotie Deng, Zhe Feng, Rucha Kulkarni

The Octahedral Tucker problem considers an n-dimensional hypergrid of side length two, centered at the origin, triangulated by connecting the origin to all outside vertices (applied recursively on each of the lower dimensional hypergrids passing through their origins at the corresponding reduced dimensions). Each vertex is assigned a color in ... more >>>

Mohammad Mahmoody, David Xiao

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

An $r$-simple $k$-path is a {path} in the graph of length $k$ that

passes through each vertex at most $r$ times. The \simpath{r}{k}

problem, given a graph $G$ as input, asks whether there exists an

$r$-simple $k$-path in $G$. We first show that this problem is

NP-Complete. We then show ...
more >>>

Naomi Kirshner, Alex Samorodnitsky

Given a subset $A\subseteq \{0,1\}^n$, let $\mu(A)$ be the maximal ratio between $\ell_4$ and $\ell_2$ norms of a function whose Fourier support is a subset of $A$. We make some simple observations about the connections between $\mu(A)$ and the additive properties of $A$ on one hand, and between $\mu(A)$ and ... more >>>

Pavel Hrubes

We show that strong-enough lower bounds on monotone arithmetic circuits or the non-negative rank of a matrix imply unconditional lower bounds in arithmetic or Boolean circuit complexity. First, we show that if a polynomial $f\in {\mathbb {R}}[x_1,\dots, x_n]$ of degree $d$ has an arithmetic circuit of size $s$ then $(x_1+\dots+x_n+1)^d+\epsilon ... more >>>

Yogesh Dahiya, Meena Mahajan

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>

Zenon Sadowski

The notion of an optimal acceptor for TAUT (the optimality

property is stated only for input strings from TAUT) comes from the line

of research aimed at resolving the question of whether optimal

propositional proof systems exist. In this paper we introduce two new

types of optimal acceptors, a D-N-optimal ...
more >>>

Sergei Lozhkin, Alexander Shiganov

In this paper we suggest a modification of classical Lupanov's method [Lupanov1958]

that allows building circuits over the basis $\{\&,\vee,\neg\}$ for Boolean functions of $n$ variables with size at most

$$

\frac{2^n}{n}\left(1+\frac{3\log n + O(1)}{n}\right),

$$

and with more uniform distribution of outgoing arcs by circuit gates.

For almost all ... more >>>

Henning Wunderlich, Stefan Arnold

We introduce a new lower bound method for bounded-error quantum communication complexity,

the \emph{singular value method (svm)}, based on sums of squared singular values of the

communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the

spectral ...
more >>>

Rocco Servedio, Emanuele Viola

We highlight the special case of Valiant's rigidity

problem in which the low-rank matrices are truth-tables

of sparse polynomials. We show that progress on this

special case entails that Inner Product is not computable

by small $\acz$ circuits with one layer of parity gates

close to the inputs. We then ...
more >>>

Argimiro Arratia, Carlos E. Ortiz

We formulate a formal syntax of approximate formulas for the logic with counting

quantifiers, $\mathcal{SOLP}$, studied by us in \cite{aaco06}, where we showed the

following facts:

$(i)$ In the presence of a built--in (linear) order, $\mathcal{SOLP}$ can

describe {\bf NP}--complete problems and fragments of it capture classes like

{\bf P} ...
more >>>

Henning Wunderlich

In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly ...
more >>>

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

In 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the ... more >>>

Prerona Chatterjee, Anamay Tengse

We study the algebraic complexity of annihilators of polynomials maps. In particular, when a polynomial map is `encoded by' a small algebraic circuit, we show that the coefficients of an annihilator of the map can be computed in PSPACE. Even when the underlying field is that of reals or complex ... more >>>

Marek Karpinski

We survey some recent results on the complexity of computing

approximate solutions for instances of the Minimum Bisection problem

and formulate some intriguing and still open questions about the

approximability status of that problem. Some connections to other

optimization problems are also indicated.

Amey Bhangale, Subhash Khot, Dor Minzer

We consider the $P$-CSP problem for $3$-ary predicates $P$ on satisfiable instances. We show that under certain conditions on $P$ and a $(1,s)$ integrality gap instance of the $P$-CSP problem, it can be translated into a dictatorship vs. quasirandomness test with perfect completeness and soundness $s+\varepsilon$, for every constant $\varepsilon>0$. ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

Let $\Sigma$ be an alphabet and $\mu$ be a distribution on $\Sigma^k$ for some $k \geq 2$. Let $\alpha > 0$ be the minimum probability of a tuple in the support of $\mu$ (denoted by $supp(\mu)$). Here, the support of $\mu$ is the set of all tuples in $\Sigma^k$ that ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

We prove a stability result for general $3$-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if $\Sigma,\Gamma$ and $\Phi$ are alphabets of constant size, and $\mu$ is a pairwise connected distribution over $\Sigma\times\Gamma\times\Phi$ with no $(\mathbb{Z},+)$ embeddings in which the probability of each atom is ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

We propose a framework of algorithm vs. hardness for all Max-CSPs and demonstrate it for a large class of predicates. This framework extends the work of Raghavendra [STOC, 2008], who showed a similar result for almost satisfiable Max-CSPs.

Our framework is based on a new hybrid approximation algorithm, which uses ... more >>>

U. Faigle, S.P. Fekete, W. Hochstättler, W. Kern

We consider the problem of fair cost allocation for traveling

salesman games for which the triangle inequality holds. We

give examples showing that the core of such games may be

empty, even for the case of Euclidean distances. On the

positive side, we develop an LP-based ...
more >>>

Johan Håstad

We prove that any constraint satisfaction problem

where each variable appears a bounded number of

times admits a nontrivial polynomial time approximation

algorithm.

Bodo Manthey

A cycle cover of a graph is a set of cycles such that every vertex is

part of exactly one cycle. An L-cycle cover is a cycle cover in which

the length of every cycle is in the set L. The weight of a cycle cover

of an edge-weighted graph ...
more >>>

Dean Doron, Amir Sarid, Amnon Ta-Shma

Approximating the eigenvalues of a Hermitian operator can be solved

by a quantum logspace algorithm. We introduce the problem of

approximating the eigenvalues of a given matrix in the context of

classical space-bounded computation. We show that:

- Approximating the second eigenvalue of stochastic operators (in a

certain range of ...
more >>>

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):

Given a low-degree polynomial mapping

$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy

$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

Michal Parnas, Dana Ron

We consider the problem of estimating the size, $VC(G)$, of a

minimum vertex cover of a graph $G$, in sublinear time,

by querying the incidence relation of the graph. We say that

an algorithm is an $(\alpha,\eps)$-approximation algorithm

if it outputs with high probability an estimate $\widehat{VC}$

such that ...
more >>>

Dana Ron, Gilad Tsur

In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a ... more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is

the problem of finding a tour of minimum length in a complete

weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy

$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ...
more >>>

Marek Karpinski, Juergen Wirtgen

The bandwidth problem is the problem of enumerating

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 a number of applications

and is ...
more >>>

Gunter Blache, Marek Karpinski, Juergen Wirtgen

The bandwidth problem is the problem of enumerating

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 a number of applications.

There was not ...
more >>>

Marek Karpinski, Richard Schmied

We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>>

Andrzej Lingas, Martin Wahlén

We consider the ``minor'' and ``homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest $h$ such that the input graph has a minor isomorphic to $K_h$ or a subgraph homeomorphic to $K_h,$ respectively.We show the former to be approximable within $O(\sqrt {n} \log^{1.5} n)$ by ... more >>>

Vitaly Feldman

We consider the problems of attribute-efficient PAC learning of two well-studied concept classes: parity functions and DNF expressions over $\{0,1\}^n$. We show that attribute-efficient learning of parities with respect to the uniform distribution is equivalent to decoding high-rate random linear codes from low number of errors, a long-standing open problem ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

Tomas Feder, Carlos Subi

Barnette's conjecture is the statement that every 3-connected cubic

planar bipartite graph is Hamiltonian. Goodey showed that the conjecture

holds when all faces of the graph have either 4 or 6 sides. We

generalize Goodey's result by showing that when the faces of such a

graph are 3-colored, with adjacent ...
more >>>

Mikito Nanashima

A black-box (BB) reduction is a central proof technique in theoretical computer science. However, the limitations on BB reductions have been revealed for several decades, and the series of previous work gives strong evidence that we should avoid a nonadaptive BB reduction to base cryptography on NP-hardness (e.g., Akavia et ... more >>>

Andrej Bogdanov, Christina Brzuska

We prove that if the hardness of inverting a size-verifiable one-way function can

be based on NP-hardness via a general (adaptive) reduction, then coAM is contained in NP. This

claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but

was later retracted (STOC 2010).

David Xiao

Learning is a central task in computer science, and there are various

formalisms for capturing the notion. One important model studied in

computational learning theory is the PAC model of Valiant (CACM 1984).

On the other hand, in cryptography the notion of ``learning nothing''

is often modelled by the simulation ...
more >>>

Bill Fefferman, Ronen Shaltiel, Chris Umans, Emanuele Viola

The {\em hybrid argument}

allows one to relate

the {\em distinguishability} of a distribution (from

uniform) to the {\em

predictability} of individual bits given a prefix. The

argument incurs a loss of a factor $k$ equal to the

bit-length of the

distributions: $\epsilon$-distinguishability implies only

$\epsilon/k$-predictability. ...
more >>>

Roei Tell

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

Jin-Yi Cai, Pinyan Lu

We give a classification of block-wise symmetric signatures

in the theory of matchgate computations. The main proof technique

is matchgate identities, a.k.a. useful Grassmann-Pl\"{u}cker

identities.

Daniel Avraham , Amir Yehudayoff

A matrix is blocky if it is a blowup of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. ... more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving

lower bounds on the size of branching programs (b.p.). The argument

is based on Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during various

stages of the computation. ...
more >>>

Albert Atserias, Maria Luisa Bonet, Jordi Levy

We study the Chv\'atal rank of polytopes as a complexity measure of

unsatisfiable sets of clauses. Our first result establishes a

connection between the Chv\'atal rank and the minimum refutation

length in the cutting planes proof system. The result implies that

length lower bounds for cutting planes, or even for ...
more >>>

Karthik C. S., Pasin Manurangsi

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

Thomas Thierauf, Thanh Minh Hoang

We show necessary and sufficient conditions that

certain algebraic functions like the rank or the signature

of an integer matrix can be computed in GapL.

Oded Goldreich

For any fixed $t$, we present two fine-grained reductions of the problem of approximately counting the number of $t$-cliques in a graph to the problem of detecting a $t$-clique in a graph.

One of our reductions is slightly better than the prior reduction of Dell, Lapinskas, and Meeks (SODA20) and ...
more >>>

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of ... more >>>

Predrag Tosic

We study the computational complexity of counting the fixed point configurations in certain discrete dynamical systems. We prove that both exact and approximate counting in Sequential and Synchronous Dynamical Systems (SDSs and SyDS, respectrively) is computationally intractable, even when each node is required to update according to a symmetric Boolean ... more >>>

Li-Sha Huang, Xiaotie Deng

We consider the computational complexity of the market equilibrium

problem by exploring the structural properties of the Leontief

exchange economy. We prove that, for economies guaranteed to have

a market equilibrium, finding one with maximum social welfare or

maximum individual welfare is NP-hard. In addition, we prove that

counting the ...
more >>>

Farid Ablayev, Airat Khasianov, Alexander Vasiliev

We consider Generalized Equality, the Hidden Subgroup,

and related problems in the context of quantum Ordered Binary

Decision Diagrams. For the decision versions of considered problems

we show polynomial upper bounds in terms of quantum OBDD width. We

apply a new modification of the fingerprinting technique and present

the algorithms ...
more >>>

Farid Ablayev

A regular $(1,+k)$-branching program ($(1,+k)$-ReBP) is an

ordinary branching program with the following restrictions: (i)

along every consistent path at most $k$ variables are tested more

than once, (ii) for each node $v$ on all paths from the source to

$v$ the same set $X(v)\subseteq X$ of variables is ...
more >>>

We explore the computational power of formal models for computation

with pulses. Such models are motivated by realistic models for

biological neurons, and by related new types of VLSI (``pulse stream

VLSI'').

In preceding work it was shown that the computational power of formal

models for computation with pulses is ...
more >>>

Pavol Duris

In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. ... more >>>

Suryajith Chillara

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

Oded Goldreich, Avishay Tal

We consider new complexity measures for the model of multilinear circuits with general multilinear gates introduced by Goldreich and Wigderson (ECCC, 2013).

These complexity measures are related to the size of canonical constant-depth Boolean circuits, which extend the definition of canonical depth-three Boolean circuits.

We obtain matching lower and upper ...
more >>>

Oded Goldreich, Leonid Levin, Noam Nisan

We show how to construct length-preserving 1-1 one-way

functions based on popular intractability assumptions (e.g., RSA, DLP).

Such 1-1 functions should not

be confused with (infinite) families of (finite) one-way permutations.

What we want and obtain is a single (infinite) 1-1 one-way function.

Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener

The best-known representations of boolean functions f are those of disjunctions of terms (DNFs) and as conjuctions of clauses (CNFs). It is convenient to define the DNF size of f as the minimal number of terms in a DNF representing f and the CNF size as the minimal number of ... more >>>

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

Khrapchenko's classical lower bound $n^2$ on the formula size of the

parity function~$f$ can be interpreted as designing a suitable

measure of subrectangles of the combinatorial rectangle

$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we

arrived at the concept of \emph{convex measures}. We prove the

more >>>

Peter Ivanov, Liam Pavlovic, Emanuele Viola

We study the fundamental challenge of exhibiting explicit functions that have small correlation with low-degree polynomials over $\mathbb{F}_{2}$. Our main contributions include:

1. In STOC 2020, CHHLZ introduced a new technique to prove correlation bounds. Using their technique they established new correlation bounds for low-degree polynomials. They conjectured that their ... more >>>

Eran Iceland, Alex Samorodnitsky

We suggest a new approach to obtain bounds on locally correctable and some locally testable binary linear codes, by arguing that their coset leader graphs have high discrete Ricci curvature.

The bounds we obtain for locally correctable codes are worse than the best known bounds obtained using quantum information theory, ... more >>>

Andris Ambainis, David Mix Barrington, Huong LeThanh

Continuing the study of the relationship between $TC^0$,

$AC^0$ and arithmetic circuits, started by Agrawal et al.

(IEEE Conference on Computational Complexity'97),

we answer a few questions left open in this

paper. Our main result is that the classes Diff$AC^0$ and

Gap$AC^0$ ...
more >>>

Oded Goldreich

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.

We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ...
more >>>

Martin Dyer, Leslie Ann Goldberg, Michael S. Paterson

We give a dichotomy theorem for the problem of counting homomorphisms to

directed acyclic graphs. $H$ is a fixed directed acyclic graph.

The problem is, given an input digraph $G$, how many homomorphisms are there

from $G$ to $H$. We give a graph-theoretic classification, showing that

for some digraphs $H$, ...
more >>>

Amir M. Ben-Amram, Zvi Galil

Consider a problem involving updates and queries of a data structure.

Assume that there exists a family of algorithms which exhibit a

tradeoff between query and update time. We demonstrate a general

technique of constructing from such a family

a single algorithm with best amortized time. We indicate some ...
more >>>

Peter Buergisser

Let $\tau(n)$ denote the minimum number of arithmetic operations sufficient to build the integer $n$ from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of $n$ by $n$ matrices having size polynomial in $n$, then $\tau(n!)$ is polynomially bounded in $\log n$. Under the ... more >>>

Or Meir

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$

is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$

and computes

\[

(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).

\]

This operation has been used several times for amplifying different

hardness measures of $f$ and $g$. This comes at a cost: the ...
more >>>

Oded Goldreich, Avi Wigderson

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:

For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ...
more >>>

Petr Savicky

Let $f$ be a Boolean function. Let $N(f)=\dnf(f)+\dnf(\neg f)$ be the

sum of the minimum number of monomials in a disjunctive normal form

for $f$ and $\neg f$. Let $p(f)$ be the minimum size of a partition

of the Boolean cube into disjoint subcubes such that $f$ is constant on

more >>>

Paul Beame, Sajin Koroth

Query-to-communication lifting theorems, which connect the query complexity of a Boolean function to the communication complexity of an associated `lifted' function obtained by composing the function with many copies of another function known as a gadget, have been instrumental in resolving many open questions in computational complexity. Several important complexity ... more >>>

Howard Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani

We study the classification problem {\sc Metric Labeling} and its special case {\sc 0-Extension} in the context of earthmover metrics. Researchers recently proposed using earthmover metrics to get a polynomial time-solvable relaxation of {\sc Metric Labeling}; until now, however, no one knew if the integrality ratio was constant or not, ... more >>>

Vikraman Arvind, Pushkar Joglekar

In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring F of polynomials in noncommuting variables x_1,x_2,…,x_n over the field F. We obtain the following result:

Given a noncommutative arithmetic formula of size s computing a noncommutative polynomial f in F as input, where ... more >>>

Jop Briet

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

Oded Goldreich, Maya Leshkowitz

The known emulation of interactive proof systems by public-coins interactive proof systems proceeds by selecting, at each round, a message such that each message is selected with probability that is at most polynomially larger than its probability in the original protocol.

Specifically, the possible messages are essentially clustered according to ...
more >>>

Elchanan Mossel, Amir Shpilka, 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 is always a

distinguisher; ...
more >>>

Oded Goldreich, Dana Ron

Following Feige, we consider the problem of

estimating the average degree of a graph.

Using ``neighbor queries'' as well as ``degree queries'',

we show that the average degree can be approximated

arbitrarily well in sublinear time, unless the graph is extremely sparse

(e.g., unless the graph has a sublinear ...
more >>>

Bernd Borchert, Dietrich Kuske, Frank Stephan

Pin & Weil [PW95] characterized the automata of existentially

first-order definable languages. We will use this result for the following

characterization of the complexity class NP. Assume that the

Polynomial-Time Hierarchy does not collapse. Then a regular language

L characterizes NP as an unbalanced polynomial-time leaf language

if and ...
more >>>

Jonathan Katz, Chiu-Yuen Koo

In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the ... more >>>

Oded Goldreich

This paper concerns the possibility of developing a coherent

theory of security when feasibility is associated

with expected probabilistic polynomial-time (expected PPT).

The source of difficulty is that

the known definitions of expected PPT strategies

(i.e., expected PPT interactive machines)

do not support natural results of the ...
more >>>

Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev

The Exponential-Time Hypothesis ($ETH$) is a strengthening of the $\mathcal{P} \neq \mathcal{NP}$ conjecture, stating that $3\text{-}SAT$ on $n$ variables cannot be solved in time $2^{\epsilon\cdot n}$, for some $\epsilon>0$. In recent years, analogous hypotheses that are ``exponentially-strong'' forms of other classical complexity conjectures (such as $\mathcal{NP}\not\subseteq\mathcal{BPP}$ or $co\text{-}\mathcal{NP}\not\subseteq \mathcal{NP}$) have ... more >>>

Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao

If $k<n$, can one express the majority of $n$ bits as the majority of at most $k$ majorities, each of at most $k$ bits? We prove that such an expression is possible only if $k = \Omega(n^{4/5})$. This improves on a bound proved by Kulikov and Podolskii, who showed that ... more >>>

Amnon Ta-Shma

We deal with the problem of extracting as much randomness as possible

from a defective random source.

We devise a new tool, a ``merger'', which is a function that accepts

d strings, one of which is uniformly distributed,

and outputs a single string that is guaranteed ...
more >>>

C. Ramya, Anamay Tengse

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials ... more >>>

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

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

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivityof Boolean functions. Recently, Tal (ITCS, 2013) and

Gilmer, Saks, and Srinivasan (CCC, 2013) independently introduced this complexity measure, denoted by $fbs(f)$, and showed

that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by $RC(f)$, which ...
more >>>

Robert H. Sloan, Ken Takata, György Turán

Given a Boolean matrix and a threshold t, a subset of the

columns is frequent if there are at least t rows having a 1 entry in

each corresponding position. This concept is used in the algorithmic,

combinatorial approach to knowledge discovery and data mining. We

consider the complexity aspects ...
more >>>

Stasys Jukna

A boolean circuit $f(x_1,\ldots,x_n)$ \emph{represents} a graph $G$

on $n$ vertices if for every input vector $a\in\{0,1\}^n$ with

precisely two $1$'s in, say, positions $i$ and $j$, $f(a)=1$

precisely when $i$ and $j$ are adjacent in $G$; on inputs with more

or less than two ...
more >>>

Ronen Shaltiel, Emanuele Viola

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1\}^r \to \{0,1\}^m$ that fool circuits of size $m$, assuming the existence of explicit hard functions. A ``high-end PRG'' with seed length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>

Subhash Khot, Igor Shinkar

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

Pavel Hrubes

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

Suryajith Chillara, Coral Grichener, Amir Shpilka

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>

Konstantin Pervyshev

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

Dean Doron, Amnon Ta-Shma, Roei Tell

We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>>

Michael Forbes, Amir Shpilka

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but has no known such black-box algorithm. We recast this problem as ... more >>>

Karthik C. S., Pasin Manurangsi

The field of combinatorial reconfiguration studies search problems with a focus on transforming one feasible solution into another.

Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some $\varepsilon>0$ such that given as input a $k$-CSP instance (for some constant $k$) over ... more >>>

Subhash Khot

We present a candidate reduction from the $3$-Lin problem to the $2$-to-$2$ Games problem and present a combinatorial hypothesis about

Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in

a certain non-standard sense. A reduction that is sound in this non-standard sense

implies that ...
more >>>

Meghal Gupta, Rachel Zhang

In interactive coding, Alice and Bob wish to compute some function $f$ of their individual private inputs $x$ and $y$. They do this by engaging in an interactive protocol to jointly compute $f(x,y)$. The goal is to do this in an error-resilient way, such that even given some fraction of ... more >>>

Oded Goldreich, Guy Rothblum, Tal Skverer

Interactive proofs of proximity (IPPs) offer ultra-fast

approximate verification of assertions regarding their input,

where ultra-fast means that only a small portion of the input is read

and approximate verification is analogous to the notion of

approximate decision that underlies property testing.

Specifically, in an IPP, the prover can make ...
more >>>

Oded Goldreich, Salil Vadhan, Avi Wigderson

We continue the investigation of interactive proofs with bounded

communication, as initiated by Goldreich and Hastad (IPL 1998).

Let $L$ be a language that has an interactive proof in which the prover

sends few (say $b$) bits to the verifier.

We prove that the complement $\bar L$ has ...
more >>>

Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian

We introduce {\em online interactive proofs} (OIP), which are a hierarchy of communication complexity models that involve both randomness and nondeterminism (thus, they belong to the Arthur--Merlin family), but are {\em online} in the sense that the basic communication flows from Alice to Bob alone. The complexity classes defined by ... more >>>

Pavel Hrubes, Amir Yehudayoff

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

Felix Brandt, Felix Fischer, Markus Holzer

We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>>

Robert H. Sloan, Balázs Szörényi, György Turán

It is known that a k-term DNF can have at most 2^k ? 1 prime implicants and this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a non-repeating ... more >>>

Oded Goldreich, Dana Ron

We initiate a study of learning and testing dynamic environments,

focusing on environment that evolve according to a fixed local rule.

The (proper) learning task consists of obtaining the initial configuration

of the environment, whereas for non-proper learning it suffices to predict

its future values. The testing task consists of ...
more >>>

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

This paper studies the learnability of branching programs and small depth

circuits with modular and threshold gates in both the exact and PAC learning

models with and without membership queries. Some of the results extend earlier

works in [GG95,ERR95,BTW95]. The main results are as follows. For

branching programs we ...
more >>>

Ke Yang

In this paper, we study the problem of using statistical

query (SQ) to learn highly correlated boolean functions, namely, a

class of functions where any

pair agree on significantly more than a fraction 1/2 of the inputs.

We give a limit on how well ...
more >>>

Peter Auer

We investigate a variant of the Probably Almost Correct learning model

where the learner has to learn from ambiguous information. The

ambiguity is introduced by assuming that the learner does not receive

single instances with their correct labels as training data, but that

the learner receives ...
more >>>

Rocco Servedio

We show that the class of monotone $2^{O(\sqrt{\log n})}$-term DNF

formulae can be PAC learned in polynomial time under the uniform

distribution. This is an exponential improvement over previous

algorithms in this model, which could learn monotone

$o(\log^2 n)$-term DNF, and is the first efficient algorithm

for ...
more >>>

Matthias Krause, Stefan Lucks

\begin{abstract}

A set $F$ of $n$-ary Boolean functions is called a pseudorandom function generator

(PRFG) if communicating

with a randomly chosen secret function from $F$ cannot be

efficiently distinguished from communicating with a truly random function.

We ask for the minimal hardware complexity of a PRFG. This question ...
more >>>

Ilya Volkovich

We extend the line of research initiated by Fortnow and Klivans \cite{FortnowKlivans09} that studies the relationship between efficient learning algorithms and circuit lower bounds. In \cite{FortnowKlivans09}, it was shown that if a Boolean circuit class $\mathcal{C}$ has an efficient \emph{deterministic} exact learning algorithm, (i.e. an algorithm that uses membership and ... more >>>

Vikraman Arvind, Abhranil Chatterjee

We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $\Omega(n^{\omega/2+\epsilon})$ size noncommutative arithmetic circuit size lower bound (where $\omega$ is the matrix multiplication exponent) for a constant-degree $n$-variate polynomial family $(g_n)_n$, where each $g_n$ is a noncommutative polynomial, can be ``lifted'' to an exponential size ... more >>>

Yijia Chen, Joerg Flum

Ehrenfeucht-Fraisse games and their generalizations have been quite successful in finite model theory and yield various inexpressibility results. However, for key problems such as P $\ne$ NP or NP $\ne$ coNP no progress has been achieved using the games. We show that for these problems it is already hard to ... more >>>

Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang

A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.

There are two well-studied notions of linear-algebraic expansion, namely dimension expansion ... more >>>

Anup Rao, Oscar Sprumont

We study the error resilience of transitive linear codes over $F_2$. We give tight bounds on the weight distribution of every such code $C$, and we show how these bounds can be used to infer bounds on the error rates that $C$ can tolerate on the binary symmetric channel. Using ... more >>>

Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

Luca Trevisan

We prove an extremal combinatorial result regarding

the fraction of satisfiable clauses in boolean CNF

formulae enjoying a locally checkable property, thus

solving a problem that has been open for several years.

We then generalize the problem to arbitrary constraint

satisfaction ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.

1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ...
more >>>

Robert Andrews

We show that lower bounds on the border rank of matrix multiplication can be used to non-trivially derandomize polynomial identity testing for small algebraic circuits. Letting $\underline{R}(n)$ denote the border rank of $n \times n \times n$ matrix multiplication, we construct a hitting set generator with seed length $O(\sqrt{n} \cdot ... more >>>

Zeev Dvir

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

Mahdi Cheraghchi

The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower ... more >>>

Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin

In recent years the explosion in the volumes of data being stored online has resulted in distributed storage systems transitioning to erasure coding based schemes. Local Reconstruction Codes (LRCs) have emerged as the codes of choice for these applications. An $(n,r,h,a,q)$-LRC is a $q$-ary code, where encoding is as a ... more >>>

Jakob Nordström, Alexander Razborov

In the context of proving lower bounds on proof space in $k$-DNF

resolution, [Ben-Sasson and Nordström 2009] introduced the concept of

minimally unsatisfiable sets of $k$-DNF formulas and proved that a

minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most

$O((mk)^{k+1})$ variables. They also gave an example of ...
more >>>

Hermann Gruber , Markus Holzer, Simon Wolfsteiner

Finite languages lie at the heart of literally every regular expression. Therefore, we investigate the approximation complexity of minimizing regular expressions without Kleene star, or, equivalently, regular expressions describing finite languages. On the side of approximation hardness, given such an expression of size~$s$, we prove that it is impossible to ... more >>>

Subhash Khot, Dor Minzer, Muli Safra

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

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

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

being monotone ...
more >>>

Stasys Jukna, Georg Schnitger

We show that recognizing the $K_3$-freeness and $K_4$-freeness of

graphs is hard, respectively, for two-player nondeterministic

communication protocols with exponentially many partitions and for

nondeterministic (syntactic) read-$s$ times branching programs.

The key ingradient is a generalization of a coloring lemma, due to

Papadimitriou and Sipser, which says that for every ...
more >>>

Ronald Cramer, Chaoping Xing, chen yuan

Reed-Muller codes are among the most important classes of locally correctable codes. Currently local decoding of Reed-Muller codes is based on decoding on lines or quadratic curves to recover one single coordinate. To recover multiple coordinates simultaneously, the naive way is to repeat the local decoding for recovery of a ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

We study k-partition communication protocols, an extension

of the standard two-party best-partition model to k input partitions.

The main results are as follows.

1. A strong explicit hierarchy on the degree of

non-obliviousness is established by proving that,

using k+1 partitions instead of k may decrease

the communication complexity from ...
more >>>

Alexander A. Sherstov

The communication complexity of $F$ with unbounded error is the limit of the $\epsilon$-error randomized complexity of $F$ as $\epsilon\to1/2.$ Communication complexity with weakly bounded error is defined similarly but with an additive penalty term that depends on $1/2-\epsilon$. Explicit functions are known whose two-party communication complexity with unbounded error ... more >>>

Oded Goldreich

We consider three types of multiple input problems in the context of property testing.

Specifically, for a property $\Pi\subseteq\{0,1\}^n$, a proximity parameter $\epsilon$, and an integer $m$, we consider the following problems:

\begin{enumerate}

\item Direct $m$-Sum Problem for $\Pi$ and $\epsilon$:

Given a sequence of $m$ inputs, output a sequence ...
more >>>

Vasken Bohossian, Jehoshua Bruck

Linear threshold elements are the basic building blocks of artificial neural

networks. A linear threshold element computes a function that is a sign of a

weighted sum of the input variables. The weights are arbitrary integers;

actually, they can be very big integers---exponential in the number of the

input variables. ...
more >>>

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

This paper studies the computational complexity of the following type of

quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find $x \in \{-1,+1\}^n$ that maximizes $x^TA x$. This problem recently attracted attention due to its application in various clustering settings (Charikar and Wirth, 2004) as well as ...
more >>>

Brendan Juba

We consider the proof search ("automatizability") problem for integrated learning and reasoning, a problem modeling certain kinds of data mining and common sense reasoning (Juba, 2013a). In such a problem, the approximate validity (i.e., under Valiant’s PAC-Semantics (Valiant, 2000)) of an input query formula over a background probability distribution is ... more >>>

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

The paper investigates expansion properties of the Grassmann graph,

motivated by recent results of [KMS, DKKMS] concerning hardness

of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the

hypotheses put forward by these papers seems to first require a better

understanding of these expansion properties.

We consider the edge ... more >>>

Shuichi Hirahara, Osamu Watanabe

We investigate the computational power of an arbitrary distinguisher for (not necessarily computable) hitting set generators as well as the set of Kolmogorov-random strings. This work contributes to (at least) two lines of research. One line of research is the study of the limits of black-box reductions to some distributional ... more >>>

Martin Sauerhoff

Randomized branching programs are a probabilistic model of computation

defined in analogy to the well-known probabilistic Turing machines.

In this paper, we present complexity theoretic results for randomized

read-once branching programs.

Our main result shows that nondeterminism can be more powerful than

randomness for read-once branching programs. We present a ...
more >>>

Dmitry Itsykson, Alexander Knop, Andrei Romashchenko, Dmitry Sokolov

In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based ... more >>>

Shankar Kalyanaraman, Chris Umans

A number of recent results have constructed randomness extractors

and pseudorandom generators (PRGs) directly from certain

error-correcting codes. The underlying construction in these

results amounts to picking a random index into the codeword and

outputting $m$ consecutive symbols (the codeword is obtained from

the weak random source in the case ...
more >>>

Elizaveta Okol'nishnikova

The method of obtaining lower bounds on the complexity

of Boolean functions for nondeterministic branching programs

is proposed.

A nonlinear lower bound on the complexity of characteristic

functions of Reed--Muller codes for nondeterministic

branching programs is obtained.

Nader Bshouty

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ ... more >>>

Yanyi Liu, Rafael Pass

We prove the equivalence of two fundamental problems in the theory of computation:

- Existence of one-way functions: the existence of one-way functions (which in turn are equivalent to pseudorandom generators, pseudorandom functions, private-key encryption schemes, digital signatures, commitment schemes, and more).

- Mild average-case hardness of $K^{poly}$-complexity: ...
more >>>

Yanyi Liu, Rafael Pass

Whether one-way functions (OWF) exist is arguably the most important

problem in Cryptography, and beyond. While lots of candidate

constructions of one-way functions are known, and recently also

problems whose average-case hardness characterize the existence of

OWFs have been demonstrated, the question of

whether there exists some \emph{worst-case hard problem} ...
more >>>

Yanyi Liu, Rafael Pass

We present the first natural $\NP$-complete problem whose average-case hardness w.r.t. the uniform distribution over instances implies the existence of one-way functions (OWF). In fact, we prove that the existence of OWFs is \emph{equivalent} to mild average-case hardness of this $\NP$-complete problem. The problem, which originated in the 1960s, is ... more >>>

E.A. Okol'nishnikiva

Some operations over Boolean functions are considered. It is shown that

the operation of the geometrical projection and the operation of the

monotone extension can increase the complexity of Boolean functions for

formulas in each finite basis, for switching networks, for branching

programs, and read-$k$-times ...
more >>>

Edward Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajicek and Pudlak (1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (2009) ... more >>>

Constantinos Daskalakis, S. Matthew Weinberg

We efficiently solve the optimal multi-dimensional mechanism design problem for independent bidders with arbitrary demand constraints when either the number of bidders is a constant or the number of items is a constant. In the first setting, we need that each bidder's values for the items are sampled from a ... more >>>

Yijia Chen, Joerg Flum

We prove that TAUT has a $p$-optimal proof system if and only if $L_\le$, a logic introduced in [Gurevich, 88], is a P-bounded logic for P. Furthermore, using the method developed in [Chen and Flum, 10], we show that TAUT has no \emph{effective} $p$-optimal proof system under some reasonable complexity-theoretic ... more >>>

Nikhil Vyas, Ryan Williams

This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.

1. We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let ... more >>>

S. Jukna, A. Razborov, Petr Savicky, Ingo Wegener

It is known that if a Boolean function f in n variables

has a DNF and a CNF of size at most N then f also has a

(deterministic) decision tree of size $\exp(O(\log n\log^2 N)$.

We show that this simulation {\em cannot} be ...
more >>>

Emanuele Viola

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$

where $C$ is a polynomial-size constant depth circuit

and $C$ and the $q$'s are generated from $x$ arbitrarily.

more >>>

Anup Rao, Makrand Sinha

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

Yijia Chen, Martin Grohe, Magdalena Grüber

Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability.

The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems.

Hanna Mazzawi, Nader Bshouty

We prove that for every prime $p$ there exists a $(0,1)$-matrix

$M$ of size $t_p(n,m)\times n$ where

$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every

$m$ columns of $M$ are linearly independent over $\Z_p$, the field

of integers modulo $p$ (and therefore over any field of

characteristic $p$ and over the real ...
more >>>

Nikhil Mande, Swagato Sanyal

We study parity decision trees for Boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows. Let $f : \mathbb{F}_2^n \to \{-1, 1\}$ be a Boolean function with Fourier support ... more >>>

Daniel Reichman, Igor Shinkar

We consider the robustness of computational hardness of problems

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

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

graph are ...
more >>>

Scott Aaronson

Whether the class QMA (Quantum Merlin Arthur) is equal to QMA1, or QMA with one-sided error, has been an open problem for years. This note helps to explain why the problem is difficult, by using ideas from real analysis to give a "quantum oracle" relative to which QMA and QMA1 ... more >>>

Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun

The generalized pigeonhole principle says that if tN + 1 pigeons are put into N holes then there must be a hole containing at least t + 1 pigeons. Let t-PPP denote the class of all total NP-search problems reducible to finding such a t-collision of pigeons. We introduce a ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Prahladh Harsha, Srikanth Srinivasan

We make progress on some questions related to polynomial approximations of $\mathrm{AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC 1991), that any $\mathrm{AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabilistic polynomial over the reals ... more >>>

Igor E. Shparlinski

Lower bounds are obtained on the degree and the number of monomials of

Boolean functions, considered as a polynomial over $GF(2)$,

which decide if a given $r$-bit integer is square-free.

Similar lower bounds are also obtained for polynomials

over the reals which provide a threshold representation

more >>>

Edmund Ihler

We show that a fully polynomial time approximation scheme given

for an optimization problem can always be simply modified to a

polynomial time algorithm solving the problem optimally if the

computation model is the deterministic Turing Machine or the

logarithmic cost RAM and ...
more >>>

Sevag Gharibian, Dorian Rudolph

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as $P^{NP}$ and $P^{QMA}$, respectively.

The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate ...
more >>>

Troy Lee, Andrei Romashchenko

The information contained in a string $x$ about a string $y$

is defined as the difference between the Kolmogorov complexity

of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,

i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ...
more >>>

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

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

Emanuele Viola

We prove several new results regarding the relationship between probabilistic time, BPTime(t), and alternating time, \Sigma_{O(1)} Time(t). Our main results are the following:

1) We prove that BPTime(t) \subseteq \Sigma_3 Time(t polylog(t)). Previous results show that BPTime(t) \subseteq \Sigma_2 Time(t^2 log t) (Sipser and Gacs, STOC '83; Lautemann, IPL '83) ... more >>>

Mihir Bellare, Oded Goldreich

This note points out a gap between two natural formulations of

the concept of a proof of knowledge, and shows that in all

natural cases (e.g., NP-statements) this gap can be closed.

The aforementioned formulations differ by whether they refer to

(all possible) probabilistic or deterministic prover strategies.

Unlike ...
more >>>

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>

Erfan Khaniki

The refutation system ${Res}_R({PC}_d)$ is a natural extension of resolution refutation system such that it operates with disjunctions of degree $d$ polynomials over ring $R$ with boolean variables. For $d=1$, this system is called ${Res}_R({lin})$. Based on properties of $R$, ${Res}_R({lin})$ systems can be too strong to prove lower ... more >>>

Nader Bshouty, Oded Goldreich

In this note we show that all sets that are neither finite nor too dense are non-trivial to test in the sense that, for every $\epsilon>0$, distinguishing between strings in the set and strings that are $\epsilon$-far from the set requires $\Omega(1/\epsilon)$ queries.

Specifically, we show that if, for ...
more >>>

Mikolas Janota, Joao Marques-Silva

Over the years, proof systems for propositional satisfiability (SAT)

have been extensively studied. Recently, proof systems for

quantified Boolean formulas (QBFs) have also been gaining attention.

Q-resolution is a calculus enabling producing proofs from

DPLL-based QBF solvers. While DPLL has become a dominating technique

for SAT, QBF has been tackled ...
more >>>

Alexander Razborov

In this paper we study the pairs $(U,V)$ of disjoint ${\bf NP}$-sets

representable in a theory $T$ of Bounded Arithmetic in the sense that

$T$ proves $U\cap V=\emptyset$. For a large variety of theories $T$

we exhibit a natural disjoint ${\bf NP}$-pair which is complete for the

class of disjoint ...
more >>>

Gal Arnon, Guy Rothblum

A central question in the study of interactive proofs is the relationship between private-coin proofs, where the verifier is allowed to hide its randomness from the prover, and public-coin proofs, where the verifier's random coins are sent to the prover.

In this work, we study transformations ...
more >>>

Oded Goldreich, Dana Ron

We initiate a systematic study of a special type of property testers.

These testers consist of repeating a basic test

for a number of times that depends on the proximity parameters,

whereas the basic test is oblivious of the proximity parameter.

We refer to such basic ...
more >>>

Oded Goldreich, Avi Wigderson

In the theory of pseudorandomness, potential (uniform) observers

are modeled as probabilistic polynomial-time machines.

In fact many of the central results in

that theory are proven via probabilistic polynomial-time reductions.

In this paper we show that analogous deterministic reductions

are unlikely to hold. We conclude that randomness ...
more >>>

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

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

Ben Davis, Hamed Hatami, William Pires, Ran Tao, Hamza Usmani

We prove that for every Boolean function, the public-coin zero-error randomized communication complexity and the deterministic communication complexity are polynomially equivalent.

more >>>Mikolas Janota

Q-resolution and its variations provide the underlying proof

systems for the DPLL-based QBF solvers. While (long-distance) Q-resolution

models a conflict driven clause learning (CDCL) QBF solver, it is not

known whether the inverse is also true. This paper provides a negative

answer to this question. This contrasts with SAT solving, ...
more >>>

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming

Aaronson and Ambainis (STOC 2015, SICOMP 2018) claimed that the acceptance probability of every quantum algorithm that makes $q$ queries to an $N$-bit string can be estimated to within $\epsilon$ by a randomized classical algorithm of query complexity $O_q((N/\epsilon^2)^{1-1/2q})$. We describe a flaw in their argument but prove that the ... more >>>

Vadim Lyubashevsky

In the Subset Sum problem, we are given n integers a_1,...,a_n

and a target number t, and are asked to find the subset of the

a_i's such that the sum is t. A version of the subset sum

problem is the Random Modular Subset Sum problem. In this version,

the ...
more >>>

Petr Savicky

There are Boolean functions such that almost all orderings of

its variables yield an OBDD of polynomial size, but there are

also some exceptional orderings, for which the size is exponential.

We prove that for parity OBDDs the size for a random ordering

...
more >>>

Michael Saks, Rahul Santhanam

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.

As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language $L$ that has a randomized ... more >>>

Marek Karpinski, Rutger Verbeek

In contrast to deterministic or nondeterministic computation, it is

a fundamental open problem in randomized computation how to separate

different randomized time classes (at this point we do not even know

how to separate linear randomized time from ${\mathcal O}(n^{\log n})$

randomized time) or how to ...
more >>>

Oded Goldreich, Emanuele Viola, Avi Wigderson

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

For $k ... more >>>

Noam Nisan, Avi Wigderson

This paper concerns the open problem of Lovasz and

Saks regarding the relationship between the communication complexity

of a boolean function and the rank of the associated matrix.

We first give an example exhibiting the largest gap known. We then

prove two related theorems.

Pavel Hrubes, Pushkar Joglekar

We consider read-$k$ determinantal representations of polynomials and prove some non-expressibility results. A square matrix $M$ whose entries are variables or field elements will be called \emph{read-$k$}, if every variable occurs at most $k$ times in $M$. It will be called a \emph{determinantal representation} of a polynomial $f$ if $f=\det(M)$. ... more >>>

Pavel Pudlak

We consider some problems about pairs of disjoint $NP$ sets.

The theory of these sets with a natural concept of reducibility

is, on the one hand, closely related to the theory of proof

systems for propositional calculus, and, on the other, it

resembles the theory of NP completeness. Furthermore, such

more >>>

Mark Braverman, Subhash Khot, Dor Minzer

We propose a variant of the $2$-to-$1$ Games Conjecture that we call the Rich $2$-to-$1$ Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the $2$-to-$1$ Games Conjecture, we hope to understand ... more >>>

Noga Alon, Gil Cohen

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>

Oded Goldreich, Dana Ron

The standard definition of property testing endows the tester with the ability to make arbitrary queries to ``elements''

of the tested object.

In contrast, sample-based testers only obtain independently distributed elements (a.k.a. labeled samples) of the tested object.

While sample-based testers were defined by

Goldreich, Goldwasser, and Ron ({\em JACM}\/ ...
more >>>

Paul Beame, Faith Fich

We obtain improved lower bounds for a class of static and dynamic

data structure problems that includes several problems of searching

sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent

striking improvements in searching algorithms given by Fredman and

Willard's ...
more >>>

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>>

Rahul Santhanam

We give the first extension of the result due to Paul, Pippenger,

Szemeredi and Trotter that deterministic linear time is distinct from

nondeterministic linear time. We show that DTIME(n \sqrt(log^{*}(n)))

\neq NTIME(n \sqrt(log^{*}(n))). We show that atleast one of the

following statements holds: (1) P \neq L ...
more >>>

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... more >>>

Jayram S. Thathachar

We obtain an exponential separation between consecutive

levels in the hierarchy of classes of functions computable by

polynomial-size syntactic read-$k$-times branching programs, for

{\em all\/} $k>0$, as conjectured by various

authors~\cite{weg87,ss93,pon95b}. For every $k$, we exhibit two

explicit functions that can be computed by linear-sized

read-$(\kpluso)$-times branching programs but ...
more >>>

Joanna Boyland, Michael Hwang, Tarun Prasad, Noah Singer, Santhoshini Velusamy

A Boolean maximum constraint satisfaction problem, Max-CSP\((f)\), is specified by a predicate \(f:\{-1,1\}^k\to\{0,1\}\). An \(n\)-variable instance of Max-CSP\((f)\) consists of a list of constraints, each of which applies \(f\) to \(k\) distinct literals drawn from the \(n\) variables. For \(k=2\), Chou, Golovnev, and Velusamy [CGV20, FOCS 2020] obtained explicit ratios ... more >>>

Alexander Kozachinsky

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

Johan Håstad

We study Frege proofs for the one-to-one graph Pigeon Hole Principle

defined on the $n\times n$ grid where $n$ is odd.

We are interested in the case where each formula

in the proof is a depth $d$ formula in the basis given by

$\land$, $\lor$, and $\neg$. We prove that ...
more >>>

Johan Håstad

We prove that a small-depth Frege refutation of the Tseitin contradiction

on the grid requires subexponential size.

We conclude that polynomial size Frege refutations

of the Tseitin contradiction must use formulas of almost

logarithmic depth.

Pranav Bisht, Ilya Volkovich

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>

Piotr Berman, Marek Karpinski

We prove a number of improved inaproximability results,

including the best up to date explicit approximation

thresholds for MIS problem of bounded degree, bounded

occurrences MAX-2SAT, and bounded degree Node Cover. We

prove also for the first time inapproximability of the

problem of Sorting by ...
more >>>

Piotr Berman, Marek Karpinski

Improved inaproximability results are given, including the

best up to date explicit approximation thresholds for bounded

occurence satisfiability problems, like MAX-2SAT and E2-LIN-2,

and problems in bounded degree graphs, like MIS, Node Cover

and MAX CUT. We prove also for the first time inapproximability

more >>>

Alexander Razborov

We show that the total space in resolution, as well as in any other reasonable

proof system, is equal (up to a polynomial and $(\log n)^{O(1)}$ factors) to

the minimum refutation depth. In particular, all these variants of total space

are equivalent in this sense. The same conclusion holds for ...
more >>>

Anna Palbom

In an attempt to generalize Christofides algorithm for metric TSP to the asymmetric TSP with triangle inequality we have studied various properties of directed spanning cacti. In this paper we first observe that finding the TSP in a directed, weighted complete graph with triangle inequality is polynomial time equivalent to ... more >>>

Iddo Tzameret

We formalize a combinatorial principle, called the 3XOR principle, due to Feige, Kim and Ofek (2006), as a family of unsatisfiable propositional formulas for which refutations of small size in any propositional proof system that possesses the feasible interpolation property imply an efficient *deterministic* refutation algorithm for random 3SAT with ... more >>>

Avrim Blum, Ke Yang

We introduce a ``Statistical Query Sampling'' model, in which

the goal of an algorithm is to produce an element in a hidden set

$S\subseteq\bit^n$ with reasonable probability. The algorithm

gains information about $S$ through oracle calls (statistical

queries), where the algorithm submits a query function $g(\cdot)$

and receives ...
more >>>

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

Affine-invariant properties are an abstract class of properties that generalize some

central algebraic ones, such as linearity and low-degree-ness, that have been

studied extensively in the context of property testing. Affine invariant properties

consider functions mapping a big field $\mathbb{F}_{q^n}$ to the subfield $\mathbb{F}_q$ and include all

properties that form ...
more >>>

Noga Alon, Amir Shpilka, Chris Umans

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

Young Kun Ko

Unique Games Conjecture (UGC), proposed by [Khot02], lies in the center of many inapproximability results. At the heart of UGC lies approximability of MAX-CUT, which is a special instance of Unique Game.[KhotKMO04, MosselOO05] showed that assuming Unique Games Conjecture, it is NP-hard to distinguish between MAX-CUT instance that has a ... more >>>

Jin-Yi Cai, Pinyan Lu

The most intriguing aspect of the new theory of matchgate computations and holographic algorithms by Valiant~\cite{Valiant:Quantum} \cite{Valiant:Holographic} is that its reach and ultimate capability are wide open. The methodology produces unexpected polynomial time algorithms solving problems which seem to require exponential time. To sustain our belief in P $\not =$ ... more >>>

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

We attempt to reconcile the two distinct views of approximation

classes: syntactic and computational.

Syntactic classes such as MAX SNP allow for clean complexity-theoretic

results and natural complete problems, while computational classes such

as APX allow us to work with problems whose approximability is

well-understood. Our results give a computational ...
more >>>

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

In both query and communication complexity, we give separations between the class NISZK, containing those problems with non-interactive statistical zero knowledge proof systems, and the class UPP, containing those problems with randomized algorithms with unbounded error. These results significantly improve on earlier query separations of Vereschagin [Ver95] and Aaronson [Aar12] ... more >>>

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>

Oded Goldreich

This text provides a basic presentation of the the approximation method of Razborov (Matematicheskie Zametki, 1987) and its application by Smolensky (19th STOC, 1987) for proving lower bounds on the size of ${\cal AC}^0[p]$-circuits that compute sums mod~$q$ (for primes $q\neq p$).

The textbook presentations of the latter result ...
more >>>

Arnab Bhattacharyya

An affine-invariant property over a finite field is a property of functions over F_p^n that is closed under all affine transformations of the domain. This class of properties includes such well-known beasts as low-degree polynomials, polynomials that nontrivially factor, and functions of low spectral norm. The last few years has ... more >>>

Oded Goldreich

We consider the problem of testing asymmetry in the bounded-degree graph model, where a graph is called asymmetric if the identity permutation is its only automorphism. Seeking to determine the query complexity of this testing problem, we provide partial results. Considering the special case of $n$-vertex graphs with connected components ... more >>>

Abhishek Bhrushundi

A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.

We study bent functions in the framework of property testing. In particular, we ...
more >>>

Oded Goldreich

We take another step in the study of the testability

of small-width OBDDs, initiated by Ron and Tsur (Random'09).

That is, we consider algorithms that,

given oracle access to a function $f:\{0,1\}^n\to\{0,1\}$,

need to determine whether $f$ can be implemented

by some restricted class of OBDDs or is far from

more >>>

Oded Goldreich, Dana Ron

We consider testing graph expansion in the bounded-degree graph model.

Specifically, we refer to algorithms for testing whether the graph

has a second eigenvalue bounded above by a given threshold

or is far from any graph with such (or related) property.

We present a natural algorithm aimed ... more >>>

Oded Goldreich, Laliv Tauber

Following Ergun et al. (JCSS 2000), we consider testing group properties and focus on the problem of testing whether a binary operation is a group operation.

That is, given a finite set $S$ and oracle access to a function $f:S\times S \to S$, we wish to distinguish the case that ...
more >>>

Oded Goldreich

We show that testing Hamiltonicity in the bounded-degree graph model requires a linear number of queries. This refers to both the path and the cycle versions of the problem, and similar results hold also for the directed analogues.

In addition, we present an alternative proof for the known fact that ...
more >>>

Yuan Li, Alexander Razborov, Benjamin Rossman

Let $P$ be a fixed graph (hereafter called a ``pattern''), and let

$Subgraph(P)$ denote the problem of deciding whether a given graph $G$

contains a subgraph isomorphic to $P$. We are interested in

$AC^0$-complexity of this problem, determined by the smallest possible exponent

$C(P)$ for which $Subgraph(P)$ possesses bounded-depth circuits ...
more >>>

Aditya Potukuchi

Andreev's Problem asks the following: Given an integer $d$ and a subset of $S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y = p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a)) \in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem.

... more >>>Aniruddha Biswas, Palash Sarkar

We show that the ''majority is least stable'' conjecture is true for $n=1$ and $3$ and false for all odd $n\geq 5$.

more >>>Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying

\[

\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ...
more >>>

Ke Yang

We study the problem of non-interactive correlation distillation

(NICD). Suppose Alice and Bob each has a string, denoted by

$A=a_0a_1\cdots a_{n-1}$ and $B=b_0b_1\cdots b_{n-1}$,

respectively. Furthermore, for every $k=0,1,...,n-1$, $(a_k,b_k)$ is

independently drawn from a distribution $\noise$, known as the ``noise

mode''. Alice and Bob wish to ``distill'' the correlation

more >>>

Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang

Informally, an <i>obfuscator</i> <b>O</b> is an (efficient, probabilistic)

"compiler" that takes as input a program (or circuit) <b>P</b> and

produces a new program <b>O(P)</b> that has the same functionality as <b>P</b>

yet is "unintelligible" in some sense. Obfuscators, if they exist,

would have a wide variety of cryptographic ...
more >>>

Yael Tauman Kalai

In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security ... more >>>

Cody Murray, Ryan Williams

The Minimum Circuit Size Problem (MCSP) is: given the truth table of a Boolean function $f$ and a size parameter $k$, is the circuit complexity of $f$ at most $k$? This is the definitive problem of circuit synthesis, and it has been studied since the 1950s. Unlike many problems of ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this paper we present a new approximation algorithm for the MAX ACYCLIC SUBGRAPH problem. Given an instance where the maximum acyclic subgraph contains (1/2 + delta) fraction of all edges, our algorithm finds an acyclic subgraph with (1/2 + Omega(delta/ log n)) fraction of all edges.

more >>>Valentin E. Brimkov, Stefan S. Dantchev

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem

(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors

$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ...
more >>>

Samuel Epstein

We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

more >>>Valentin Brimkov, Andrew Leach, Jimmy Wu, Michael Mastroianni

Given a finite set of straight line segments $S$ in $R^{2}$ and some $k\in N$, is there a subset $V$ of points on segments in $S$ with $\vert V \vert \leq k$ such that each segment of $S$ contains at least one point in $V$? This is a special case ... more >>>

Edoardo Amaldi, Viggo Kann

We investigate the computational complexity of two classes of

combinatorial optimization problems related to linear systems

and study the relationship between their approximability properties.

In the first class (MIN ULR) one wishes, given a possibly infeasible

system of linear relations, to find ...
more >>>

Luca Trevisan

We consider the Traveling Salesperson Problem (TSP) restricted

to Euclidean spaces of dimension at most k(n), where n is the number of

cities. We are interested in the relation between the asymptotic growth of

k(n) and the approximability of the problem. We show that the problem is ...
more >>>

Li-Sha Huang, Shang-Hua Teng

We show that the problem of finding an \epsilon-approximate Nash equilibrium af an n*n two-person game can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange ... more >>>

Igor Sergeev

We investigate the number of pairwise comparisons sufficient to sort $n$ elements chosen from a linearly ordered set. This number is shown to be $\log_2(n!) + o(n)$ thus improving over the previously known upper bounds of the form $\log_2(n!) + \Theta(n)$. The new bound is achieved by the proposed group ... more >>>

Soren Riis

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

Nicola Galesi, Massimo Lauria

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>Albert Atserias, Maria Luisa Bonet

Having good algorithms to verify tautologies as efficiently as possible

is of prime interest in different fields of computer science.

In this paper we present an algorithm for finding Resolution refutations

based on finding tree-like Res(k) refutations. The algorithm is based on

the one of Beame and Pitassi \cite{BP96} ...
more >>>

Todd Ebert, Wolfgang Merkle, Heribert Vollmer

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

Oded Goldreich

Motivated by a recent study of Zimand (22nd CCC, 2007),

we consider the average-case complexity of property testing

(focusing, for clarity, on testing properties of Boolean strings).

We make two observations:

1) In the context of average-case analysis with respect to

the uniform distribution (on all strings of ...
more >>>

Esther Ezra, Shachar Lovett

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

Charanjit Jutla, Vijay Kumar, Atri Rudra

We study the circuit complexity of linear transformations between Galois fields GF(2^{mn}) and their isomorphic composite fields GF((2^{m})^n). For such a transformation, we show a lower bound of \Omega(mn) on the number of gates required in any circuit consisting of constant-fan-in XOR gates, except for a class of transformations between ... more >>>

Oded Goldreich, Avi Wigderson

We consider the size of circuits which perfectly hash

an arbitrary subset $S\!\subset\!\bitset^n$ of cardinality $2^k$

into $\bitset^m$.

We observe that, in general, the size of such circuits is

exponential in $2k-m$,

and provide a matching upper bound.

Prasad Chaugule, Nutan Limaye

In this paper we prove the following two results.

* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. ...
more >>>

Oded Goldreich

A couple of years ago, Blais, Brody, and Matulef put forward a methodology for proving lower bounds on the query complexity

of property testing via communication complexity. They provided a restricted formulation of their methodology

(via ``simple combining operators'')

and also hinted towards a more general formulation, which we spell ...
more >>>

Tim Roughgarden, Omri Weinstein

We study the two-party communication complexity of finding an approximate Brouwer fixed point of a composition

of two Lipschitz functions $g\circ f : [0,1]^n \to [0,1]^n$, where Alice holds $f$ and Bob holds $g$. We prove an

exponential (in $n$) lower bound on the deterministic ...
more >>>

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Xi Chen, Xiaotie Deng

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits

for division, matrix powering, and related problems, where the improvement is in terms of ...
more >>>

Zhenjian Lu, Igor Oliveira, Hanlin Ren, Rahul Santhanam

We introduce and study the following natural total search problem, which we call the {\it heavy element avoidance} (Heavy Avoid) problem: for a distribution on $N$ bits specified by a Boolean circuit sampling it, and for some parameter $\delta(N) \ge 1/\poly(N)$ fixed in advance, output an $N$-bit string that has ... more >>>

Parikshit Gopalan, Shachar Lovett, Amir Shpilka

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

Oded Goldreich, Salil Vadhan

We consider two basic computational problems

regarding discrete probability distributions:

(1) approximating the statistical difference (aka variation distance)

between two given distributions,

and (2) approximating the entropy of a given distribution.

Both problems are considered in two different settings.

In the first setting the approximation algorithm

more >>>

Pavel Hrubes

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:

(i) every $f$ can be defined by a formula of size $O(n)$,

(ii) if $A$ is required to have at most $k\geq 1$ ...
more >>>

Michael Schmitt

In a great variety of neuron models neural inputs are

combined using the summing operation. We introduce the concept of

multiplicative neural networks which contain units that multiply

their inputs instead of summing them and, thus, allow inputs to

interact nonlinearly. The class of multiplicative networks

comprises such widely known ...
more >>>

Xiaotie Deng, Yuhao Li, David Mguni, Jun Wang, Yaodong Yang

Similar to the role of Markov decision processes in reinforcement learning, Markov Games (also called Stochastic Games)lay down the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we introduce the solution concept, approximate Markov Perfect Equilibrium (MPE), to finite-state Stochastic Games repeated ... more >>>

Lakhdar Saïs, Mohand-Saïd Hacid, francois hantry

We show that (1) the Minimal False QCNF search problem (MF-search) and

the Minimal Unsatisfiable LTL formula search problem (MU-search) are FPSPACE complete because of the very expressive power of QBF/LTL, (2) we extend the PSPACE-hardness of the MF decision problem to the MU decision problem. As a consequence, we ...
more >>>

Eric Miles, Emanuele Viola

We study the complexity of black-box constructions of

pseudorandom functions (PRF) from one-way functions (OWF)

that are secure against non-uniform adversaries. We show

that if OWF do not exist, then given as an oracle any

(inefficient) hard-to-invert function, one can compute a

PRF in polynomial time with only $k(n)$ oracle ...
more >>>

Sanjeeb Dash

We prove a monotone interpolation property for split cuts which, together with results from Pudlak (1997), implies that cutting-plane proofs which use split cuts have exponential length in the worst case.

As split cuts are equivalent to mixed-integer rounding cuts and Gomory mixed-integer cuts, cutting-plane proofs using the above cuts ...
more >>>

Oded Goldreich

We consider the complexity of enumerating ordered sets, defined as solving the following type of a computational problem: For a predetermined ordered set, given $i\in\N$, one is required to answer with the $i^{th}$ member of the set (according to the predetermined order).

Our focus is on countable sets such as ... more >>>

Oded Goldreich

Loosely speaking, the effective support size of a distribution is the size of the support of a distribution that is close to it (in totally variation distance).

We study the complexity of estimating the effective support size of an unknown distribution when given samples of the distributions as well ...
more >>>

Iftach Haitner, Nikolaos Makriyannis, Eran Omri

A two-party coin-flipping protocol is $\varepsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] ... more >>>

Peter Jonsson, Paolo Liberatore

We study the computational complexity of an optimization

version of the constraint satisfaction problem: given a set $F$ of

constraint functions, an instance consists of a set of variables $V$

related by constraints chosen from $F$ and a natural number $k$. The

problem is to decide whether there exists a ...
more >>>

Peter Auer, Philip M. Long, Gerhard J. Woeginger

The majority of results in computational learning theory

are concerned with concept learning, i.e. with the special

case of function learning for classes of functions

with range {0,1}. Much less is known about the theory of

learning functions with a larger range such

as N or R. In ...
more >>>

Fabian Wagner

The group isomorphism problem consists in deciding whether two groups $G$ and $H$

given by their multiplication tables are isomorphic.

An algorithm for group isomorphism attributed to Tarjan runs in time $n^{\log n + O(1)}$, c.f. [Mil78].

Miller and Monk showed in [Mil79] that group isomorphism can be many-one ... more >>>

Robert Albin Legenstein

In this article we consider a basic problem in the layout of

VLSI-circuits, the channel-routing problem in the knock-knee mode.

We show that knock-knee channel routing with 3-terminal nets is

NP-complete and thereby settling a problem that was open for more

than a decade. In 1987, Sarrafzadeh showed that knock-knee ...
more >>>

Michael Schmitt

Spiking neurons are models for the computational units in

biological neural systems where information is considered to be encoded

mainly in the temporal pattern of their activity. In a network of

spiking neurons a new set of parameters becomes relevant which has no

counterpart in traditional ...
more >>>

Ran Raz

We prove a lower bound of $\Omega(m^2 \log m)$ for the size of

any arithmetic circuit for the product of two matrices,

over the real or complex numbers, as long as the circuit doesn't

use products with field elements of absolute value larger than 1

(where $m \times m$ is ...
more >>>

Vikraman Arvind, Pushkar Joglekar, Gaurav Rattan

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

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

Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

We study two quite different approaches to understanding the complexity

of fundamental problems in numerical analysis. We show that both hinge

on the question of understanding the complexity of the following problem,

which we call PosSLP:

Given a division-free straight-line program

producing an integer N, decide whether N>0.

more >>>

Igor Sergeev

It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, ... more >>>

Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

In sequencing by hybridization (SBH),

one has to reconstruct a sequence

from its $l$-long substrings.

SBH was proposed as

an alternative to

gel-based

DNA sequencing approaches, but in its original form the method

is

not competitive.

Positional SBH (PSBH) is a recently proposed

enhancement ...
more >>>

Vitaly Feldman, Will Perkins, Santosh Vempala

We consider the problem of identifying a planted assignment given a random $k$-SAT formula consistent with the assignment. This problem exhibits a large algorithmic gap: while the planted solution can always be identified given a formula with $O(n\log n)$ clauses, there are distributions over clauses for which the best known ... more >>>

Meena Mahajan, Jayalal Sarma

Given a matrix $M$ over a ring \Ringk, a target rank $r$ and a bound

$k$, we want to decide whether the rank of $M$ can be brought down to

below $r$ by changing at most $k$ entries of $M$. This is a decision

version of the well-studied notion of ...
more >>>

Takashi Ishizuka

One of the most famous TFNP subclasses is PPP, which is the set of all search problems whose totality is guaranteed by the pigeonhole principle. The author's recent preprint [ECCC TR24-002 2024] has introduced a TFNP problem related to the pigeonhole principle over a quotient set, called Quotient Pigeon, and ... more >>>

Lance Fortnow, Russell Impagliazzo, Chris Umans

We study the complexity of solving succinct zero-sum games,

i.e., the

games whose payoff matrix $M$ is given implicitly by a Boolean circuit

$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness

of computing the \emph{exact} value of a succinct zero-sum game by

several results on \emph{approximating} the value. (1) ...
more >>>

Xiaohui Bei, Ning Chen, Shengyu Zhang

Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>>

Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram

In a recent work of Bei, Chen and Zhang (STOC 2013), a trial and error model of computing was introduced, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle which, for a candidate assignment, reveals some information about a violated constraint if ... more >>>

Iftach Haitner, Noam Mazor, Jad Silbak, Eliad Tsfadia

In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, ... more >>>

Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>

Danny Harnik, Moni Naor

We initiate the study of the compressibility of NP problems. We

consider NP problems that have long instances but relatively

short witnesses. The question is, can one efficiently compress an

instance and store a shorter representation that maintains the

information of whether the original input is in the language or

more >>>

Farid Ablayev, Alexander Vasiliev

We develop quantum fingerprinting technique for constructing quantum

branching programs (QBPs), which are considered as circuits with an

ability to use classical bits as control variables.

We demonstrate our approach constructing optimal quantum ordered

binary decision diagram (QOBDD) for $MOD_m$ and $DMULT_n$ Boolean

functions. The construction of our technique also ...
more >>>

Mohamed El Halaby

Given a Boolean formula in Conjunctive Normal Form (CNF) $\phi=S \cup H$, the MaxSAT (Maximum Satisfiability) problem asks for an assignment that satisfies the maximum number of clauses in $\phi$. Due to the good performance of current MaxSAT solvers, many real-life optimization problems such as scheduling can be solved efficiently ... more >>>

Bernd Borchert, Desh Ranjan, Frank Stephan

The paper analyzes in terms of polynomial time many-one reductions

the computational complexity of several natural equivalence

relations on Boolean functions which derive from replacing

variables by expressions. Most of these computational problems

turn out to be between co-NP and Sigma^p_2.

PERRET ludovic

We study in this paper the computational complexity of some

equivalence relations on polynomial systems of equations over finite

fields. These problems are analyzed with respect to polynomial-time

many-one reductions (resp. Turing reductions, Levin reductions). In

particular, we show that some of these problems are between ...
more >>>

Marek Karpinski, Igor E. Shparlinski

We show that deciding square-freeness of a sparse univariate

polynomial over the integer and over the algebraic closure of a

finite field is NP-hard. We also discuss some related open

problems about sparse polynomials.

Matthias Krause, Pavel Pudlak

We investigate the computational power of depth two circuits

consisting of $MOD^r$--gates at the bottom and a threshold gate at

the top (for short, threshold--$MOD^r$ circuits) and circuits with

two levels of $MOD$ gates ($MOD^{p}$-$MOD^q$ circuits.) In particular, we

will show the following results

(i) For all prime numbers ... more >>>

Marek Karpinski

We survey some upper and lower bounds established recently on

the sizes of randomized branching programs computing explicit

boolean functions. In particular, we display boolean

functions on which randomized read-once ordered branching

programs are exponentially more powerful than deterministic

or nondeterministic read-$k$-times branching programs for ...
more >>>

Henry Markram

Understanding the structure of real-time neural computation in

highly recurrent neural microcircuits that consist of complex

heterogeneous components has remained a serious challenge for

computational modeling. We propose here a new conceptual framework

that strongly differs from all previous approaches based on

computational models inspired ...
more >>>

In this paper the computational power of a new type of gate is studied:

winner-take-all gates. This work is motivated by the fact that the cost

of implementing a winner-take-all gate in analog VLSI is about the same

as that of implementing a threshold gate.

We show that ... more >>>

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

Irit Dinur, Igor Shinkar

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

Douglas R. Stinson

In this primarily expository

paper, we discuss the connections between two popular and useful

tools in theoretical computer science, namely,

universal hashing and pairwise

independent random variables; and classical combinatorial stuctures

such as error-correcting codes, balanced incomplete block designs,

difference matrices

...
more >>>

Noam Livne

In this paper we study the possibility of proving the existence of

one-way functions based on average case hardness. It is well-known

that if there exists a polynomial-time sampler that outputs

instance-solution pairs such that the distribution on the instances

is hard on average, then one-way functions exist. We study ...
more >>>

Moni Naor, Omer Reingold

Luby and Rackoff showed a method for constructing a pseudo-random

permutation from a pseudo-random function. The method is based on

composing four (or three for weakened security) so called Feistel

permutations each of which requires the evaluation of a pseudo-random

function. We reduce somewhat the complexity ...
more >>>

Oded Goldreich

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings, and each leaf is assigned an $\ell$-bit string.

The desired output is the value of the root, ...
more >>>

Johan Håstad

We prove that the correlation of a depth-$d$

unbounded fanin circuit of size $S$ with parity

of $n$ variables is at most $2^{-\Omega(n/(\log S)^{d-1})}$.

Nir Bitansky, Omer Paneth, Alon Rosen

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

Boris Hemkemeier, Frank Vallentin

A lattice in euclidean space which is an orthogonal sum of

nontrivial sublattices is called decomposable. We present an algorithm

to construct a lattice's decomposition into indecomposable sublattices.

Similar methods are used to prove a covering theorem for generating

systems of lattices and to speed up variations of the LLL ...
more >>>

Olaf Beyersdorff

In this paper we ask the question whether the extended Frege proof

system EF satisfies a weak version of the deduction theorem. We

prove that if this is the case, then complete disjoint NP-pairs

exist. On the other hand, if EF is an optimal proof system, ...
more >>>

Kiran Kedlaya, Swastik Kopparty

For an odd prime $p$, we say $f(X) \in {\mathbb F}_p[X]$ computes square roots in $\mathbb F_p$ if, for all nonzero perfect squares $a \in \mathbb F_p$, we have $f(a)^2 = a$.

When $p \equiv 3$ mod $4$, it is well known that $f(X) = X^{(p+1)/4}$ computes square ...
more >>>

Gil Cohen, Amir Shpilka

In this paper we study the degree of non-constant symmetric functions $f:\{0,1\}^n \to \{0,1,\ldots,c\}$, where $c\in

\mathbb{N}$, when represented as polynomials over the real numbers. We show that as long as $c < n$ it holds that deg$(f)=\Omega(n)$. As we can have deg$(f)=1$ when $c=n$, our

result shows a surprising ...
more >>>

Gil Cohen, Amir Shpilka, Avishay Tal

We study the following problem raised by von zur Gathen and Roche:

What is the minimal degree of a nonconstant polynomial $f:\{0,\ldots,n\}\to\{0,\ldots,m\}$?

Clearly, when $m=n$ the function $f(x)=x$ has degree $1$. We prove that when $m=n-1$ (i.e. the point $\{n\}$ is not in the range), it must be the case ... more >>>

Andrej Bogdanov, Chin Ho Lee

We show that secure homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure encryption scheme cannot be implemented by constant depth, polynomial size circuits, i.e. in the class AC0. In contrast, we observe that certain previously studied encryption schemes (with quasipolynomial security) can ... more >>>

Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe

In this paper we separate many-one reducibility from truth-table

reducibility for distributional problems in DistNP under the

hypothesis that P neq NP. As a first example we consider the

3-Satisfiability problem (3SAT) with two different distributions

on 3CNF formulas. We show that 3SAT using a version of the

standard distribution ...
more >>>

Tzvika Hartman, Ran Raz

Weak designs were defined by Raz, Reingold and Vadhan (1999) and are

used in constructions of extractors. Roughly speaking, a weak design

is a collection of subsets satisfying some near-disjointness

properties. Constructions of weak designs with certain parameters are

given in [RRV99]. These constructions are explicit in the sense that

more >>>

Oded Goldreich

We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).

Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in ...
more >>>

Pekka Orponen

We introduce a model for analog computation with discrete

time in the presence of analog noise

that is flexible enough to cover the most important concrete

cases, such as noisy analog neural nets and networks of spiking neurons.

This model subsumes the classical ...
more >>>

Oded Goldreich

This note refers to the effect of the proximity parameter on the operation of (standard) property testers. Its bottom-line is that, except in pathological cases, the effect of the proximity parameter is restricted to determining the query complexity of the tester. The point is that, in non-pathological cases, the mapping ... more >>>

Or Meir

We define a non-uniform model of PCPs of Proximity, and observe that in this model the non-uniform verifiers can always be made very efficient. Specifically, we show that any non-uniform verifier can be modified to run in time that is roughly polynomial in its randomness and query complexity.

more >>>Marco Cesati, Luca Trevisan

A polynomial time approximation scheme (PTAS) for an optimization

problem $A$ is an algorithm that on input an instance of $A$ and

$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time

that is polynomial for each fixed $\epsilon$. Typical running times

are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ...
more >>>

Alex Samorodnitsky

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

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

Alina Beygelzimer, Mitsunori Ogihara

We investigate the complexity of enumerative approximation of

two elementary problems in linear algebra, computing the rank

and the determinant of a matrix. In particular, we show that

if there exists an enumerator that, given a matrix, outputs a

list of constantly many numbers, one of which is guaranteed to

more >>>

Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

Optimal dispersers have better dependence on the error than

optimal extractors. In this paper we give explicit disperser

constructions that beat the best possible extractors in some

parameters. Our constructions are not strong, but we show that

having such explicit strong constructions implies a solution

to the Ramsey graph construction ...
more >>>

Prerona Chatterjee, Mrinal Kumar, C Ramya, Ramprasad Saptharishi, Anamay Tengse

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:

* For every family {f_n} of polynomials in VP, where f_n is an n ...
more >>>

Detlef Sieling

The size of Ordered Binary Decision Diagrams (OBDDs) is

determined by the chosen variable ordering. A poor choice may cause an

OBDD to be too large to fit into the available memory. The decision

variant of the variable ordering problem is known to be

NP-complete. We strengthen this result by ...
more >>>

Shai Ben-David, Anna Gringauze.

We investigate sufficient conditions for the existence of

optimal propositional proof systems (PPS).

We concentrate on conditions of the form CoNF = NF.

We introduce a purely combinatorial property of complexity classes

- the notions of {\em slim} vs. {\em fat} classes.

These notions partition the ...
more >>>

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of ... more >>>

Jan Krajicek

The working conjecture from K'04 that there is a proof complexity generator hard for all

proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions

as follows:

\begin{itemize}

\item There exist a p-time function $g$ extending each input by one bit such that its ...
more >>>

Eran Ofek

Let $d \geq d_0$ be a sufficiently large constant. A $(n,d,c

\sqrt{d})$ graph $G$ is a $d$ regular graph over $n$ vertices whose

second largest eigenvalue (in absolute value) is at most $c

\sqrt{d}$. For any $0 < p < 1, ~G_p$ is the graph induced by

retaining each edge ...
more >>>

Pushkar Joglekar, Aravind N.R.

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

Shafi Goldwasser, Dhiraj Holden

We set out to study the impact of having access to correlated instances on the fine grained complexity of polynomial time problems, which have notoriously resisted improvement.

In particular, we show how to use a logarithmic number of auxiliary correlated instances to obtain $o(n^2)$ time algorithms for the longest common ...
more >>>

Jiawei Gao

Least Weight Subsequence (LWS) is a type of highly sequential optimization problems with form $F(j) = \min_{i < j} [F(i) + c_{i,j}]$. They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than $n^{2-o(1)}$ time. Surprisingly, each such ... more >>>

Nader Bshouty, Christino Tamon

Srinivasan Arunachalam, Oded Regev, Penghui Yao

We show that for sufficiently large $n\geq 1$ and $d=C n^{3/4}$ for some universal constant $C>0$, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area $\Theta(n^{1/8})$ with high probability.

more >>>Venkatesan Guruswami, Sanjeev Khanna

We give a new proof showing that it is NP-hard to color a 3-colorable

graph using just four colors. This result is already known (Khanna,

Linial, Safra 1992), but our proof is novel as it does not rely on

the PCP theorem, while the earlier one does. This ...
more >>>

Lijie Chen

In this paper we study the (Bichromatic) Maximum Inner Product Problem (Max-IP), in which we are given sets $A$ and $B$ of vectors, and the goal is to find $a \in A$ and $b \in B$ maximizing inner product $a \cdot b$. Max-IP is very basic and serves ...
more >>>

Elad Hazan, Shmuel Safra, Oded Schwartz

We study bounded degree graph problems, mainly the problem of

k-Dimensional Matching \emph{(k-DM)}, namely, the problem of

finding a maximal matching in a k-partite k-uniform balanced

hyper-graph. We prove that k-DM cannot be efficiently approximated

to within a factor of $ O(\frac{k}{ \ln k}) $ unless $P = NP$.

This ...
more >>>

Irit Dinur, S. Safra

The label-cover problem was introduced in \cite{ABSS} and shown

there to be quasi-NP-hard to approximate to within a factor of

$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This

combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}

for showing hardness-of-approximation of numerous problems. We

present a direct combinatorial reduction from low

error-probability PCP ...
more >>>

Uriel Feige, Daniel Reichman

Max-Satisfy is the problem of finding an assignment that satisfies

the maximum number of equations in a system of linear equations

over $\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no

polynomial time algorithm for the problem achieving an

approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number

of ...
more >>>

Scott Aaronson, Yosi Atia, Leonard Susskind

When is decoherence "effectively irreversible"? Here we examine this central question of quantum foundations using the tools of quantum computational complexity. We prove that, if one had a quantum circuit to determine if a system was in an equal superposition of two orthogonal states (for example, the $|$Alive$\rangle$ and $|$Dead$\rangle$ ... more >>>

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

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

Bernhard Fuchs

We investigate the computational hardness of the {\sc Connectivity},

the {\sc Strong Connectivity} and the {\sc Broadcast} type of Range

Assignment Problems in $\R^2$ and $\R^3$.

We present new reductions for the {\sc Connectivity} problem, which

are easily adapted to suit the other two problems. All reductions

are considerably simpler ...
more >>>

Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell

It is becoming increasingly important to understand the vulnerability of machine learning models to adversarial attacks. In this paper we study the feasibility of robust learning from the perspective of computational learning theory, considering both sample and computational complexity. In particular, our definition of robust learnability requires polynomial sample complexity. ... more >>>

Vikraman Arvind, Srikanth Srinivasan

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>Heiner Ackermann, Heiko Röglin, Berthold Vöcking

We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space ... more >>>

Oded Goldreich, Asaf Nussboim

We initiate a general study of pseudo-random implementations

of huge random objects, and apply it to a few areas

in which random objects occur naturally.

For example, a random object being considered may be

a random connected graph, a random bounded-degree graph,

or a random error-correcting code with good ...
more >>>

Shachar Lovett, Jiapeng Zhang

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. ... more >>>

Eli Ben-Sasson, Gal Maor

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

Pierre Péladeau, Denis Thérien

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

Elmar Böhler

A clone is a set of functions that is closed under generalized substitution.

The set FP of functions being computable deterministically in polynomial

time is such a clone. It is well-known that the set of subclones of every

clone forms a lattice. We study the lattice below FP, which ...
more >>>

Alexander Golovnev, Edward Hirsch, Alexander Knop, Alexander Kulikov

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of ... more >>>

Oded Goldreich

We show simple constant-round interactive proof systems for

problems capturing the approximability, to within a factor of $\sqrt{n}$,

of optimization problems in integer lattices; specifically,

the closest vector problem (CVP), and the shortest vector problem (SVP).

These interactive proofs are for the ``coNP direction'';

that is, ...
more >>>

Rahul Santhanam, Srikanth Srinivasan

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for $k$-CNFs:

every k-CNF is a sub-exponential size disjunction of $k$-CNFs with a linear

number of clauses. This lemma has subsequently played a key role in the study

of the exact complexity of the satisfiability problem. A natural question is

more >>>

Ben Lund, Aditya Potukuchi

We show that a random puncturing of a code with good distance is list recoverable beyond the Johnson bound.

In particular, this implies that there are Reed-Solomon codes that are list recoverable beyond the Johnson bound.

It was previously known that there are Reed-Solomon codes that do not have this ...
more >>>

Venkatesan Guruswami, Johan Håstad, Swastik Kopparty

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >

0$, we prove that with high probability a random subspace $C$ of

$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the

property that every Hamming ball of radius $pn$ has at most

$O(1/\varepsilon)$ codewords.

This ... more >>>

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

Consider a linear $[n,k,d]_q$ code $\mc{C}.$ We say that that $i$-th coordinate of $\mc{C}$ has locality $r,$ if the value at this coordinate can be recovered from accessing some other $r$ coordinates of $\mc{C}.$ Data storage applications require codes with small

redundancy, low locality for information coordinates, large distance, and ...
more >>>

Oded Goldreich

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).

In particular, the group theoretic aspects are abstracted as much as possible.

Boris Brimkov, Illya Hicks

In this paper, we reduce the logspace shortest path problem to biconnected graphs; in particular, we present a logspace shortest path algorithm for general graphs which uses a logspace shortest path oracle for biconnected graphs. We also present a linear time logspace shortest path algorithm for graphs with bounded vertex ... more >>>

Thanh Minh Hoang

In the present paper we show some new complexity bounds for

the matching problem for special graph classes.

We show that for graphs with a polynomially bounded number

of nice cycles, the decision perfect matching problem is in

$SPL$, it is hard for $FewL$, and the construction ...
more >>>

Oded Goldreich, Johan Håstad

We investigate the computational complexity of languages

which have interactive proof systems of bounded message complexity.

In particular, we show that

(1) If $L$ has an interactive proof in which the total

communication is bounded by $c(n)$ bits

then $L$ can be recognized a probabilitic machine

in time ...
more >>>

Amir Shpilka, Avishay Tal

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non-linear symmetric Boolean function.

Specifically, we prove that for every non-linear and symmetric $f:\{0,1\}^{k} \to \{0,1\}$ there exists a set $\emptyset\neq S\subset[k]$ such that $|S|=O(\Gamma(k)+\sqrt{k})$, and $\hat{f}(S) \neq 0$, where ...
more >>>

Beate Bollig

Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions.

Some applications work with a restricted variant called complete OBDDs

which is strongly related to nonuniform deterministic finite automata.

One of its complexity measures is the width which has been investigated

in several areas in computer science ...
more >>>

Avi Wigderson

[ This paper is a (self contained) chapter in a new book on computational complexity theory, called Mathematics and Computation, available at https://www.math.ias.edu/avi/book ].

I attempt to give here a panoramic view of the Theory of Computation, that demonstrates its place as a revolutionary, disruptive science, and as a central, ... more >>>

Beate Bollig

Integer multiplication as one of the basic arithmetic functions has been

in the focus of several complexity theoretical investigations.

Ordered binary decision diagrams (OBDDs) are one of the most common

dynamic data structures for boolean functions.

Among the many areas of application are verification, model checking,

computer-aided design, relational algebra, ...
more >>>

James Cook, Omid Etesami, Rachel Miller, Luca Trevisan

A function $f$ mapping $n$-bit strings to $m$-bit strings can be constructed from a bipartite graph with $n$ vertices on the left and $m$ vertices on the right having right-degree $d$ together with a predicate $P:\{0,1\}^d\rightarrow\{0,1\}$. The vertices on the left correspond to the bits of the input to the ... more >>>

Marius Zimand

We show that if DTIME[2^{O(n)}] is not included in DSPACE}[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish ... more >>>

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

more >>>

Stasys Jukna, Georg Schnitger

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

Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi

We study the parameterized complexity of approximating the $k$-Dominating Set (domset) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k) \cdot k$ whenever the graph $G$ has a dominating ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

We make progress on understanding a lower bound technique that was recently used by the authors to prove the first superpolynomial constant-depth circuit lower bounds against algebraic circuits.

More specifically, our previous work applied the well-known partial derivative method in a new setting, that of 'lopsided' set-multilinear polynomials. A ... more >>>

Stefan Edelkamp, Ingo Wegener

Dutton presents a further HEAPSORT variant called

WEAK-HEAPSORT which also contains a new data structure for

priority queues. The sorting algorithm and the underlying

data structure ara analyzed showing that WEAK-HEAPSORT is

the best HEAPSORT variant and that it has a lot of nice

more >>>

Oded Goldreich, Shafi Goldwasser, Dana Ron

We study the possibilities and limitations

of pseudodeterministic algorithms,

a notion put forward by Gat and Goldwasser (2011).

These are probabilistic algorithms that solve search problems

such that on each input, with high probability, they output

the same solution, which may be thought of as a canonical solution.

We consider ...
more >>>

Yanyi Liu, Rafael Pass

Liu and Pass (FOCS'20) recently demonstrated an equivalence between the existence of one-way functions (OWFs) and mild average-case hardness of the time-bounded Kolmogorov complexity problem. In this work, we establish a similar equivalence but to a different form of time-bounded Kolmogorov Complexity---namely, Levin's notion of Kolmogorov Complexity---whose hardness is closely ... more >>>

Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson

The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simulate Cutting Planes and to refute the Tseitin formulas -- certain unsatisfiable systems of linear equations mod 2 -- which are canonical ... more >>>

Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri

Given a finite set $S$ of points (i.e. the stations of a radio

network) on a $d$-dimensional Euclidean space and a positive integer

$1\le h \le |S|-1$, the \minrangeh{d} problem

consists of assigning transmission ranges to the stations so as

to minimize the total power consumption, provided ...
more >>>

Karthik Gajulapalli, Alexander Golovnev, Samuel King

We study the problem of function inversion with preprocessing where, given a function $f : [N] \to [N]$ and a point $y$ in its image, the goal is to find an $x$ such that $f(x) = y$ using at most $T$ oracle queries to $f$ and $S$ bits of preprocessed ... more >>>

Eric Allender, Fengming Wang

We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several

settings.

Vince Grolmusz

We examine the power of Boolean functions with low L_1 norms in several

settings. In large part of the recent literature, the degree of a polynomial

which represents a Boolean function in some way was chosen to be the measure of the complexity of the Boolean function.

However, some functions ...
more >>>

Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah

In this paper we define and examine the power of the conditional-sampling oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, ... more >>>

Beate Bollig, Martin Sauerhoff, Detlef Sieling, Ingo Wegener

Almost the same types of restricted branching programs (or

binary decision diagrams BDDs) are considered in complexity

theory and in applications like hardware verification. These

models are read-once branching programs (free BDDs) and certain

types of oblivious branching programs (ordered and indexed BDDs

with k layers). The complexity of ...
more >>>

Till Tantau

A language is \emph{selective} if there exists a

selection algorithm for it. Such an algorithm selects

from any two words one, which is an element of the

language whenever at least one of them is.

Restricting the complexity of selection algorithms

yields different \emph{selectivity classes} ...
more >>>

Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking ... more >>>

Mrinal Kumar, Shubhangi Saraf

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the {\it Iterated Matrix Multiplication} polynomial - in particular we show that any homogeneous depth 4 circuit computing the $(1,1)$ entry in the product of $n$ ... more >>>

Raghav Kulkarni

The purpose of this paper is to study the deterministic

{\em isolation} for certain structures in directed and undirected

planar graphs.

The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and

\cite{dkr08} isolate a perfect matching in ...
more >>>

Pavol Duris, Juraj Hromkovic, Jose' D. P. Rolim, Georg Schnitger

The study of the computational power of randomized

computations is one of the central tasks of complexity theory. The

main goal of this paper is the comparison of the power of Las Vegas

computation and deterministic respectively nondeterministic

computation. We investigate the power of Las Vegas computation for ...
more >>>

Juraj Hromkovic, Georg Schnitger

The investigation of the computational power of randomized

computations is one of the central tasks of current complexity and

algorithm theory. This paper continues in the comparison of the computational

power of LasVegas computations with the computational power of deterministic

and nondeterministic ones. While for one-way ...
more >>>

Vitaly Feldman

We study the properties of the agnostic learning framework of Haussler (1992)and Kearns, Schapire and Sellie (1992). In particular, we address the question: is there any situation in which membership queries are useful in agnostic learning?

Our results show that the answer is negative for distribution-independent agnostic learning and positive ... more >>>

Mohammad Mahmoody, Hemanta Maji, Manoj Prabhakaran

We qualitatively separate semi-honest secure computation of non-trivial secure-function evaluation (SFE) functionalities from existence of key-agreement protocols.

Technically, we show the existence of an oracle (namely, PKE-oracle) relative to which key-agreement protocols exist; but it is useless for semi-honest secure realization of symmetric 2-party (deterministic finite) SFE functionalities, i.e. any ...
more >>>

Andrew Chi-Chih Yao

In the simultaneous message model, two parties holding $n$-bit integers

$x,y$ send messages to a third party, the {\it referee}, enabling

him to compute a boolean function $f(x,y)$. Buhrman et al

[BCWW01] proved the remarkable result that, when $f$ is the

equality function, the referee can solve this problem by ...
more >>>

Iftach Haitner, Eran Omri, Hila Zarosim

In the random oracle model, the parties are given oracle access to a random member of

a (typically huge) function family, and are assumed to have unbounded computational power

(though they can only make a bounded number of oracle queries). This model provides powerful

properties that allow proving the security ...
more >>>

Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in

the natural way similar to the definition of a randomized

circuit. We exhibit an explicit function $f_{n}$ for which

we prove that:

1) $f_{n}$ can be computed by polynomial size randomized

...
more >>>

Farid Ablayev, Marek Karpinski

We introduce a model of a {\em randomized branching program}

in a natural way similar to the definition of a randomized circuit.

We exhibit an explicit boolean function

$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized

...
more >>>

Chin Ho Lee, Edward Pyne, Salil Vadhan

We give new upper and lower bounds on the power of several restricted classes of arbitrary-order read-once branching programs (ROBPs) and standard-order ROBPs (SOBPs) that have received significant attention in the literature on pseudorandomness for space-bounded computation.

Regular SOBPs of length $n$ and width $\lfloor w(n+1)/2\rfloor$ can exactly simulate general ... more >>>

Iftach Haitner, Danny Harnik, Omer Reingold

We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm ... more >>>

A. Pavan, Raghunath Tewari, N. V. Vinodchandran

We report progress on the \NL\ vs \UL\ problem.

\begin{itemize}

\item[-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$.

\item[-] We investigate the complexity of min-uniqueness - a central

notion in studying the \NL\ vs \UL\ problem.

more >>>

Edward Hirsch, Dmitry Sokolov

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>

Srikanth Srinivasan, S Venkitesh

Nisan and Szegedy (CC 1994) showed that any Boolean function $f:\{0,1\}^n\to\{0,1\}$ that depends on all its input variables, when represented as a real-valued multivariate polynomial $P(x_1,\ldots,x_n)$, has degree at least $\log n - O(\log \log n)$. This was improved to a tight $(\log n - O(1))$ bound by Chiarelli, Hatami ... more >>>

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

We study the probabilistic degree over reals of the OR function on $n$ variables. For an error parameter $\epsilon$ in (0,1/3), the $\epsilon$-error probabilistic degree of any Boolean function $f$ over reals is the smallest non-negative integer $d$ such that the following holds: there exists a distribution $D$ of polynomials ... more >>>

Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial $\mathbf{P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov (1987), upper and lower bounds on probabilistic degrees ... more >>>

Jan Krajicek

Let $g$ be a map defined as the Nisan-Wigderson generator

but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of

$g$ determines a propositional tautology $\tau(g)_b$ expressing this

fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for

P/poly then these ...
more >>>

Nader Bshouty, Lynn Burroughs

We study the proper learnability of axis parallel concept classes

in the PAC learning model and in the exact learning model with

membership and equivalence queries. These classes include union of boxes,

DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$

we ...
more >>>

Jiapeng Zhang

A theorem of Green, Tao, and Ziegler can be stated as follows: if $R$ is a pseudorandom distribution, and $D$ is a dense distribution of $R,$ then $D$ can be modeled as a distribution $M$ which is dense in uniform distribution such that $D$ and $M$ are indistinguishable. The reduction ... more >>>

Jorge Castro

This paper introduces a framework for quantum exact learning via queries, the so-called quantum protocol. It is shown that usual protocols in the classical learning setting have quantum counterparts. A combinatorial notion, the general halving dimension, is also introduced. Given a quantum protocol and a target concept class, the general ... more >>>

Joao Marques-Silva, Mikolas Janota

Propositional Satisfiability (SAT) solvers are routinely used for

solving many function problems.

A natural question that has seldom been addressed is: what is the

best worst-case number of calls to a SAT solver for solving some

target function problem?

This paper develops tighter upper bounds on the query complexity of

more >>>

Oded Goldreich

We consider the query complexity of testing local graph properties in the bounded-degree graph model.

A local property is defined in terms of forbidden subgraphs that are augmented by degree information, where the latter account also for neighbors that are not in the subgraph.

Indeed, this formulation yields a generalized ...
more >>>

Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in ... more >>>

Oded Goldreich, Or Sheffet

We initiate a general study of the randomness complexity of

property testing, aimed at reducing the randomness complexity of

testers without (significantly) increasing their query complexity.

One concrete motovation for this study is provided by the

observation that the product of the randomness and query complexity

of a tester determine ...
more >>>

Hanlin Ren, Rahul Santhanam, Zhikun Wang

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>

Or Meir

Given linear two codes R,C, their tensor product $R \otimes C$

consists of all matrices whose rows are codewords of R and whose

columns are codewords of C. The product $R \otimes C$ is said to

be robust if for every matrix M that is far from $R \otimes C$

more >>>

Amir Shpilka, Ilya Volkovich

We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

Benny Applebaum, Pavel Raykov

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

Nathan Segerlind

We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate $\Res{O(\log n)}$. The ``OBDD proof ... more >>>

Jakob Nordström

The last decade has seen a revival of interest in pebble games in the

context of proof complexity. Pebbling has proven to be a useful tool

for studying resolution-based proof systems when comparing the

strength of different subsystems, showing bounds on proof space, and

establishing size-space trade-offs. The typical approach ...
more >>>

Oded Goldreich

A locally decodable code (LDC) is an error correcting code that allows for recovery of any desired bit in the message based on a constant number of randomly selected bits in the possibly corrupted codeword.

A relaxed LDC requires correct recovery only in case of actual codewords, while requiring that ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the complexity of the isomorphism and automorphism problems for finite rings with unity.

We show that both integer factorization and graph isomorphism reduce to the problem of counting

automorphisms of rings. The problem is shown to be in the complexity class $\AM \cap co\AM$

and hence ...
more >>>

Don Coppersmith, Atri Rudra

Ben-Sasson and Sudan in~\cite{BS04} asked if the following test

is robust for the tensor product of a code with another code--

pick a row (or column) at random and check if the received word restricted to the picked row (or column) belongs to the corresponding code. Valiant showed that ...
more >>>

Alexander Kozachinsky

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>

Mohammad Bavarian, Dmytro Gavinsky, Tsuyoshi Ito

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

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

But what happens if the shared randomness is not perfect?

In this work, ... more >>>

Michael Schmitt

A neural network is said to be nonoverlapping if there is at most one

edge outgoing from each node. We investigate the number of examples

that a learning algorithm needs when using nonoverlapping neural

networks as hypotheses. We derive bounds for this sample complexity

in terms of the Vapnik-Chervonenkis dimension. ...
more >>>

Michael Schmitt

We study networks of spiking neurons that use the timing of pulses

to encode information. Nonlinear interactions model the spatial

groupings of synapses on the dendrites and describe the computations

performed at local branches. We analyze the question of how many

examples these networks must ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

more >>>Maria Isabel Gonzalez Vasco, Igor E. Shparlinski

Boneh and Venkatesan have recently proposed a polynomial time

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

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

strings of the most significant bits of the remainder

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

uniformly at ...
more >>>

Vered Rosen

Assuming the inractability of factoring, we show that the

output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of

the ...
more >>>

Oded Goldreich, Vered Rosen

Assuming the inractability of factoring, we show that

the output of the exponentiation modulo a composite function

$f_{N,g}(x)=g^x\bmod N$ (where $N=P\cdot Q$) is pseudorandom,

even when its input is restricted to be half the size.

This result is equivalent to the simultaneous hardness of the upper

half of the bits ...
more >>>

Johannes Merkle, Ralph Werchner

In this paper we investigate the security of the server aided

RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai

resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the

complexity of attacks on these protocols and show that the bounds are

sharp by describing attacks ...
more >>>

Avishay Tal

The sensitivity of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ is the maximal number of neighbors a point in the Boolean hypercube has with different $f$-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the ... more >>>

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>

Sourav Chakraborty

In this paper we construct a cyclically invariant Boolean function

whose sensitivity is $\Theta(n^{1/3})$. This result answers two

previously published questions. Tur\'an (1984) asked if any

Boolean function, invariant under some transitive group of

permutations, has sensitivity $\Omega(\sqrt{n})$. Kenyon and Kutin

(2004) asked whether for a ``nice'' function the product ...
more >>>

Oded Goldreich, Avi Wigderson

We propose that multi-linear functions of relatively low degree

over GF(2) may be good candidates for obtaining exponential

lower bounds on the size of constant-depth Boolean circuits

(computing explicit functions).

Specifically, we propose to move gradually from linear functions

to multilinear ones, and conjecture that, for any $t\geq2$,

more >>>

Neeraj Kayal, Chandan Saha, Sébastien Tavenas

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

Yael Tauman Kalai, Ran Raz

Linear Programs are abundant in practice, and tremendous effort has been put into designing efficient algorithms for such problems, resulting with very efficient (polynomial time) algorithms. A fundamental question is: what is the space complexity of Linear Programming?

It is widely believed that (even approximating) Linear Programming requires a large ... more >>>

Michael Elberfeld, Christoph Stockhusen, Till Tantau

Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. ... more >>>

Eldar Fischer

An $\epsilon$-test for a property $P$ of functions from

${\cal D}=\{1,\ldots,d\}$ to the positive integers is a randomized

algorithm, which makes queries on the value of an input function at

specified locations, and distinguishes with high probability between the

case of the function satisfying $P$, and the case that it ...
more >>>

Ilario Bonacina, Maria Luisa Bonet

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>

Amir Shpilka, Ben Lee Volk, Avishay Tal

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of $f$ is $\|\hat{f}\|_1=\sum_{\alpha}|\hat{f}(\alpha)|$). Specifically, we prove the following results for functions $f:\{0,1\}^n\to \{0,1\}$ with $\|\hat{f}\|_1=A$.

1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f|_V$ is constant.

2. ... more >>>

Elad Haramaty, Amir Shpilka

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias ... more >>>

Ninad Rajgopal, Rahul Santhanam

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and EXP/poly. We show the following:

1. (Unconditional Lower Bounds for Learning) Building on [KKO13], we prove unconditionally that BPE/poly cannot be weakly ... more >>>

Patrick Scharpfenecker

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

Christoph Buchheim, Peter J Cameron, Taoyang Wu

We investigate the computational complexity of finding an element of

a permutation group~$H\subseteq S_n$ with a minimal distance to a

given~$\pi\in S_n$, for different metrics on~$S_n$. We assume

that~$H$ is given by a set of generators, such that the problem

cannot be solved in polynomial time ...
more >>>

Arturs Backurs, Mohammad Bavarian

For a multilinear polynomial $p(x_1,...x_n)$, over the reals, the $L1$-influence is defined to be $\sum_{i=1}^n E_x\left[\frac{|p(x)-p(x^i)|}{2} \right]$, where $x^i$ is $x$ with $i$-th bit swapped. If $p$ maps $\{-1,1\}^n$ to $[-1,1]$, we prove that the $L1$-influence of $p$ is upper bounded by a function of its degree (and independent of ... more >>>

Neeraj Kayal, Chandan Saha

The sum of square roots problem over integers is the task of deciding the sign of a nonzero sum, $S = \Sigma_{i=1}^{n}{\delta_i}$ . \sqrt{$a_i$}, where $\delta_i \in$ { +1, -1} and $a_i$'s are positive integers that are upper bounded by $N$ (say). A fundamental open question in numerical analysis and ... more >>>

Nikhil Gupta, Chandan Saha

In a Nisan-Wigderson design polynomial (in short, a design polynomial), the gcd of every pair of monomials has a low degree. A useful example of such a polynomial is the following:

$$\text{NW}_{d,k}(\mathbf{x}) = \sum_{h \in \mathbb{F}_d[z], ~\deg(h) \leq k}{~~~~\prod_{i = 0}^{d-1}{x_{i, h(i)}}},$$

where $d$ is a prime, $\mathbb{F}_d$ is the ...
more >>>

Yonatan Nakar, Dana Ron

In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998). While the family studied by Goldreich et al. includes a variety of natural properties, such as k-colorability and containing a ... more >>>

Jin-Yi Cai, Vinay Choudhary

Valiant has proposed a new theory of algorithmic

computation based on perfect matchings and the Pfaffian.

We study the properties of {\it matchgates}---the basic

building blocks in this new theory. We give a set of

algebraic identities

which completely characterize these objects in terms of

the ...
more >>>

Igor E. Shparlinski

We show that a pseudo-random number generator,

introduced recently by M. Naor and O. Reingold,

possess one more attractive and useful property.

Namely, it is proved that for almost all values of parameters it

produces a uniformly distributed sequence.

The proof is based on some recent bounds of exponential

more >>>

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

We show that there is a constant $k$ such that Buss's intuitionistic theory $\mathbf{IS}^1_2$ does not prove that SAT requires co-nondeterministic circuits of size at least $n^k$. To our knowledge, this is the first unconditional unprovability result in bounded arithmetic in the context of worst-case fixed-polynomial size circuit lower bounds. ... more >>>

Paul Beame, Trinh Huynh

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>

Radu Curticapean, Nutan Limaye, Srikanth Srinivasan

A polynomial $P\in F[x_1,\ldots,x_n]$ is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, ... more >>>

Alexander Razborov

In this paper we initiate the study of width in semi-algebraic proof systems

and various cut-based procedures in integer programming. We focus on two

important systems: Gomory-Chv\'atal cutting planes and

Lov\'asz-Schrijver lift-and-project procedures. We develop general methods for

proving width lower bounds and apply them to random $k$-CNFs and several ...
more >>>

Mrinal Kumar

We show that over the field of complex numbers, every homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, ... more >>>

Ludmila Glinskih, Dmitry Itsykson

We show that any nondeterministic read-once branching program that computes a satisfiable Tseitin formula based on an $n\times n$ grid graph has size at least $2^{\Omega(n)}$. Then using the Excluded Grid Theorem by Robertson and Seymour we show that for arbitrary graph $G(V,E)$ any nondeterministic read-once branching program that computes ... more >>>

Stephen A. Fenner, Rohit Gurjar, Arpita Korwar, Thomas Thierauf

We consider the complexity of determining the winner of a finite, two-level poset game.

This is a natural question, as it has been shown recently that determining the winner of a finite, three-level poset game is PSPACE-complete.

We give a simple formula allowing one to compute the status ...
more >>>

Stasys Jukna, Stanislav Zak

We propose an information-theoretic approach to proving lower

bounds on the size of branching programs. The argument is based on

Kraft-McMillan type inequalities for the average amount of

uncertainty about (or entropy of) a given input during the various

stages of computation. The uncertainty is measured by the average

more >>>

Mikolas Janota, Leroy Chew, Olaf Beyersdorff

Several calculi for quantified Boolean formulas (QBFs) exist, but

relations between them are not yet fully understood.

This paper defines a novel calculus, which is resolution-based and

enables unification of the principal existing resolution-based QBF

calculi, namely Q-resolution, long-distance Q-resolution and the expansion-based

calculus ...
more >>>

Ilario Bonacina, Nicola Galesi, Massimo Lauria

Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

more >>>Pushkar Joglekar, Raghavendra Rao B V, Sidhartha Sivakumar

Defining a feasible notion of space over the Blum-Shub-Smale (BSS) model of algebraic computation is a long standing open problem. In an attempt to define a right notion of space complexity for the BSS model, Naurois [CiE, 2007] introduced the notion of weak-space. We investigate the weak-space bounded computations and ... more >>>

Shuichi Hirahara, Mikito Nanashima

A PAC learning model involves two worst-case requirements: a learner must learn all functions in a class on all example distributions. However, basing the hardness of learning on NP-hardness has remained a key challenge for decades. In fact, recent progress in computational complexity suggests the possibility that a weaker assumption ... more >>>

Andrej Bogdanov, Luca Trevisan

We show that if an NP-complete problem has a non-adaptive

self-corrector with respect to a samplable distribution then

coNP is contained in NP/poly and the polynomial

hierarchy collapses to the third level. Feigenbaum and

Fortnow (SICOMP 22:994-1005, 1993) show the same conclusion

under the stronger assumption that an

more >>>

Oded Goldreich, Noam Nisan, Avi Wigderson

Stanislav Busygin, Dmitrii V. Pasechnik

We show that for a graph G it is NP-hard to decide whether its independence number alpha(G) equals its clique partition number ~chi(G) even when some minimum clique partition of G is given. This implies that any alpha(G)-upper bound provably better than ~chi(G) is NP-hard to compute.

To establish this ... more >>>

Peter Auer

We investigate the implications of noise in the equivalence query

model. Besides some results for general target and hypotheses

classes, we prove bounds on the learning complexity of d-dimensional

discretized rectangles in the case where only rectangles are allowed

as hypotheses.

Our noise model assumes ...
more >>>

Peter Auer, Nicolo Cesa-Bianchi

We investigate a variant of the on-line learning model for classes

of {0,1}-valued functions (concepts) in which the labels of a certain

amount of the input instances are corrupted by adversarial noise.

We propose an extension of a general learning strategy, known as

"Closure Algorithm", to this noise ...
more >>>

Piotr Berman, Moses Charikar, Marek Karpinski

We consider the problem of scheduling permanent jobs on related machines

in an on-line fashion. We design a new algorithm that achieves the

competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic

version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,

improving the previous competitive ratios ...
more >>>

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$, settling a ... more >>>

Alexander Razborov, Nikolay Vereshchagin

Assume that A, B are finite families of n-element sets.

We prove that there is an element that simultaneously

belongs to at least |A|/2n sets

in A and to at least |B|/2n sets in B. We use this result to prove

that for any inconsistent DNF's F,G with OR ...
more >>>

Ryan O'Donnell, A. C. Cem Say

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>

Abuzer Yakaryilmaz

Condon and Lipton (FOCS 1989) showed that the class of languages having a space-bounded interactive proof system (IPS) is a proper subset of decidable languages, where the verifier is a probabilistic Turing machine. In this paper, we show that if we use architecturally restricted verifiers instead of restricting the working ... more >>>

Tanmoy Chakraborty, Samir Datta

A monotone planar circuit (MPC) is a Boolean circuit that can be

embedded in a plane, and that has only AND and OR

gates. Yang showed that the one-input-face

monotone planar circuit value problem (MPCVP) is in NC^2, and

Limaye et. al. improved the bound to ...
more >>>

Daniel Apon, Jonathan Katz, Alex Malozemoff

We consider an instance of the following problem: Parties $P_1,..., P_k$ each receive an input $x_i$, and a coordinator (distinct from each of these parties) wishes to compute $f(x_1,..., x_k)$ for some predicate $f$. We are interested in one-round protocols where each party sends a single message to the coordinator; ... more >>>

Egor Klenin, Alexander Kozachinsky

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where ... more >>>

Oded Goldreich, Dana Ron

We consider the query complexity of three versions of the problem of testing monomials and affine (and linear) subspaces with one-sided error, and obtain the following results:

\begin{itemize}

\item The general problem, in which the arity of the monomial (resp., co-dimension of the subspace) is not specified, has ...
more >>>

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Swagato Sanyal

Let $f$ be a Boolean function on $n$-bits, and $\mathsf{IP}$ the inner-product function on $2b$ bits. Let $f^{\mathsf{IP}}:=f \circ \mathsf{IP}^n$ be the two party function obtained by composing $f$ with $\mathsf{IP}$. In this work we bound the one-way communication complexity of $f^{\IP}$ in terms of the non-adaptive query complexity of ... more >>>

Nikhil Mande, Swagato Sanyal

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on ... more >>>

Vladimir Podolskii, Dmitrii Sluch

Boolean function $F(x,y)$ for $x,y \in \{0,1\}^n$ is an XOR function if $F(x,y) = f(x\oplus y)$ for some function $f$ on $n$ input bits, where $\oplus$ is a bit-wise XOR. XOR functions are relevant in communication complexity, partially for allowing Fourier analytic technique. For total XOR functions it is known ... more >>>

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

We study deterministic one-way communication complexity

of functions with Hankel communication matrices.

Some structural properties of such matrices are established

and applied to the one-way two-party communication complexity

of symmetric Boolean functions.

It is shown that the number of required communication bits

does not depend on ...
more >>>

Yanyi Liu, Rafael Pass

Consider the recently introduced notion of \emph{probabilistic

time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,

CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.

We show the equivalence of the following:

- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable

distribution $\D$;

- ...
more >>>

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, Ilya Volkovich

One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence ... more >>>

Shuichi Hirahara, Zhenjian Lu, Igor Oliveira

We introduce $\mathrm{pKt}$ complexity, a new notion of time-bounded Kolmogorov complexity that can be seen as a probabilistic analogue of Levin's $\mathrm{Kt}$ complexity. Using $\mathrm{pKt}$ complexity, we upgrade two recent frameworks that characterize one-way functions ($\mathrm{OWFs}$) via symmetry of information and meta-complexity, respectively. Among other contributions, we establish the following ... more >>>

Agrawal Manindra, Osamu Watanabe

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.

It states that all sets complete for NP under polynomial-time many-one

reductions are P-isomorphic to each other. From previous research

it has been widely believed that all NP-complete sets are reducible

each other by one-to-one and length-increasing polynomial-time

reductions, but ...
more >>>

Shuichi Hirahara, Mikito Nanashima

The fundamental theorem of Goldreich, Micali, and Wigderson (J. ACM 1991) shows that the existence of a one-way function is sufficient for constructing computational zero knowledge ($\mathrm{CZK}$) proofs for all languages in $\mathrm{NP}$. We prove its converse, thereby establishing characterizations of one-way functions based on the worst-case complexities of ... more >>>

Emanuele Viola, Avi Wigderson

In this paper we study the one-way multi-party communication model,

in which every party speaks exactly once in its turn. For every

fixed $k$, we prove a tight lower bound of

$\Omega{n^{1/(k-1)}}$ on the probabilistic communication

complexity of pointer jumping in a $k$-layered tree, where the

pointers of the $i$-th ...
more >>>

Rakesh Mohanty, N. S. Narayanaswamy

The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic ... more >>>

Alexander Fanghänel, Sascha Geulen, Martin Hoefer, Berthold Vöcking

In this paper we study a dynamic version of capacity maximization in the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension $d$ arrive iteratively over time. When a new request arrives, an online algorithm needs to decide ... more >>>

John Hitchcock

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one ... more >>>

Oded Goldreich

We briefly discuss a few open problems in the study of various models of testing graph properties, focusing on the query complexity of the various tasks. In the dense graph model, we discuss several open problems, including:

* Determining the complexity of testing triangle-freeness.

* Characterizing the class of properties ...
more >>>

Dean Doron, Edward Pyne, Roei Tell

We provide compelling evidence for the potential of hardness-vs.-randomness approaches to make progress on the long-standing problem of derandomizing space-bounded computation.

Our first contribution is a derandomization of bounded-space machines from hardness assumptions for classes of uniform deterministic algorithms, for which strong (but non-matching) lower bounds can be unconditionally proved. ... more >>>

Ryuhei Uehara, Kensei Tsuchida, Ingo Wegener

Decision trees are a very general computation model.

Here the problem is to identify a Boolean function $f$ out of a given

set of Boolean functions $F$ by asking for the value of $f$ at adaptively

chosen inputs.

For classes $F$ consisting of functions which may be obtained from one

more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of monotonicity testing of the boolean hypercube is a classic well-studied, yet unsolved

question in property testing. We are given query access to $f:\{0,1\}^n \mapsto R$

(for some ordered range $R$). The boolean hypercube ${\cal B}^n$ has a natural partial order, denoted by $\prec$ (defined by the product ...
more >>>

Alexander A. Sherstov

The threshold degree of a function

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

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

prove that the intersection of two halfspaces on

$\{0,1\}^n$ has threshold degree $\Omega(n),$ which

matches the trivial upper bound and completely answers

a question due to Klivans (2002). The best ...
more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Jose Rolim

We prove an optimal bound on the Shannon function

$L(n,m,\epsilon)$ which describes the trade-off between the

circuit-size complexity and the degree of approximation; that is

$$L(n,m,\epsilon)\ =\

\Theta\left(\frac{m\epsilon^2}{\log(2 + m\epsilon^2)}\right)+O(n).$$

Our bound applies to any partial boolean function

and any ...
more >>>

Matthew Franklin, Ran Gelles, Rafail Ostrovsky, Leonard Schulman

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

The classical coding theorem in Kolmogorov complexity states that if an $n$-bit string $x$ is sampled with probability $\delta$ by an algorithm with prefix-free domain then K$(x) \leq \log(1/\delta) + O(1)$. In a recent work, Lu and Oliveira [LO21] established an unconditional time-bounded version of this result, by showing that ... more >>>

Yuichi Yoshida

Raghavendra (STOC 2008) gave an elegant and surprising result: if Khot's Unique Games Conjecture (STOC 2002) is true, then for every constraint satisfaction problem (CSP), the best approximation ratio is attained by a certain simple semidefinite programming and a rounding scheme for it.

In this paper, we show that a ...
more >>>

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the error resilience of the message exchange task: Two parties, each holding a private input, want to exchange their inputs. However, the channel connecting them is governed by an adversary that may corrupt a constant fraction of the transmissions. What is the maximum fraction of corruptions that still ... more >>>

Vitaly Feldman

We consider the problem of finding a monomial (or a term) that maximizes the agreement rate with a given set of examples over the Boolean hypercube. The problem originates in learning and is referred to as {\em agnostic learning} of monomials. Finding a monomial with the highest agreement rate was ... more >>>

Edward Hirsch, Dmitry Itsykson, Valeria Nikolaenko, Alexander Smal

The existence of optimal algorithms is not known for any decision problem in NP$\setminus$P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both randomized and deterministic settings (a heuristic algorithm can err on a ... more >>>

Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>>

Amey Bhangale, Subhash Khot

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

Per Austrin, Jonah Brown-Cohen, Johan Håstad

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many ... more >>>

Alexander A. Sherstov, Pei Wu

Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky ... more >>>

Jelani Nelson, Huacheng Yu

We show optimal lower bounds for spanning forest computation in two different models:

* One wants a data structure for fully dynamic spanning forest in which updates can insert or delete edges amongst a base set of $n$ vertices. The sole allowed query asks for a spanning forest, which the ... more >>>

Ryan O'Donnell, YI WU, Yuan Zhou

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

Sepehr Assadi, Gillat Kol, Zhijun Zhang

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees ... more >>>

Martin Sauerhoff, Ingo Wegener, Ralph Werchner

Many Boolean functions have short representations by OBDDs (ordered

binary decision diagrams) if appropriate variable orderings are used.

For tree-like circuits, which may contain EXOR-gates, it is proved

that some depth first traversal leads to an optimal variable ordering.

Moreover, an optimal variable ordering and the resulting OBDD

can ...
more >>>

Zenon Sadowski

We investigate the connection between optimal propositional

proof systems and complete languages for promise classes.

We prove that an optimal propositional proof system exists

if and only if there exists a propositional proof system

in which every promise class with the test set in co-NP

...
more >>>

Jochen Me\3ner, Jacobo Toran

A polynomial time computable function $h:\Sigma^*\to\Sigma^*$ whose range

is the set of tautologies in Propositional Logic (TAUT), is called

a proof system. Cook and Reckhow defined this concept

and in order to compare the relative strenth of different proof systems,

they considered the notion ...
more >>>

Ashish Dwivedi, Zeyu Guo, Ben Lee Volk

We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC ... more >>>

Shuichi Hirahara, Naoto Ohsaka

In the Minmax Set Cover Reconfiguration problem, given a set system $\mathcal{F}$ over a universe and its two covers $\mathcal{C}^\mathrm{start}$ and $\mathcal{C}^\mathrm{goal}$ of size $k$, we wish to transform $\mathcal{C}^\mathrm{start}$ into $\mathcal{C}^\mathrm{goal}$ by repeatedly adding or removing a single set of $\mathcal{F}$ while covering the universe in any intermediate state. ... more >>>

Meghal Gupta, Mihir Singhal, Hongxun Wu

Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct a new list-decodable family of asymptotically good algebraic-geometric (AG) codes over fixed alphabets. The function fields underlying these codes are constructed using class field theory, specifically Drinfeld modules of rank $1$, and designed to have an automorphism of large order that is used to ``fold" the AG code. ... more >>>

Venkatesan Guruswami, Chaoping Xing

We construct two classes of algebraic code families which are efficiently list decodable with small output list size from a fraction $1-R-\epsilon$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\epsilon$. The alphabet size depends only on $\epsilon$ and is nearly-optimal.

The ... more >>>

Mark Braverman, Ran Gelles, Michael A. Yitayew

We show an efficient method for converting a logic circuit of gates with fan-out 1 into an equivalent circuit that works even if some fraction of its gates are short-circuited, i.e., their output is short-circuited to one of their inputs. Our conversion can be applied to any circuit with fan-in ... more >>>

Yosi Ben-Asher, Ilan Newman

It is well known that the optimal solution for

searching in

a finite total order set is the binary search.

In the binary search we

divide the set into two ``halves'', by querying the middle

element, and continue the search on the suitable half.

What is the equivalent of binary ...
more >>>

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price

We study the problem of testing discrete distributions with a focus on the high probability regime.

Specifically, given samples from one or more discrete distributions, a property $\mathcal{P}$, and

parameters $0< \epsilon, \delta <1$, we want to distinguish {\em with probability at least $1-\delta$}

whether these distributions satisfy $\mathcal{P}$ ...
more >>>

Elad Haramaty, Amir Shpilka, Madhu Sudan

We consider the problem of testing if a given function $f : \F_q^n \rightarrow \F_q$ is close to a $n$-variate degree $d$ polynomial over the finite field $\F_q$ of $q$ elements. The natural, low-query, test for this property would be to pick the smallest dimension $t = t_{q,d}\approx d/q$ such ... more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Piotr Berman, Marek Karpinski, Yakov Nekrich

We prove upper and lower bounds for computing Merkle tree

traversals, and display optimal trade-offs between time

and space complexity of that problem.

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

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}{\epsilon} \cdot \log\frac{d}{\epsilon})$-query nonadaptive tester and a $O(\frac{d}{\epsilon})$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $\epsilon$. Previously known unateness testers worked only for Boolean functions, and their query ... more >>>

Kaave Hosseini, Shachar Lovett, Grigory Yaroslavtsev

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in $n$ dimensions,

the existence of efficient streaming algorithms which can process $\Omega(n^2)$ updates implies efficient linear sketching algorithms with comparable cost.

This improves upon the previous work ...
more >>>

Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

We give a complete answer to the following basic question: ``What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>>

Robert Albin Legenstein

It is shown that the total wire length of layouts of a

balanced binary tree on a 2-dimensional grid can be reduced by 33%

if one does not choose the obvious ``symmetric'' layout strategy.

Furthermore it is shown that the more efficient layout strategy that

is presented in this article ...
more >>>

Ran Raz, Avishay Tal

We present a distribution $D$ over inputs in $\{-1,1\}^{2N}$, such that:

(1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time $O(\log N)$, that distinguishes between $D$ and the uniform distribution with advantage $\Omega(1/\log N)$.

(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ ...
more >>>

Bshouty, Cleve, Gavalda, Kannan, Tamon.

We show what happen to learning if the learner can use NP-oracle.

A consequence of our results we show that

If NP\subset P/poly then the polynomial Hierarchy collapses to ZPP^NP

END_OF_DESCRIPTION

Contact: bshouty@cpsc.ucalgary.ca (Nader Bshouty)

Scott Aaronson

Theoretical computer scientists have been debating the role of

oracles since the 1970's. This paper illustrates both that oracles

can give us nontrivial insights about the barrier problems in

circuit complexity, and that they need not prevent us from trying to

solve those problems.

First, we ... more >>>

Christoph Meinel, Thorsten Theobald

Many problems in computer-aided design of highly integrated circuits

(CAD for VLSI) can be transformed to the task of manipulating objects

over finite domains. The efficiency of these operations depends

substantially on the chosen data structures. In the last years,

ordered binary decision diagrams (OBDDs) have ...
more >>>

Olga Tveretina, Carsten Sinz, Hans Zantema

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential

size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential

size: we prove that the size of one ...
more >>>

Don Coppersmith, Lisa Fleischer, Atri Rudra

We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of $5$ if the weights satisfy \textit{probability constraints}

(for any pair of vertices $u$ and $v$, $w_{uv}+w_{vu}=1$). Special cases ...
more >>>

Jiawei Gao, Russell Impagliazzo

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

Ludwig Staiger

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>Cynthia Dwork, Michael Kim, Omer Reingold, Guy Rothblum, Gal Yona

Prediction algorithms assign numbers to individuals that are popularly understood as individual ``probabilities''---what is the probability of 5-year survival after cancer diagnosis?---and which increasingly form the basis for life-altering decisions. Drawing on an understanding of computational indistinguishability developed in complexity theory and cryptography, we introduce Outcome Indistinguishability. Predictors that are ... more >>>

Periklis Papakonstantinou, Dominik Scheder, Hao Song

We give new characterizations and lower bounds relating classes in the communication complexity polynomial hierarchy and circuit complexity to limited memory communication models.

We introduce the notion of rectangle overlay complexity of a function $f: \{0,1\}^n\times \{0,1\}^n\to\{0,1\}$. This is a natural combinatorial complexity measure in terms of combinatorial rectangles in ... more >>>

Oded Goldreich

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).

Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system

in which the prover runs polynomial time ...
more >>>