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

**P**

__
TR17-004
| 8th January 2017
__

Scott Aaronson#### P=?NP

__
TR12-013
| 15th February 2012
__

Tomas Feder, Carlos Subi#### Packing Edge-Disjoint Triangles in Given Graphs

__
TR06-030
| 17th January 2006
__

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar#### Packing to angles and sectors

__
TR20-014
| 16th February 2020
__

Gil Cohen, Shahar Samocha#### Palette-Alternating Tree Codes

__
TR12-066
| 22nd April 2012
__

Jinyu Huang#### Parallel Complexity for Matroid Intersection and Matroid Parity Problems

Revisions: 1

__
TR98-009
| 25th November 1997
__

Bruce Edward Litow#### Parallel complexity of integer coprimality

Comments: 3

__
TR02-029
| 3rd June 2002
__

Marek Karpinski, Yakov Nekrich#### Parallel Construction of Minimum Redundancy Length-Limited Codes

__
TR00-053
| 5th May 2000
__

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim#### Parallel Read Operations Without Memory Contention

__
TR22-039
| 14th March 2022
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

__
TR22-167
| 23rd November 2022
__

Mark Braverman, Subhash Khot, Dor Minzer#### Parallel Repetition for the GHZ Game: Exponential Decay

__
TR08-013
| 16th January 2008
__

Anup Rao#### Parallel Repetition in Projection Games and a Concentration Bound

__
TR14-054
| 16th April 2014
__

Dana Moshkovitz#### Parallel Repetition of Fortified Games

Revisions: 2

__
TR16-047
| 23rd March 2016
__

Mohammad Bavarian, Thomas Vidick, Henry Yuen#### Parallel repetition via fortification: analytic view and the quantum case

__
TR10-195
| 13th November 2010
__

Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik#### Parallelism, Program Size, Time, and Temperature in Self-Assembly

Revisions: 1

__
TR06-072
| 25th February 2006
__

Henning Fernau#### Parameterized Algorithms for Hitting Set: the Weighted Case

__
TR10-198
| 13th December 2010
__

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov#### Parameterized Bounded-Depth Frege is Not Optimal

__
TR14-134
| 10th October 2014
__

Martin Lück, Arne Meier, Irina Schindler#### Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies

Revisions: 3

__
TR09-131
| 2nd December 2009
__

Stephan Kreutzer, Anuj Dawar#### Parameterized Complexity of First-Order Logic

Revisions: 2

__
TR16-157
| 13th October 2016
__

Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Toran#### Parameterized Complexity of Small Weight Automorphisms

__
TR01-023
| 13th March 2001
__

Jochen Alber, Henning Fernau, Rolf Niedermeier#### Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems

Revisions: 1

__
TR22-156
| 15th November 2022
__

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro#### Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

Revisions: 1

__
TR19-115
| 4th September 2019
__

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx#### Parameterized Intractability of Even Set and Shortest Vector Problem

__
TR18-057
| 26th March 2018
__

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi#### Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

__
TR97-006
| 31st January 1997
__

Marco Cesati, Miriam Di Ianni#### Parameterized Parallel Complexity

Comments: 1

__
TR07-001
| 19th November 2006
__

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider#### Parameterized Proof Complexity: a Complexity Gap for Parameterized Tree-like Resolution

Revisions: 1

__
TR17-103
| 12th June 2017
__

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Parameterized Property Testing of Functions

__
TR04-027
| 20th February 2004
__

Henning Fernau#### Parametric Duality: Kernel Sizes and Algorithmics

__
TR18-211
| 3rd December 2018
__

Kshitij Gajjar, Jaikumar Radhakrishnan#### Parametric Shortest Paths in Planar Graphs

Revisions: 1

__
TR97-033
| 1st August 1997
__

Meena Mahajan, Venkatesh Raman#### Parametrizing Above Guaranteed Values: MaxSat and MaxCut

__
TR10-153
| 7th October 2010
__

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria#### Paris-Harrington tautologies

Revisions: 2

__
TR18-174
| 19th October 2018
__

Anastasiya Chistopolskaya, Vladimir Podolskii#### Parity Decision Tree Complexity is Greater Than Granularity

Revisions: 2

__
TR13-092
| 19th June 2013
__

Pavel Pudlak, Arnold Beckmann, Neil Thapen#### Parity Games and Propositional Proofs

Revisions: 1

__
TR01-073
| 24th October 2001
__

Beate Bollig, Philipp Woelfel, Stephan Waack#### Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication

Revisions: 1

__
TR19-073
| 17th May 2019
__

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan#### Parity helps to compute Majority

__
TR07-035
| 3rd April 2007
__

Mark Braverman, Raghav Kulkarni, Sambuddha Roy#### Parity Problems in Planar Graphs

__
TR04-025
| 24th January 2004
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Partial Bi-Immunity and NP-Completeness

__
TR14-011
| 22nd January 2014
__

Dmytro Gavinsky, Pavel Pudlak#### Partition Expanders

__
TR06-016
| 1st February 2006
__

Tomas Feder, Carlos Subi#### Partition into $k$-vertex subgraphs of $k$-partite graphs

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR05-002
| 6th January 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

__
TR95-022
| 2nd May 1995
__

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara#### Pattern-Matching for Strings with Short Descriptions

__
TR98-066
| 3rd November 1998
__

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra#### PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

__
TR21-084
| 21st June 2021
__

Liron Bronfman, Ron Rothblum#### PCPs and Instance Compression from a Cryptographic Lens

__
TR10-017
| 10th February 2010
__

Jonathan Ullman, Salil Vadhan#### PCPs and the Hardness of Generating Synthetic Data

Revisions: 4

__
TR13-122
| 5th September 2013
__

Irit Dinur, Venkatesan Guruswami#### PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

__
TR18-099
| 19th May 2018
__

Scott Aaronson#### PDQP/qpoly = ALL

__
TR16-067
| 20th April 2016
__

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani#### Pebbling Meets Coloring : Reversible Pebble Game On Trees

__
TR13-006
| 8th January 2013
__

Balagopal Komarath, Jayalal Sarma#### Pebbling, Entropy and Branching Program Size Lower Bounds

__
TR15-208
| 26th December 2015
__

Shafi Goldwasser, Ofer Grossman#### Perfect Bipartite Matching in Pseudo-Deterministic $RNC$

Revisions: 2

__
TR00-080
| 24th July 2000
__

Marco Cesati#### Perfect Code is W[1]-complete

__
TR10-201
| 21st December 2010
__

Samir Datta, Raghav Kulkarni, Raghunath Tewari#### Perfect Matching in Bipartite Planar Graphs is in UL

Revisions: 1

__
TR05-097
| 31st August 2005
__

Jens Groth, Rafail Ostrovsky, Amit Sahai#### Perfect Non-Interactive Zero Knowledge for NP

__
TR19-086
| 7th June 2019
__

Alex Bredariol Grilo, William Slofstra, Henry Yuen#### Perfect zero knowledge for quantum multiprover interactive proofs

__
TR19-035
| 5th March 2019
__

Alexey Milovanov#### PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials

__
TR18-208
| 27th November 2018
__

Benny Applebaum, Prashant Nalini Vasudevan#### Placing Conditional Disclosure of Secrets in the Communication Complexity Universe

Revisions: 2

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR11-009
| 21st January 2011
__

Samir Datta, Gautam Prakriya#### Planarity Testing Revisited

__
TR19-039
| 12th March 2019
__

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee#### Planarity, Exclusivity, and Unambiguity

Comments: 1

__
TR11-148
| 3rd November 2011
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf#### Planarizing Gadgets for Perfect Matching do not Exist

__
TR16-151
| 26th September 2016
__

Amir Yehudayoff#### Pointer chasing via triangular discrimination

__
TR97-008
| 16th March 1997
__

Noam Nisan, Ziv Bar-Yossef#### Pointer Jumping Requires Concurrent Read

__
TR08-090
| 6th August 2008
__

Ulrich Schöpp, Martin Hofmann#### Pointer Programs and Undirected Reachability

Revisions: 1

__
TR05-157
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Points on Computable Curves

__
TR13-050
| 1st April 2013
__

Venkatesan Guruswami, Patrick Xia#### Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

__
TR12-165
| 19th November 2012
__

Martin Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret#### Polly Cracker, Revisited

__
TR09-011
| 31st January 2009
__

Mark Braverman#### Poly-logarithmic independence fools AC0 circuits

__
TR20-042
| 31st March 2020
__

Pranav Bisht, Nitin Saxena#### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

__
TR06-008
| 23rd November 2005
__

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour#### Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk

__
TR05-117
| 17th September 2005
__

Piotr Indyk, David P. Woodruff#### Polylogarithmic Private Approximations and Efficient Matching

__
TR04-053
| 17th June 2004
__

A. Pavan, N. V. Vinodchandran#### Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

__
TR04-007
| 13th January 2004
__

Alan L. Selman, Samik Sengupta#### Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy

Revisions: 1
,
Comments: 1

__
TR06-081
| 19th May 2006
__

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis#### Polynomial Algorithms for Approximating Nash Equilibria of Bimatrix Games

__
TR94-024
| 12th December 1994
__

Marek Karpinski, Angus Macintyre#### Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

__
TR22-043
| 2nd April 2022
__

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

__
TR19-052
| 9th April 2019
__

Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen#### Polynomial calculus space and resolution width

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

__
TR14-018
| 13th February 2014
__

Arnab Bhattacharyya#### Polynomial decompositions in polynomial time

__
TR03-036
| 27th April 2003
__

Bruce Edward Litow#### Polynomial equation elimination via Tarski Algebra

__
TR05-150
| 5th December 2005
__

Neeraj Kayal, Nitin Saxena#### Polynomial Identity Testing for Depth 3 Circuits

__
TR22-115
| 17th August 2022
__

Dieter van Melkebeek, Andrew Morgan#### Polynomial Identity Testing via Evaluation of Rational Functions

__
TR01-067
| 18th September 2001
__

Hubie Chen#### Polynomial Programs and the Razborov-Smolensky Method

__
TR13-021
| 5th February 2013
__

Kristoffer Arnsfelt Hansen, Vladimir Podolskii#### Polynomial threshold functions and Boolean threshold circuits

__
TR07-037
| 2nd February 2007
__

Leonid Gurvits#### Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Revisions: 1

__
TR98-064
| 6th November 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

__
TR01-034
| 30th April 2001
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

__
TR02-025
| 26th April 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani#### Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

__
TR97-024
| 9th June 1997
__

Marek Karpinski#### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

__
TR03-059
| 18th May 2003
__

Harumichi Nishimura, Tomoyuki Yamakami#### Polynomial time quantum computation with advice

Revisions: 2

__
TR94-005
| 12th December 1994
__

Noga Alon, Alan Frieze, Dominic Welsh#### Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

__
TR95-039
| 11th July 1995
__

Tomoyuki Yamakami#### Polynomial Time Samplable Distributions

Revisions: 2

__
TR09-039
| 6th April 2009
__

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos#### Polynomial Time with Restricted Use of Randomness

__
TR10-133
| 20th August 2010
__

Parikshit Gopalan, Adam Klivans, Raghu Meka#### Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs

__
TR06-082
| 18th June 2006
__

Prabhu Manyem#### Polynomial-Time Maximisation Classes: Syntactic Hierarchy

__
TR23-076
| 24th May 2023
__

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam#### Polynomial-Time Pseudodeterministic Construction of Primes

__
TR18-018
| 22nd January 2018
__

John Hitchcock, Adewale Sekoni, Hadi Shafei#### Polynomial-Time Random Oracles and Separating Complexity Classes

__
TR00-049
| 2nd May 2000
__

Herbert Fleischner, Stefan Szeider#### Polynomial-Time Recognition of Minimal Unsatisfiable Formulas with Fixed Clause-Variable Difference

__
TR15-085
| 23rd May 2015
__

Irit Dinur, Prahladh Harsha, Guy Kindler#### Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

__
TR15-196
| 4th December 2015
__

Andris Ambainis#### Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Revisions: 1

__
TR12-118
| 18th September 2012
__

Avi Wigderson, Amir Yehudayoff#### Population Recovery and Partial Identification

__
TR21-013
| 20th January 2021
__

Srinivasan Arunachalam, Penghui Yao#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

__
TR21-038
| 15th March 2021
__

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry#### Post-Quantum Succinct Arguments

Revisions: 1

__
TR21-167
| 23rd November 2021
__

Alex Lombardi, Fermi Ma, Nicholas Spooner#### Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)

Revisions: 1

__
TR02-028
| 15th May 2002
__

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek#### Power from Random Strings

Revisions: 1

__
TR22-186
| 31st December 2022
__

Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma#### Power of Decision Trees with Monotone Queries

__
TR96-045
| 28th August 1996
__

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

Comments: 2

__
TR02-036
| 30th May 2002
__

Stephen A. Fenner#### PP-lowness and a simple definition of AWPP

__
TR22-128
| 11th September 2022
__

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach#### PPP-Completeness and Extremal Combinatorics

__
TR18-113
| 30th May 2018
__

Dominik Scheder#### PPSZ for $k \geq 5$: More Is Better

__
TR21-069
| 12th May 2021
__

Dominik Scheder#### PPSZ is better than you think

Revisions: 1

__
TR18-179
| 31st October 2018
__

Dominik Scheder#### PPSZ on CSP Instances with Multiple Solutions

__
TR20-059
| 16th April 2020
__

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma#### Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

__
TR20-007
| 19th December 2019
__

Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang#### Practical Relativistic Zero-Knowledge for NP

__
TR17-191
| 15th December 2017
__

Alexander Smal, Navid Talebanfard#### Prediction from Partial Information and Hindsight, an Alternative Proof

Revisions: 2

__
TR17-149
| 7th October 2017
__

Or Meir, Avi Wigderson#### Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds

Revisions: 5

__
TR01-043
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Predictive complexity and information

__
TR05-119
| 15th September 2005
__

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini#### Preferred representations of Boolean relations

__
TR16-172
| 3rd November 2016
__

William Hoza, Adam Klivans#### Preserving Randomness for Adaptive Algorithms

Revisions: 4

__
TR00-047
| 29th June 2000
__

Tobias Polzin, Siavash Vahdati Daneshmand#### Primal-Dual Approaches to the Steiner Problem

__
TR03-071
| 18th August 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Privacy in Non-Private Environments

Revisions: 1

__
TR05-141
| 29th November 2005
__

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb#### Private Approximation of Search Problems

__
TR03-009
| 3rd February 2003
__

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey#### Private Computation --- $k$-connected versus $1$-connected Networks

Revisions: 1

__
TR01-051
| 4th May 2001
__

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont#### Probabilistic abstraction for model checking: An approach based on property testing

Revisions: 1

__
TR18-123
| 3rd July 2018
__

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

Revisions: 1

__
TR17-070
| 15th April 2017
__

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy#### Probabilistic Existence of Large Sets of Designs

__
TR11-144
| 2nd November 2011
__

Greg Kuperberg, Shachar Lovett, Ron Peled#### Probabilistic existence of rigid combinatorial structures

__
TR22-072
| 15th May 2022
__

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira#### Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

__
TR17-036
| 22nd February 2017
__

Dean Doron, Francois Le Gall, Amnon Ta-Shma#### Probabilistic logarithmic-space algorithms for Laplacian solvers

__
TR00-085
| 19th September 2000
__

Rustam Mubarakzjanov#### Probabilistic OBDDs: on Bound of Width versus Bound of Error

__
TR94-008
| 12th December 1994
__

Oded Goldreich#### Probabilistic Proof Systems (A Survey)

__
TR11-136
| 12th October 2011
__

eran gat , shafi goldwasser#### Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications

Revisions: 1

__
TR96-035
| 27th March 1996
__

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner#### Probabilistic Type-2 Operators and ``Almost''-Classes

__
TR01-027
| 23rd March 2001
__

Marius Zimand#### Probabilistically Checkable Proofs The Easy Way

__
TR98-040
| 24th July 1998
__

Madhu Sudan, Luca Trevisan#### Probabilistically checkable proofs with low amortized query complexity

__
TR01-063
| 5th August 2001
__

Michal Parnas, Dana Ron, Alex Samorodnitsky#### Proclaiming Dictators and Juntas or Testing Boolean Formulae

Revisions: 1

__
TR23-133
| 13th September 2023
__

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer#### Product mixing in compact Lie groups

__
TR09-101
| 20th October 2009
__

Nitin Saxena#### Progress on Polynomial Identity Testing

__
TR13-186
| 27th December 2013
__

Nitin Saxena#### Progress on Polynomial Identity Testing - II

__
TR16-183
| 16th November 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

Revisions: 2

__
TR04-098
| 5th November 2004
__

Lance Fortnow, Rahul Santhanam, Luca Trevisan#### Promise Hierarchies

__
TR21-043
| 15th March 2021
__

Peter Dixon, A. Pavan, N. V. Vinodchandran#### Promise Problems Meet Pseudodeterminism

__
TR16-098
| 16th June 2016
__

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson#### Proof Complexity Lower Bounds from Algebraic Circuit Complexity

__
TR20-184
| 10th December 2020
__

Dmitry Itsykson, Artur Riazanov#### Proof complexity of natural formulas via communication arguments

__
TR14-120
| 16th September 2014
__

Olaf Beyersdorff, Leroy Chew, Mikolas Janota#### Proof Complexity of Resolution-based QBF Calculi

__
TR19-057
| 6th April 2019
__

Olaf Beyersdorff, Joshua Blinkhorn#### Proof Complexity of Symmetry Learning in QBF

__
TR23-053
| 19th April 2023
__

Leroy Chew#### Proof Simulation via Round-based Strategy Extraction for QBF

__
TR09-092
| 8th October 2009
__

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller#### Proof Systems that Take Advice

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
TR12-120
| 24th September 2012
__

Boaz Barak#### Proof vs. Truth in Computational Complexity

Revisions: 1

__
TR15-024
| 16th February 2015
__

Oded Goldreich, Tom Gur, Ron Rothblum#### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

__
TR17-155
| 13th October 2017
__

Alessandro Chiesa, Tom Gur#### Proofs of Proximity for Distribution Testing

Revisions: 1

__
TR17-114
| 1st July 2017
__

Maciej Li\'skiewicz, Matthias Lutter, Rüdiger Reischuk#### Proper Learning of k-term DNF Formulas from Satisfying Assignments

__
TR15-040
| 24th March 2015
__

Shay Moran, Amir Yehudayoff#### Proper PAC learning is compressing

Revisions: 1

__
TR12-163
| 24th November 2012
__

Avishay Tal#### Properties and Applications of Boolean Function Composition

__
TR04-019
| 15th January 2004
__

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta#### Properties of NP-Complete Sets

__
TR04-096
| 4th November 2004
__

Eldar Fischer, Frederic Magniez, Michel de Rougemont#### Property and Equivalence Testing on Strings

Revisions: 1

__
TR96-057
| 18th November 1996
__

Oded Goldreich, Dana Ron#### Property Testing and its connection to Learning and Approximation

__
TR13-142
| 11th October 2013
__

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni#### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

Revisions: 2

__
TR11-045
| 1st April 2011
__

Eric Blais, Joshua Brody, Kevin Matulef#### Property Testing Lower Bounds via Communication Complexity

Revisions: 1

__
TR08-040
| 3rd April 2008
__

Sourav Chakraborty, Laszlo Babai#### Property Testing of Equivalence under a Permutation Group Action

__
TR13-187
| 27th December 2013
__

Peyman Afshani, Kevin Matulef, Bryan Wilkinson#### Property Testing on Linked Lists

Revisions: 1

__
TR14-042
| 2nd April 2014
__

Kashyap Dixit, Deeparnab Chakrabarty, Madhav Jha, C. Seshadhri#### Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties

__
TR10-156
| 24th October 2010
__

Victor Chen, Madhu Sudan, Ning Xie#### Property Testing via Set-Theoretic Operations

__
TR16-007
| 23rd January 2016
__

Guy Kindler#### Property Testing, PCP, andJuntas

Revisions: 1

__
TR98-067
| 12th November 1998
__

Paul Beame#### Propositional Proof Complexity: Past, Present and Future

__
TR23-066
| 4th May 2023
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Protecting Single-Hop Radio Networks from Message Drops

__
TR23-142
| 21st September 2023
__

Tom Gur, Wilfred Salmon, Sergii Strelchuk#### Provable Advantage in Quantum PAC Learning

__
TR21-180
| 21st December 2021
__

Noga Ron-Zewi, Ron Rothblum#### Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead

__
TR05-080
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width I: non-approximability of sequential clique-width

Revisions: 1

__
TR05-081
| 21st July 2005
__

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider#### Proving NP-hardness for clique-width II: non-approximability of clique-width

Revisions: 1

__
TR18-003
| 2nd January 2018
__

Roei Tell#### Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

Revisions: 5

__
TR23-016
| 22nd February 2023
__

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals#### Proving Unsatisfiability with Hitting Formulas

__
TR20-083
| 30th May 2020
__

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf#### Proximity Gaps for Reed-Solomon Codes

Revisions: 3

__
TR10-058
| 7th April 2010
__

Oded Goldreich, Tali Kaufman#### Proximity Oblivious Testing and the Role of Invariances

Revisions: 1

__
TR18-122
| 3rd July 2018
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudo-derandomizing learning and approximation

__
TR17-105
| 14th June 2017
__

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden#### Pseudo-Deterministic Proofs

__
TR19-177
| 6th December 2019
__

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff#### Pseudo-deterministic Streaming

__
TR19-078
| 1st June 2019
__

Itai Benjamini, Oded Goldreich#### Pseudo-Mixing Time of Random Walks

__
TR12-119
| 24th September 2012
__

Ilario Bonacina, Nicola Galesi#### Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems

__
TR01-064
| 10th September 2001
__

Moni Naor, Omer Reingold, Alon Rosen#### Pseudo-Random Functions and Factoring

__
TR21-132
| 11th September 2021
__

Eric Binnendyk#### Pseudo-random functions and uniform learnability

Revisions: 1

__
TR20-151
| 8th October 2020
__

Venkatesan Guruswami, Vinayak Kumar#### Pseudobinomiality of the Sticky Random Walk

__
TR21-039
| 15th March 2021
__

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Algorithms and the Structure of Probabilistic Time

__
TR16-196
| 5th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Pseudodeterministic Constructions in Subexponential Time

__
TR21-019
| 17th February 2021
__

Edward Pyne, Salil Vadhan#### Pseudodistributions That Beat All Pseudorandom Generators

Revisions: 1

__
TR19-051
| 9th April 2019
__

Emanuele Viola#### Pseudorandom bits and lower bounds for randomized Turing machines

__
TR05-043
| 5th April 2005
__

Emanuele Viola#### Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

__
TR17-122
| 28th July 2017
__

Rohit Gurjar, Ben Lee Volk#### Pseudorandom Bits for Oblivious Branching Programs

__
TR07-081
| 10th August 2007
__

Andrej Bogdanov, Emanuele Viola#### Pseudorandom bits for polynomials

__
TR18-028
| 7th February 2018
__

Xin Li#### Pseudorandom Correlation Breakers, Independence Preserving Mergers and their Applications

Revisions: 1

__
TR17-113
| 1st July 2017
__

Andrej Bogdanov, Alon Rosen#### Pseudorandom Functions: Three Decades Later

__
TR10-033
| 6th March 2010
__

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka#### Pseudorandom generators for $\mathrm{CC}_0[p]$ and the Fourier spectrum of low-degree polynomials over finite fields

__
TR10-168
| 9th November 2010
__

Thomas Watson#### Pseudorandom Generators for Combinatorial Checkerboards

Revisions: 2

__
TR10-176
| 15th November 2010
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman#### Pseudorandom Generators for Combinatorial Shapes

Revisions: 1

__
TR10-113
| 16th July 2010
__

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak#### Pseudorandom Generators for Group Products

__
TR13-155
| 10th November 2013
__

Gil Cohen, Amnon Ta-Shma#### Pseudorandom Generators for Low Degree Polynomials from Algebraic Geometry Codes

Revisions: 2

__
TR17-025
| 16th February 2017
__

Pooya Hatami, Avishay Tal#### Pseudorandom Generators for Low-Sensitivity Functions

__
TR18-147
| 19th August 2018
__

Michael Forbes, Zander Kelley#### Pseudorandom Generators for Read-Once Branching Programs, in any Order

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR20-138
| 9th September 2020
__

William Hoza, Edward Pyne, Salil Vadhan#### Pseudorandom Generators for Unbounded-Width Permutation Branching Programs

Revisions: 1

__
TR18-112
| 5th June 2018
__

Raghu Meka, Omer Reingold, Avishay Tal#### Pseudorandom Generators for Width-3 Branching Programs

Revisions: 1

__
TR18-015
| 25th January 2018
__

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett#### Pseudorandom Generators from Polarizing Random Walks

Revisions: 1
,
Comments: 1

__
TR18-155
| 8th September 2018
__

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal#### Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates

__
TR00-023
| 11th May 2000
__

Michael Alekhnovich, Eli Ben-Sasson, Alexander Razborov, Avi Wigderson#### Pseudorandom Generators in Propositional Proof Complexity

__
TR11-007
| 17th January 2011
__

Benny Applebaum#### Pseudorandom Generators with Long Stretch and Low locality from Random Local One-Way Functions

Revisions: 3

__
TR98-074
| 16th December 1998
__

Madhu Sudan, Luca Trevisan, Salil Vadhan#### Pseudorandom generators without the XOR Lemma

Revisions: 2

__
TR95-006
| 1st January 1995
__

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai#### Pseudorandom Generators, Measure Theory, and Natural Proofs

__
TR21-076
| 4th June 2021
__

Dmitry Sokolov#### Pseudorandom Generators, Resolution and Heavy Width

Revisions: 1

__
TR10-129
| 16th August 2010
__

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel#### Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds

__
TR21-170
| 25th November 2021
__

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda#### Pseudorandom Self-Reductions for NP-Complete Problems

__
TR18-006
| 10th January 2018
__

Subhash Khot, Dor Minzer, Muli Safra#### Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion

Revisions: 2

__
TR05-022
| 19th February 2005
__

Omer Reingold, Luca Trevisan, Salil Vadhan#### Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

__
TR06-013
| 24th January 2006
__

Luca Trevisan#### Pseudorandomness and Combinatorial Constructions

__
TR14-076
| 27th May 2014
__

Thomas Steinke#### Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs

Revisions: 1

__
TR19-155
| 6th November 2019
__

Rahul Santhanam#### Pseudorandomness and the Minimum Circuit Size Problem

__
TR04-086
| 12th October 2004
__

Ronen Shaltiel, Chris Umans#### Pseudorandomness for Approximate Counting and Sampling

__
TR13-132
| 23rd September 2013
__

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka#### Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

__
TR12-083
| 29th June 2012
__

Thomas Steinke#### Pseudorandomness for Permutation Branching Programs Without the Group Theory

__
TR11-117
| 3rd September 2011
__

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan#### Pseudorandomness for read-once formulas

__
TR13-086
| 13th June 2013
__

Omer Reingold, Thomas Steinke, Salil Vadhan#### Pseudorandomness for Regular Branching Programs via Fourier Analysis

Revisions: 1

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

__
TR12-057
| 7th May 2012
__

Russell Impagliazzo, Raghu Meka, David Zuckerman#### Pseudorandomness from Shrinkage

Revisions: 2

__
TR22-024
| 17th February 2022
__

Louis Golowich, Salil Vadhan#### Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs

Revisions: 1

__
TR16-037
| 15th March 2016
__

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel#### Pseudorandomness when the odds are against you

__
TR03-028
| 28th February 2003
__

Olivier Powell#### PSPACE contains almost complete problems

__
TR07-021
| 5th March 2007
__

Brett Hemenway, Rafail Ostrovsky#### Public Key Encryption Which is Simultaneously a Locally-Decodable Error-Correcting Code

Revisions: 3

__
TR11-118
| 6th September 2011
__

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters#### Public Key Locally Decodable Codes with Short Keys

__
TR13-130
| 17th September 2013
__

Mark Braverman, Ankit Garg#### Public vs private coin in bounded-round information

Revisions: 1

__
TR21-029
| 1st March 2021
__

Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan#### Public-Coin Statistical Zero-Knowledge Batch Verification against Malicious Verifiers

__
TR02-042
| 7th June 2002
__

Dima Grigoriev#### Public-key cryptography and invariant theory

__
TR96-056
| 12th November 1996
__

Oded Goldreich, Shai Halevi#### Public-Key Cryptosystems from Lattice Reduction Problems

__
TR08-100
| 14th November 2008
__

Chris Peikert#### Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem

__
TR22-011
| 25th January 2022
__

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen#### Public-Key Encryption from Continuous LWE

__
TR23-098
| 5th July 2023
__

Andrej Bogdanov, Pravesh Kothari, Alon Rosen#### Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

__
TR12-130
| 3rd October 2012
__

Abuzer Yakaryilmaz#### Public-qubits versus private-coins

__
TR21-139
| 24th September 2021
__

Venkatesan Guruswami, Jonathan Mosheiff#### Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

Revisions: 2

__
TR05-031
| 1st March 2005
__

Carme Alvarez, Joaquim Gabarro, Maria Serna#### Pure Nash equilibria in games with a large number of actions

__
TR01-081
| 8th August 2001
__

Palash Sarkar#### Pushdown Automaton with the Ability to Flip its Stack

Scott Aaronson

In 1955, John Nash sent a remarkable letter to the National Security Agency, in which—seeking to build theoretical foundations for cryptography—he all but formulated what today we call the P=?NP problem, considered one of the great open problems of science. Here I survey the status of this problem in 2017, ... more >>>

Tomas Feder, Carlos Subi

Given a graph $G$, we consider the problem of finding the largest set

of edge-disjoint triangles contained in $G$. We show that even the

simpler case of decomposing the edges of

a sparse split graph $G$ into edge-disjoint triangles

is NP-complete. We show next that the case of a general ...
more >>>

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar

In our problem we are given a set of customers, their positions on the

plane and their demands. Geometrically, directional antenna with

parameters $\alpha,\rho,R$ is a set

of points with radial coordinates $(\theta,r)$ such that

$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of

possible directional ...
more >>>

Gil Cohen, Shahar Samocha

A tree code is an edge-coloring of the complete infinite binary tree such that every two nodes of equal depth have a fraction--bounded away from $0$--of mismatched colors between the corresponding paths to their least common ancestor. Tree codes were introduced in a seminal work by Schulman (STOC 1993) and ... more >>>

Jinyu Huang

Let two linear matroids have the same rank in matroid intersection.

A maximum linear matroid intersection (maximum linear matroid parity

set) is called a basic matroid intersection (basic matroid parity

set), if its size is the rank of the matroid. We present that

enumerating all basic matroid intersections (basic matroid ...
more >>>

Bruce Edward Litow

It is shown that integer coprimality is in NC.

more >>>Marek Karpinski, Yakov Nekrich

This paper presents new results on parallel constructions of the

length-limited prefix-free codes with the minimum redundancy.

We describe an algorithm for the construction of length-limited codes

that works in $O(L)$ time with $n$ processors for $L$ the

maximal codeword length.

We also describe an algorithm for a construction ...
more >>>

Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, Jose' D. P. Rolim

We address the problem of organizing a set $T$ of shared data into

the memory modules of a Distributed Memory Machine (DMM) in order

to minimize memory access conflicts (i.e. memory contention)

during read operations.

Previous solutions for this problem can be found as fundamental ...
more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

Mark Braverman, Subhash Khot, Dor Minzer

We show that the value of the $n$-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

more >>>Anup Rao

In a two player game, a referee asks two cooperating players (who are

not allowed to communicate) questions sampled from some distribution

and decides whether they win or not based on some predicate of the

questions and their answers. The parallel repetition of the game is

the game in which ...
more >>>

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.

Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated ...
more >>>

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification'', and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial ... more >>>

Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik

We settle a number of questions in variants of Winfree's abstract Tile Assembly Model (aTAM), a model of molecular algorithmic self-assembly. In the "hierarchical" aTAM, two assemblies, both consisting of multiple tiles, are allowed to aggregate together, whereas in the "seeded" aTAM, tiles attach one at a time to a ... more >>>

Henning Fernau

We are going to analyze simple search tree algorithms

for Weighted d-Hitting Set. Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) d-Hitting Set.

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander Razborov

A general framework for parameterized proof complexity was introduced by Dantchev, Martin, and Szeider (FOCS'07). In that framework the parameterized version of any proof system is not fpt-bounded for some technical reasons, but we remark that this question becomes much more interesting if we restrict ourselves to those parameterized contradictions ... more >>>

Martin Lück, Arne Meier, Irina Schindler

We present a complete classification of the parameterized complexity of all operator fragments of the satisfiability problem in computation tree logic CTL. The investigated parameterization is temporal depth and pathwidth. Our results show a dichotomy between W[1]-hard and fixed-parameter tractable fragments. The two real operator fragments which are in FPT ... more >>>

Stephan Kreutzer, Anuj Dawar

We show that if $\mathcal C$ is a class of graphs which is

"nowhere dense" then first-order model-checking is

fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ...
more >>>

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

We consider the PermCode problem to decide, given a representation of a permutation group G and a parameter k, whether there is a non-trivial element of G with support at most k. This problem generalizes several problems in the literature. We introduce a new method that allows to reduce the ... more >>>

Jochen Alber, Henning Fernau, Rolf Niedermeier

A parameterized problem is called fixed parameter tractable

if it admits a solving algorithm whose running time on

input instance $(I,k)$ is $f(k) \cdot |I|^\alpha$, where $f$

is an arbitrary function depending only on~$k$. Typically,

$f$ is some exponential function, e.g., $f(k)=c^k$ for ...
more >>>

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>

Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

Marco Cesati, Miriam Di Ianni

We consider the framework of Parameterized Complexity, and we

investigate the issue of which problems do admit efficient fixed

parameter parallel algorithms by introducing two different

degrees of efficiently parallelizable parameterized problems, PNC

and FPP. We sketch both some FPP-algorithms solving natural

parameterized problems and ...
more >>>

Stefan S. Dantchev, Barnaby Martin, Stefan Szeider

We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

Henning Fernau

We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize"

parameterized algorithms.

Kshitij Gajjar, Jaikumar Radhakrishnan

We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ ... more >>>

Meena Mahajan, Venkatesh Raman

In this paper we investigate the parametrized

complexity of the problems MaxSat and MaxCut using the

framework developed by Downey and Fellows.

Let $G$ be an arbitrary graph having $n$ vertices and $m$

edges, and let $f$ be an arbitrary CNF formula with $m$

clauses on $n$ variables. We improve ...
more >>>

Lorenzo Carlucci, Nicola Galesi, Massimo Lauria

We initiate the study of the proof complexity of propositional encoding of (weak cases of) concrete independence results. In particular we study the proof complexity of Paris-Harrington's Large Ramsey Theorem. We prove a conditional lower bound in Resolution and a quasipolynomial upper bound in bounded-depth Frege.

more >>>Anastasiya Chistopolskaya, Vladimir Podolskii

We prove a new lower bound on the parity decision tree complexity $D_{\oplus}(f)$ of a Boolean function $f$. Namely, granularity of the Boolean function $f$ is the smallest $k$ such that all Fourier coefficients of $f$ are integer multiples of $1/2^k$. We show that $D_{\oplus}(f)\geq k+1$.

This lower bound is ... more >>>

Pavel Pudlak, Arnold Beckmann, Neil Thapen

A propositional proof system is \emph{weakly automatizable} if there

is a polynomial time algorithm which separates satisfiable formulas

from formulas which have a short refutation in the system, with

respect to a given length bound. We show that if the resolution

proof system is weakly automatizable, ...
more >>>

Beate Bollig, Philipp Woelfel, Stephan Waack

Branching programs are a well-established computation model

for Boolean functions, especially read-once branching programs

have been studied intensively. Exponential lower bounds for

deterministic and nondeterministic read-once branching programs

are known for a long time. On the other hand, the problem of

proving superpolynomial lower bounds ...
more >>>

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC$^0[\oplus]$ circuits. Razborov (1987) and Smolensky (1987, 1993) showed that Majority requires depth-$d$ AC$^0[\oplus]$ circuits of size $2^{\Omega(n^{1/2(d-1)})}$. By using a divide-and-conquer approach, it is easy to show that Majority can ... more >>>

Mark Braverman, Raghav Kulkarni, Sambuddha Roy

We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the problem to be complete for Logspace when the modulus is 2^k, for constant k. ... more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

The Turing and many-one completeness notions for $\NP$ have been

previously separated under {\em measure}, {\em genericity}, and {\em

bi-immunity} hypotheses on NP. The proofs of all these results rely

on the existence of a language in NP with almost everywhere hardness.

In this paper we separate the same NP-completeness ... more >>>

Dmytro Gavinsky, Pavel Pudlak

We introduce a new concept, which we call partition expanders. The basic idea is to study quantitative properties of graphs in a slightly different way than it is in the standard definition of expanders. While in the definition of expanders it is required that the number of edges between any ... more >>>

Tomas Feder, Carlos Subi

The $H$-matching problem asks to partition the vertices of an input graph $G$

into sets of size $k=|V(H)|$, each of which induces a subgraph of $G$

isomorphic to $H$. The $H$-matching problem has been classified as polynomial

or NP-complete depending on whether $k\leq 2$ or not. We consider a variant

more >>>

Noga Alon, Ilan Newman, Alexander Shen, Gábor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

Magnus Bordewich, Martin Dyer, Marek Karpinski

We give a new method for analysing the mixing time of a Markov chain using

path coupling with stopping times. We apply this approach to two hypergraph

problems. We show that the Glauber dynamics for independent sets in a

hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ...
more >>>

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

We consider strings which are succinctly described. The description

is in terms of straight-line programs in which the constants are

symbols and the only operation is the concatenation. Such

descriptions correspond to the systems of recurrences or to

context-free grammars generating single words. The descriptive ...
more >>>

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

This paper strengthens the low-error PCP characterization of NP, coming

closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for

membership in any NP language can be verified with a constant

number of accesses, and with an error probability exponentially

small in the ...
more >>>

Liron Bronfman, Ron Rothblum

Modern cryptography fundamentally relies on the assumption that the adversary trying to break the scheme is computationally bounded. This assumption lets us construct cryptographic protocols and primitives that are known to be impossible otherwise. In this work we explore the effect of bounding the adversary's power in other information theoretic ... more >>>

Jonathan Ullman, Salil Vadhan

Assuming the existence of one-way functions, we show that there is no

polynomial-time, differentially private algorithm $A$ that takes a database

$D\in (\{0,1\}^d)^n$ and outputs a ``synthetic database'' $\hat{D}$ all of whose two-way

marginals are approximately equal to those of $D$. (A two-way marginal is the fraction

of database rows ...
more >>>

Irit Dinur, Venkatesan Guruswami

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>

Scott Aaronson

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable ... more >>>

Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and ... more >>>

Balagopal Komarath, Jayalal Sarma

We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al.(2011). Proving an exponential lower bound for the size of the non-deterministic thrifty branching programs would separate NL from P under the thrifty hypothesis. In this ... more >>>

Shafi Goldwasser, Ofer Grossman

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That ... more >>>

Marco Cesati

We show that the parameterized problem Perfect Code belongs to W[1].

This result closes an old open question, because it was often

conjectured that Perfect Code could be a natural problem having

complexity degree intermediate between W[1] and W[2]. This result

also shows W[1]-membership of the parameterized problem Weighted

more >>>

Samir Datta, Raghav Kulkarni, Raghunath Tewari

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon

the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space

complexity bounds for some related problems. Summarizing, we show that, constructing:

1. a Perfect Matching in bipartite planar graphs is in ...
more >>>

Jens Groth, Rafail Ostrovsky, Amit Sahai

Non-interactive zero-knowledge (NIZK) systems are

fundamental cryptographic primitives used in many constructions,

including CCA2-secure cryptosystems, digital signatures, and various

cryptographic protocols. What makes them especially attractive, is

that they work equally well in a concurrent setting, which is

notoriously hard for interactive zero-knowledge protocols. However,

while for interactive zero-knowledge we ...
more >>>

Alex Bredariol Grilo, William Slofstra, Henry Yuen

In this work we consider the interplay between multiprover interactive proofs, quantum

entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory,

quantum information and cryptography. In particular, we study the relationship between the

complexity class MIP$^*$ , the set of languages decidable by multiprover interactive ...
more >>>

Alexey Milovanov

This text is a development of a preprint of Ankit Gupta.

We present an approach for devising a deterministic polynomial time whitekbox identity testing (PIT) algorithm for depth-$4$ circuits with bounded top fanin.

This approach is similar to Kayal-Saraf approach for depth-$3$ circuits. Kayal and Saraf based their ...
more >>>

Benny Applebaum, Prashant Nalini Vasudevan

In the *Conditional Disclosure of Secrets* (CDS) problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold $n$-bit inputs $x$ and $y$ respectively, wish to release a common secret $z$ to Carol (who knows both $x$ and $y$) if and only if the input $(x,y)$ satisfies ... more >>>

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

Samir Datta, Gautam Prakriya

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.

The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ...
more >>>

Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf

To compare the complexity of the perfect matching problem for general graphs with that for planar graphs, one might try to come up with a reduction from the perfect matching problem to the planar perfect matching problem.

The obvious way to construct such a reduction is via a {\em planarizing ...
more >>>

Amir Yehudayoff

We prove an essentially sharp $\tilde\Omega(n/k)$ lower bound on the $k$-round distributional complexity of the $k$-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson's $\tilde \Omega(n/k^2)$ lower bound. A key part of the proof is using triangular discrimination instead ... more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>

Ulrich Schöpp, Martin Hofmann

We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the ... more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

The ``analyst's traveling salesman theorem'' of geometric

measure theory characterizes those subsets of Euclidean

space that are contained in curves of finite length.

This result, proven for the plane by Jones (1990) and

extended to higher-dimensional Euclidean spaces by

Okikiolu (1991), says that a bounded set $K$ is contained

more >>>

Venkatesan Guruswami, Patrick Xia

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. Polar coding gives the *first known explicit construction* with rigorous ... more >>>

Martin Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret

We initiate the formal treatment of cryptographic constructions based on the hardness of computing remainders modulo an ideal in multivariate polynomial rings. Of particular interest to us is a class of schemes known as "Polly Cracker." We start by formalising and studying the relation between the ideal remainder problem and ... more >>>

Mark Braverman

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

Pranav Bisht, Nitin Saxena

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>>

MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

We consider the non-uniform multicommodity buy-at-bulk network

design problem. In this problem we are given a graph $G(V,E)$ with

two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost

$r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$)

with each pair $i$ ...
more >>>

Piotr Indyk, David P. Woodruff

A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about the input x other than what can be deduced from f(x). We give the first two-party private approximation of the Euclidean distance ... more >>>

A. Pavan, N. V. Vinodchandran

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine

and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

Alan L. Selman, Samik Sengupta

It is known \cite{BHZ87} that if every language in coNP has a

constant-round interactive proof system, then the polynomial hierarchy

collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that

#SAT, the #P-complete function that outputs the number of satisfying

assignments of a Boolean ...
more >>>

Spyros Kontogiannis, Panagiota Panagopoulou, Paul Spirakis

We focus on the problem of computing an $\epsilon$-Nash equilibrium of a bimatrix game, when $\epsilon$ is an absolute constant.

We present a simple algorithm for computing a $\frac{3}{4}$-Nash equilibrium for any bimatrix game in strongly polynomial time and

we next show how to extend this algorithm so as to ...
more >>>

Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds on the VC

Dimension of general functional basis networks, and prove as an

application, for the first time, the VC Dimension of analog neural

networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$

to ...
more >>>

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

Nicola Galesi, Leszek Kolodziejczyk, Neil Thapen

We show that if a $k$-CNF requires width $w$ to refute in resolution, then it requires space $\sqrt w$ to refute in polynomial calculus, where the space of a polynomial calculus refutation is the number of monomials that must be kept in memory when working through the proof. This is ... more >>>

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving super-logarithmic data structure lower bounds in the static \emph{group model} has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic ... more >>>

Arnab Bhattacharyya

Fix a prime $p$. Given a positive integer $k$, a vector of positive integers ${\bf \Delta} = (\Delta_1, \Delta_2, \dots, \Delta_k)$ and a function $\Gamma: \mathbb{F}_p^k \to \F_p$, we say that a function $P: \mathbb{F}_p^n \to \mathbb{F}_p$ is $(k,{\bf \Delta},\Gamma)$-structured if there exist polynomials $P_1, P_2, \dots, P_k:\mathbb{F}_p^n \to \mathbb{F}_p$ ... more >>>

Bruce Edward Litow

The elimination

problem is classical:

implicitly express one of the variables occurring in a finite

system of polynomial equations as an algebraic function of a

designated subset of the remaining variables. Solutions to this

problem by resultants, or more comprehensively by

use of Gr\"{o}bner basis methods are available. In this ...
more >>>

Neeraj Kayal, Nitin Saxena

We study the identity testing problem for depth $3$ arithmetic circuits ($\Sigma\Pi\Sigma$ circuits). We give the first deterministic polynomial time identity test for $\Sigma\Pi\Sigma$ circuits with bounded top fanin. We also show that the {\em rank} of a minimal and simple $\Sigma\Pi\Sigma$ circuit with bounded top fanin, computing zero, can ... more >>>

Dieter van Melkebeek, Andrew Morgan

We introduce a hitting set generator for Polynomial Identity Testing

based on evaluations of low-degree univariate rational functions at

abscissas associated with the variables. Despite the univariate

nature, we establish an equivalence up to rescaling with a generator

introduced by Shpilka and Volkovich, which has a similar structure but

uses ...
more >>>

Hubie Chen

Representations of boolean functions as polynomials (over rings) have

been used to establish lower bounds in complexity theory. Such

representations were used to great effect by Smolensky, who

established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)

by representing AC^0[MOD p] functions as low-degree multilinear

polynomials over ...
more >>>

Kristoffer Arnsfelt Hansen, Vladimir Podolskii

We study the complexity of computing Boolean functions on general

Boolean domains by polynomial threshold functions (PTFs). A typical

example of a general Boolean domain is $\{1,2\}^n$. We are mainly

interested in the length (the number of monomials) of PTFs, with

their degree and weight being of secondary interest. We ...
more >>>

Leonid Gurvits

We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.

Our main result is a poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and

with better rates if the affine dimensions of most of the sets $K_i$ are small.\\

Our approach is ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski

We give the first polynomial time approximability characterization

of dense weighted instances of MAX-CUT, and some other dense

weighted NP-hard problems in terms of their empirical weight

distributions. This gives also the first almost sharp

characterization of inapproximability of unweighted 0,1

MAX-BISECTION instances ...
more >>>

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

It is known that large fragments of the class of dense

Minimum Constraint Satisfaction (MIN-CSP) problems do not have

polynomial time approximation schemes (PTASs) contrary to their

Maximum Constraint Satisfaction analogs. In this paper we prove,

somewhat surprisingly, that the minimum satisfaction of dense

instances of kSAT-formulas, ...
more >>>

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

We give polynomial time approximation schemes for the problem

of partitioning an input set of n points into a fixed number

k of clusters so as to minimize the sum over all clusters of

the total pairwise distances in a cluster. Our algorithms work

for arbitrary metric spaces as well ...
more >>>

Marek Karpinski

We survey recent results on the existence of polynomial time

approximation schemes for some dense instances of NP-hard

optimization problems. We indicate further some inherent limits

for existence of such schemes for some other dense instances of

the optimization problems.

Harumichi Nishimura, Tomoyuki Yamakami

Advice is supplementary information that enhances the computational

power of an underlying computation. This paper focuses on advice that

is given in the form of a pure quantum state. The notion of advised

quantum computation has a direct connection to non-uniform quantum

circuits and tally languages. The paper examines the ...
more >>>

Noga Alon, Alan Frieze, Dominic Welsh

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$

encodes numerous interesting combinatorial quantities associated

with the graph. Its evaluation in various points in the $(x,y)$

plane give the number of spanning forests of the graph, the number

of its strongly connected orientations, the number of its proper

$k$-colorings, the (all ...
more >>>

Tomoyuki Yamakami

This paper studies distributions which

can be ``approximated'' by sampling algorithms in time polynomial in

the length of their outputs. First, it is known that if

polynomial-time samplable distributions are polynomial-time

computable, then NP collapses to P. This paper shows by a simple

...
more >>>

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

Parikshit Gopalan, Adam Klivans, Raghu Meka

We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with total weight W and accuracy parameter eps, our algorithm produces a (1 + eps)-multiplicative approximation in time poly(n,log W,1/eps). We also give algorithms ... more >>>

Prabhu Manyem

In Descriptive Complexity, there is a vast amount of literature on

decision problems, and their classes such as \textbf{P, NP, L and NL}. ~

However, research on the descriptive complexity of optimisation problems

has been limited. In a previous paper [Man], we characterised

the optimisation versions of \textbf{P} via expressions ...
more >>>

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.

... more >>>John Hitchcock, Adewale Sekoni, Hadi Shafei

Bennett and Gill (1981) showed that P^A != NP^A != coNP^A for a random

oracle A, with probability 1. We investigate whether this result

extends to individual polynomial-time random oracles. We consider two

notions of random oracles: p-random oracles in the sense of

martingales and resource-bounded measure (Lutz, 1992; Ambos-Spies ...
more >>>

Herbert Fleischner, Stefan Szeider

Irit Dinur, Prahladh Harsha, Guy Kindler

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

Andris Ambainis

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials.

Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon<1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'<1/2$.

This result holds for two ...
more >>>

Avi Wigderson, Amir Yehudayoff

We study several problems in which an {\em unknown} distribution over an {\em unknown} population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution $p$ over a population $V \subseteq \{0,1\}^n$. A ... more >>>

Srinivasan Arunachalam, Penghui Yao

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>

Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors).

At the heart of our proof is a new ... more >>>

Alex Lombardi, Fermi Ma, Nicholas Spooner

A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problematic in the context of zero-knowledge simulation, where preserving the adversary's state is essential.

In this work, we develop new techniques for ...
more >>>

Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

We consider sets of strings with high Kolmogorov complexity, mainly

in resource-bounded settings but also in the traditional

recursion-theoretic sense. We present efficient reductions, showing

that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure

K, ...
more >>>

Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma

In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of ... more >>>

Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

We study EP, the subclass of NP consisting of those

languages accepted by NP machines that when they accept always have a

number of accepting paths that is a power of two. We show that the

negation equivalence problem for OBDDs (ordered binary decision

diagrams) ...
more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Romain Bourneuf, Lukáš Folwarczný, Pavel Hubacek, Alon Rosen, Nikolaj Schwartzbach

Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on monochromatic subgraphs and the Erdos-Rado sunflower lemma. Implicit versions of the corresponding total search problems are known to be PWPP-hard; here "implicit" means that the collection is represented ... more >>>

Dominik Scheder

We show that for $k \geq 5$, the PPSZ algorithm for $k$-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every $k\geq 5$, there is a strictly increasing function $f: [0,1] \rightarrow \mathbb{R}$ with $f(0) = 0$ that has the ... more >>>

Dominik Scheder

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being ... more >>>

Dominik Scheder

We study the success probability of the PPSZ algorithm on $(d,k)$-CSP formulas. We greatly simplify the analysis of Hertli, Hurbain, Millius, Moser, Szedlak, and myself for the notoriously difficult case that the input formula has more than one satisfying assignment.

more >>>Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.

The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ...
more >>>

Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang

In this work we consider the following problem: in a Multi-Prover environment, how close can we get to prove the validity of an NP statement in Zero-Knowledge ? We exhibit a set of two novel Zero-Knowledge protocols for the 3-COLorability problem that use two (local) provers or three (entangled) provers ... more >>>

Alexander Smal, Navid Talebanfard

Let $X$ be a random variable distributed over $n$-bit strings with $H(X) \ge n - k$, where $k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around $n/k$ ... more >>>

Or Meir, Avi Wigderson

Consider a random sequence of $n$ bits that has entropy at least $n-k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that ... more >>>

Mikhail V. Vyugin, Vladimir Vyugin

A new notion of predictive complexity and corresponding amount of

information are considered.

Predictive complexity is a generalization of Kolmogorov complexity

which bounds the ability of any algorithm to predict elements of

a sequence of outcomes. We consider predictive complexity for a wide class

of bounded loss functions which ...
more >>>

Nadia Creignou, Phokion G. Kolaitis, Bruno Zanuttini

We introduce the notion of a plain basis for a co-clone in Post's lattice. Such a basis is a set of relations B such that every constraint C over a relation in the co-clone is logically equivalent to a conjunction of equalities and constraints over B and the same variables ... more >>>

William Hoza, Adam Klivans

We introduce the concept of a randomness steward, a tool for saving random bits when executing a randomized estimation algorithm $\mathrm{Est}$ on many adaptively chosen inputs. For each execution, the chosen input to $\mathrm{Est}$ remains hidden from the steward, but the steward chooses the randomness of $\mathrm{Est}$ and, crucially, is ... more >>>

Tobias Polzin, Siavash Vahdati Daneshmand

We study several old and new algorithms for computing lower

and upper bounds for the Steiner problem in networks using dual-ascent

and primal-dual strategies. These strategies have been proven to be

very useful for the algorithmic treatment of the Steiner problem. We

show that none of the known algorithms ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study private computations in information-theoretical settings on

networks that are not 2-connected. Non-2-connected networks are

``non-private'' in the sense that most functions cannot privately be

computed on such networks. We relax the notion of privacy by

introducing lossy private protocols, which generalize private

protocols. We measure the information each ...
more >>>

Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Many approximation algorithms have been presented in the last decades

for hard search problems. The focus of this paper is on cryptographic

applications, where it is desired to design algorithms which do not

leak unnecessary information. Specifically, we are interested in

private approximation algorithms -- efficient algorithms ...
more >>>

Markus Bläser, Andreas Jakoby, Maciej Liskiewicz, Bodo Manthey

We study the role of connectivity of communication networks in private

computations under information theoretic settings. It will be shown that

some functions can be computed by private protocols even if the

underlying network is 1-connected but not 2-connected. Then we give a

complete characterisation of non-degenerate functions that can ...
more >>>

Sophie Laplante, Richard Lassaigne, Frederic Magniez, Sylvain Peyronnet, Michel de Rougemont

In model checking, program correctness on all inputs is verified

by considering the transition system underlying a given program.

In practice, the system can be intractably large.

In property testing, a property of a single input is verified

by looking at a small subset of that input.

We ...
more >>>

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

Greg Kuperberg, Shachar Lovett, Ron Peled

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Oliveira

Understanding the relationship between the worst-case and average-case complexities of $\mathrm{NP}$ and of other subclasses of $\mathrm{PH}$ is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the ... more >>>

Dean Doron, Francois Le Gall, Amnon Ta-Shma

A recent series of breakthroughs initiated by Spielman and Teng culminated in the construction of nearly linear time Laplacian solvers, approximating the solution of a linear system $L x=b$, where $L$ is the normalized Laplacian of an undirected graph. In this paper we study the space complexity of the problem.

more >>>

Rustam Mubarakzjanov

Ordered binary decision diagrams (OBDDs) are well established tools to

represent Boolean functions. There are a lot of results concerning

different types of generalizations of OBDDs. The same time, the power

of the most general form of OBDD, namely probabilistic (without bounded

error) OBDDs, is not studied enough. In ...
more >>>

Oded Goldreich

Various types of probabilistic proof systems have played

a central role in the development of computer science in the last decade.

In this exposition, we concentrate on three such proof systems ---

interactive proofs, zero-knowledge proofs,

and probabilistic checkable proofs --- stressing the essential

role of randomness in each ...
more >>>

eran gat , shafi goldwasser

In this paper we introduce a new type of probabilistic search algorithm, which we call the

{\it Bellagio} algorithm: a probabilistic algorithm which is guaranteed to run in expected polynomial time,

and to produce a correct and {\it unique} solution with high probability.

We argue the applicability of such algorithms ...
more >>>

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

We define and examine several probabilistic operators ranging over sets

(i.e., operators of type 2), among them the formerly studied

ALMOST-operator. We compare their power and prove that they all coincide

for a wide variety of classes. As a consequence, we characterize the

ALMOST-operator which ranges over infinite objects ...
more >>>

Marius Zimand

We present a weaker variant of the PCP Theorem that admits a

significantly easier proof. In this

variant the prover only has $n^t$ time to compute each

bit of his answer, for an arbitray but fixed constant

$t$, in contrast to

being all powerful. We show that

3SAT ...
more >>>

Madhu Sudan, Luca Trevisan

The error probability of Probabilistically Checkable Proof (PCP)

systems can be made exponentially small in the number of queries

by using sequential repetition. In this paper we are interested

in determining the precise rate at which the error goes down in

an optimal protocol, and we make substantial progress toward ...
more >>>

Michal Parnas, Dana Ron, Alex Samorodnitsky

We consider the problem of determining whether a given

function f : {0,1}^n -> {0,1} belongs to a certain class

of Boolean functions F or whether it is far from the class.

More precisely, given query access to the function f and given

a distance parameter epsilon, we would ...
more >>>

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is ... more >>>

Nitin Saxena

Polynomial identity testing (PIT) is the problem of checking whether a given

arithmetic circuit is the zero circuit. PIT ranks as one of the most important

open problems in the intersection of algebra and computational complexity. In the last

few years, there has been an impressive progress on this ...
more >>>

Nitin Saxena

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.

more >>>Joshua Brakensiek, Venkatesan Guruswami

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>>

Lance Fortnow, Rahul Santhanam, Luca Trevisan

We show that for any constant a, ZPP/b(n) strictly contains

ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques

are very general and give the same hierarchy for all the common

promise time classes including RTIME, NTIME \cap coNTIME, UTIME,

MATIME, AMTIME and BQTIME.

We show a ... more >>>

Peter Dixon, A. Pavan, N. V. Vinodchandran

The Acceptance Probability Estimation Problem (APEP) is to additively approximate the acceptance probability of a Boolean circuit. This problem admits a probabilistic approximation scheme. A central question is whether we can design a pseudodeterministic approximation algorithm for this problem: a probabilistic polynomial-time algorithm that outputs a canonical approximation with high ... more >>>

Michael Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the ...
more >>>

Dmitry Itsykson, Artur Riazanov

A canonical communication problem ${\rm Search}(\phi)$ is defined for every unsatisfiable CNF $\phi$: an assignment to the variables of $\phi$ is distributed among the communicating parties, they are to find a clause of $\phi$ falsified by this assignment. Lower bounds on the randomized $k$-party communication complexity of ${\rm Search}(\phi)$ in ... more >>>

Olaf Beyersdorff, Leroy Chew, Mikolas Janota

Proof systems for quantified Boolean formulas (QBFs) provide a theoretical underpinning for the performance of important

QBF solvers. However, the proof complexity of these proof systems is currently not well understood and in particular

lower bound techniques are missing. In this paper we exhibit a new and elegant proof technique ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn

For quantified Boolean formulas (QBF), a resolution system with a symmetry rule was recently introduced by Kauers and Seidl (Inf. Process. Lett. 2018). In this system, many formulas hard for QBF resolution admit short proofs.

Kauers and Seidl apply the symmetry rule on symmetries of the original formula. Here we ... more >>>

Leroy Chew

The proof complexity of Quantified Boolean Formulas (QBF) relates to both QBF solving and OBF certification. One method to p-simulate a QBF proof system is by formalising the soundness of its strategy extraction in propositional logic. In this work we illustrate how to use extended QBF Frege to simulate LD-Q(Drrs)-Res, ... more >>>

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined

propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ...
more >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

We show that every language in NP has a probablistic verifier

that checks membership proofs for it using

logarithmic number of random bits and by examining a

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Boaz Barak

In this survey, I discuss the general question of what evidence can we use to predict the answer for open questions in computational complexity, as well as the concrete evidence currently known for two conjectures: Khot's Unique Games Conjecture and Feige's Random 3SAT Hypothesis.

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

Alessandro Chiesa, Tom Gur

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

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

In certain applications there may only be positive samples available to

to learn concepts of a class of interest,

and this has to be done properly, i.e. the

hypothesis space has to coincide with the concept class,

and without false positives, i.e. the hypothesis always has be a subset ...
more >>>

Shay Moran, Amir Yehudayoff

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.

In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ...
more >>>

Avishay Tal

For Boolean functions $f:\{0,1\}^n \to \{0,1\}$ and $g:\{0,1\}^m \to \{0,1\}$, the function composition of $f$ and $g$ denoted by $f\circ g : \{0,1\}^{nm} \to \{0,1\}$ is the value of $f$ on $n$ inputs, each of them is the calculation of $g$ on a distinct set of $m$ Boolean variables. Motivated ... more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such ...
more >>>

Eldar Fischer, Frederic Magniez, Michel de Rougemont

Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>>

Oded Goldreich, Dana Ron

In this paper, we consider the question of determining whether

a function $f$ has property $P$ or is $\e$-far from any

function with property $P$.

The property testing algorithm is given a sample of the value

of $f$ on instances drawn according to some distribution.

In some cases,

more >>>

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Eric Blais, Joshua Brody, Kevin Matulef

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>

Sourav Chakraborty, Laszlo Babai

For a permutation group $G$ acting on the set $\Omega$

we say that two strings $x,y\,:\,\Omega\to\boole$

are {\em $G$-isomorphic} if they are equivalent under

the action of $G$, \ie, if for some $\pi\in G$ we have

$x(i^{\pi})=y(i)$ for all $i\in\Omega$.

Cyclic Shift, Graph Isomorphism ...
more >>>

Peyman Afshani, Kevin Matulef, Bryan Wilkinson

We define a new property testing model for algorithms that do not have arbitrary query access to the input, but must instead traverse it in a manner that respects the underlying data structure in which it is stored. In particular, we consider the case when the underlying data structure is ... more >>>

Kashyap Dixit, Deeparnab Chakrabarty, Madhav Jha, C. Seshadhri

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the {\em uniform} distribution on the domain. ... more >>>

Victor Chen, Madhu Sudan, Ning Xie

Given two testable properties $\mathcal{P}_{1}$ and $\mathcal{P}_{2}$, under what conditions are the union, intersection or set-difference

of these two properties also testable?

We initiate a systematic study of these basic set-theoretic operations in the context of property

testing. As an application, we give a conceptually different proof that linearity is ...
more >>>

Guy Kindler

The first part of this thesis strengthens the low-error PCP

characterization of NP, coming closer to the upper limit of the

conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over

$n$ variables can be tested for the property of depending ...
more >>>

Paul Beame

Proof complexity, the study of the lengths of proofs in

propositional logic, is an area of study that is fundamentally connected

both to major open questions of computational complexity theory and

to practical properties of automated theorem provers. In the last

decade, there have been a number of significant advances ...
more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Single-hop radio networks (SHRN) are a well studied abstraction of communication over a wireless channel. In this model, in every round, each of the $n$ participating parties may decide to broadcast a message to all the others, potentially causing collisions. We consider the SHRN model in the presence of stochastic ... more >>>

Tom Gur, Wilfred Salmon, Sergii Strelchuk

We revisit the problem of characterising the complexity of Quantum PAC learning, as introduced by Bshouty and Jackson [SIAM J. Comput.

1998, 28, 1136–1153]. Several quantum advantages have been demonstrated in this setting, however, none are generic: they apply to particular concept classes and typically only work when the distribution ...
more >>>

Noga Ron-Zewi, Ron Rothblum

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing ... more >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter, defined by a composition mechanism

for vertex-labeled graphs, which measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic, that includes NP-hard

problems) can be solved efficiently for graphs of certified small

clique-width. It ...
more >>>

Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider

Clique-width is a graph parameter that measures in a certain sense the

complexity of a graph. Hard graph problems (e.g., problems

expressible in Monadic Second Order Logic with second-order

quantification on vertex sets, that includes NP-hard problems) can be

solved efficiently for graphs of certified small clique-width. It is

widely ...
more >>>

Roei Tell

We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without ... more >>>

Yuval Filmus, Edward Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals

Hitting formulas have been studied in many different contexts at least since [Iwama 1989]. A hitting formula is a set of Boolean clauses such that any two of the clauses cannot be simultaneously falsified. [Peitl and Szeider 2022] conjectured that the family of unsatisfiable hitting formulas should contain the hardest ... more >>>

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are $\delta$-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are $\delta$-close to the property. In particular, no set ... more >>>

Oded Goldreich, Tali Kaufman

We present a general notion of properties that

are characterized by local conditions that are invariant

under a sufficiently rich class of symmetries.

Our framework generalizes two popular models of

testing graph properties as well as the algebraic

invariances studied by Kaufman and Sudan (STOC'08).

We show that, in the ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser

[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed

output with high probability. We explore pseudo-determinism in the settings of learning and ap-

proximation. Our goal is to simulate known randomized algorithms in these settings ...
more >>>

Shafi Goldwasser, Ofer Grossman, Dhiraj Holden

We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where

the verifier is guaranteed with high probability to output the same output on different executions.

As in the case with classical interactive proofs,

the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David Woodruff

A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, $\ell_2$ approximation, finding a nonzero entry in a vector (for turnstile algorithms) ... more >>>

Itai Benjamini, Oded Goldreich

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the ... more >>>

Ilario Bonacina, Nicola Galesi

We devise a new combinatorial characterization for proving space lower bounds in algebraic systems like Polynomial Calculus (Pc) and Polynomial Calculus with Resolution (Pcr). Our method can be thought as a Spoiler-Duplicator game, which is capturing boolean reasoning on polynomials instead that clauses as in the case of Resolution. Hence, ... more >>>

Moni Naor, Omer Reingold, Alon Rosen

Factoring integers is the most established problem on which

cryptographic primitives are based. This work presents an efficient

construction of {\em pseudorandom functions} whose security is based

on the intractability of factoring. In particular, we are able to

construct efficient length-preserving pseudorandom functions where

each evaluation requires only a ...
more >>>

Eric Binnendyk

Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate ... more >>>

Venkatesan Guruswami, Vinayak Kumar

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of $BPTIME$: proving hierarchy theorems and showing the existence of complete problems. Our main contributions can be summarised as follows.

1. A new pseudorandom generator and its consequences: We build on techniques developed to ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

Edward Pyne, Salil Vadhan

A recent paper of Braverman, Cohen, and Garg (STOC 2018) introduced the concept of a pseudorandom pseudodistribution generator (PRPG), which amounts to a pseudorandom generator (PRG) whose outputs are accompanied with real coefficients that scale the acceptance probabilities of any potential distinguisher. They gave an explicit construction of PRPGs for ... more >>>

Emanuele Viola

We exhibit a pseudorandom generator with nearly quadratic stretch for randomized Turing machines, which have a one-way random tape and a two-way work tape. This is the first generator for this model. Its stretch is essentially the best possible given current lower bounds. We use the generator to prove a ... more >>>

Emanuele Viola

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>

Rohit Gurjar, Ben Lee Volk

We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $\tilde{O}(n^{1-1/2^{k-1}})$ (for the ... more >>>

Andrej Bogdanov, Emanuele Viola

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:

\begin{enumerate}

\item a ...
more >>>

Xin Li

The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in the following five seemingly different topics: seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey ... more >>>

Andrej Bogdanov, Alon Rosen

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds.

In ... more >>>

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka

In this paper we give the first construction of a pseudorandom generator, with seed length $O(\log n)$, for $\mathrm{CC}_0[p]$, the class of constant-depth circuits with unbounded fan-in $\mathrm{MOD}_p$ gates, for some prime $p$. More accurately, the seed length of our generator is $O(\log n)$ for any constant error $\epsilon>0$. In ... more >>>

Thomas Watson

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

We construct pseudorandom generators for combinatorial shapes, which substantially generalize combinatorial rectangles, small-bias spaces, 0/1 halfspaces, and 0/1 modular sums. A function $f:[m]^n \rightarrow \{0,1\}^n$ is an $(m,n)$-combinatorial shape if there exist sets $A_1,\ldots,A_n \subseteq [m]$ and a symmetric function $h:\{0,1\}^n \rightarrow \{0,1\}$ such that $f(x_1,\ldots,x_n) = h(1_{A_1} (x_1),\ldots,1_{A_n}(x_n))$. Our ... more >>>

Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak

We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement ... more >>>

Gil Cohen, Amnon Ta-Shma

Constructing pseudorandom generators for low degree polynomials has received a considerable attention in the past decade. Viola [CC 2009], following an exciting line of research, constructed a pseudorandom generator for degree d polynomials in n variables, over any prime field. The seed length used is $O(d \log{n} + d 2^d)$, ... more >>>

Pooya Hatami, Avishay Tal

A Boolean function is said to have maximal sensitivity $s$ if $s$ is the largest number of Hamming neighbors of a point which differ from it in function value. We construct a pseudorandom generator with seed-length $2^{O(\sqrt{s})} \cdot \log(n)$ that fools Boolean functions on $n$ variables with maximal sensitivity at ... more >>>

Michael Forbes, Zander Kelley

A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom generators (PRGs) that fool polynomial-size read-once (oblivious) branching programs (roBPs). Starting with the work of Nisan, pseudorandom generators with seed-length $O(\log^2 n)$ were constructed. Unfortunately, ... more >>>

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.

A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.

For every width $d$ and length $n$,

our pseudorandom generator uses a seed of length $O((\log d + \log\log n ...
more >>>

William Hoza, Edward Pyne, Salil Vadhan

We prove that the Impagliazzo-Nisan-Wigderson (STOC 1994) pseudorandom generator (PRG) fools ordered (read-once) permutation branching programs of unbounded width with a seed length of $\widetilde{O}(\log d + \log n \cdot \log(1/\varepsilon))$, assuming the program has only one accepting vertex in the final layer. Here, $n$ is the length of the ... more >>>

Raghu Meka, Omer Reingold, Avishay Tal

We construct pseudorandom generators of seed length $\tilde{O}(\log(n)\cdot \log(1/\epsilon))$ that $\epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $\tilde{O}(\log(n) \cdot \mathrm{poly}(1/\epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal

A recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design ... more >>>

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

We call a pseudorandom generator $G_n:\{0,1\}^n\to \{0,1\}^m$ {\em

hard} for a propositional proof system $P$ if $P$ can not efficiently

prove the (properly encoded) statement $G_n(x_1,\ldots,x_n)\neq b$ for

{\em any} string $b\in\{0,1\}^m$. We consider a variety of

``combinatorial'' pseudorandom generators inspired by the

Nisan-Wigderson generator on the one hand, and ...
more >>>

Benny Applebaum

We continue the study of pseudorandom generators (PRG) $G:\{0,1\}^n \rightarrow \{0,1\}^m$ in NC0. While it is known that such generators are likely to exist for the case of small sub-linear stretch $m=n+n^{1-\epsilon}$, it remains unclear whether achieving larger stretch such as $m=2n$ or even $m=n+n^2$ is possible. The existence of ... more >>>

Madhu Sudan, Luca Trevisan, Salil Vadhan

Impagliazzo and Wigderson have recently shown that

if there exists a decision problem solvable in time $2^{O(n)}$

and having circuit complexity $2^{\Omega(n)}$

(for all but finitely many $n$) then $\p=\bpp$. This result

is a culmination of a series of works showing

connections between the existence of hard predicates

and ...
more >>>

Kenneth W. Regan, D. Sivakumar, Jin-Yi Cai

This paper proves that if strong pseudorandom number generators or

one-way functions exist, then the class of languages that have

polynomial-sized circuits is not small within exponential

time, in terms of the resource-bounded measure theory of Lutz.

More precisely, if for some \epsilon > 0 there exist nonuniformly

2^{n^{\epsilon}}-hard ...
more >>>

Dmitry Sokolov

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson \cite{ABRW04} we call a pseudorandom generator $\mathrm{PRG}\colon \{0, 1\}^n \to \{0, 1\}^m$ hard for for a propositional proof system $\mathrm{P}$ if $\mathrm{P}$ cannot efficiently prove the (properly encoded) statement $b \notin \mathrm{Im}(\mathrm{PRG})$ for any string $b \in \{0, 1\}^m$.

In \cite{ABRW04} authors ... more >>>

Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of "typically-correct" deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways.

First, we ... more >>>

Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda

A language $L$ is random-self-reducible if deciding membership in $L$ can be reduced (in polynomial time) to deciding membership in $L$ for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete ... more >>>

Subhash Khot, Dor Minzer, Muli Safra

We prove that pseudorandom sets in Grassmann graph have near-perfect expansion as hypothesized in [DKKMS-2]. This completes

the proof of the $2$-to-$2$ Games Conjecture (albeit with imperfect completeness) as proposed in [KMS, DKKMS-1], along with a

contribution from [BKT].

The Grassmann graph $Gr_{global}$ contains induced subgraphs $Gr_{local}$ that are themselves ... more >>>

Omer Reingold, Luca Trevisan, Salil Vadhan

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

Luca Trevisan

In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of objects with such properties are often very difficult, or unknown. In computer science,

probabilistic algorithms are sometimes simpler and more efficient

than the best known ...
more >>>

Thomas Steinke

We present an explicit pseudorandom generator for oblivious, read-once, width-$3$ branching programs, which can read their input bits in any order. The generator has seed length $\tilde{O}( \log^3 n ).$ The previously best known seed length for this model is $n^{1/2+o(1)}$ due to Impagliazzo, Meka, and Zuckerman (FOCS '12). Our ... more >>>

Rahul Santhanam

We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[$s$]), which asks whether a Boolean function on $n$ bits specified by its truth table has circuits of size $s(n)$.

1. (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for ... more >>>

Ronen Shaltiel, Chris Umans

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>

Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>

Thomas Steinke

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. ... more >>>

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

Omer Reingold, Thomas Steinke, Salil Vadhan

We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is $O(\log^2 n)$, where $n$ is the length of the branching program. The previous best seed length known for this model was $n^{1/2+o(1)}$, ... more >>>

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>

Russell Impagliazzo, Raghu Meka, David Zuckerman

One powerful theme in complexity theory and pseudorandomness in the past few decades has been the use of lower bounds to give pseudorandom generators (PRGs). However, the general results using this hardness vs. randomness paradigm suffer a quantitative loss in parameters, and hence do not give nontrivial implications for models ... more >>>

Louis Golowich, Salil Vadhan

We study the pseudorandomness of random walks on expander graphs against tests computed by symmetric functions and permutation branching programs. These questions are motivated by applications of expander walks in the coding theory and derandomization literatures. We show that expander walks fool symmetric functions up to a $O(\lambda)$ error in ... more >>>

Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then

every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ...
more >>>

Olivier Powell

An almost complete set A for a complexity class C is a language of C which is not complete, but that has the property that ``many'' languages of C reduce to A, where the term ``many'' is used in reference to Lutz's resource bounded measure (rbm). The question of the ... more >>>

Brett Hemenway, Rafail Ostrovsky

In this paper, we introduce the notion of a Public-Key Encryption (PKE) Scheme that is also a Locally-Decodable Error-Correcting Code.

In particular, our construction simultaneously satisfies all of the following properties:

\begin{itemize}

\item

Our Public-Key Encryption is semantically secure under a certain number-theoretic hardness assumption

...
more >>>

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

This work considers locally decodable codes in the computationally bounded channel model. The computationally bounded channel model, introduced by Lipton in 1994, views the channel as an adversary which is restricted to polynomial-time computation. Assuming the existence of IND-CPA secure public-key encryption, we present a construction of public-key locally decodable ... more >>>

Mark Braverman, Ankit Garg

We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We show that if using private randomness a message can be transmitted while revealing $I$ bits of information, the transmission can be ... more >>>

Inbar Kaslasi, Ron Rothblum, Prashant Nalini Vasudevan

Suppose that a problem $\Pi$ has a statistical zero-knowledge (SZK) proof with communication complexity $m$. The question of batch verification for SZK asks whether one can prove that $k$ instances $x_1,\ldots,x_k$ all belong to $\Pi$ with a statistical zero-knowledge proof whose communication complexity is better than $k \cdot m$ (which ... more >>>

Dima Grigoriev

Public-key crypto

Contact: dima@maths.univ-rennes1.fr

Author: Dima Grigoriev

Title: Public-key cryptography and invariant theory

Abstract: Public-key cryptosystems are suggested based on invariants of group

representations

Oded Goldreich, Shai Halevi

We present a new proposal for a trapdoor one-way function,

from which we derive public-key encryption and digital

signatures. The security of the new construction is based

on the conjectured computational difficulty of lattice-reduction

problems, providing a possible alternative to existing

more >>>

Chris Peikert

We construct public-key cryptosystems that are secure assuming the

\emph{worst-case} hardness of approximating the length of a shortest

nonzero vector in an $n$-dimensional lattice to within a small

$\poly(n)$ factor. Prior cryptosystems with worst-case connections

were based either on the shortest vector problem for a \emph{special

class} of lattices ...
more >>>

Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen

The continuous learning with errors (CLWE) problem was recently introduced by Bruna

et al. (STOC 2021). They showed that its hardness implies infeasibility of learning Gaussian

mixture models, while its tractability implies efficient Discrete Gaussian Sampling and thus

asymptotic improvements in worst-case lattice algorithms. No reduction between CLWE and

LWE ...
more >>>

Andrej Bogdanov, Pravesh Kothari, Alon Rosen

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics.

We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis ... more >>>

Abuzer Yakaryilmaz

We introduce a new public quantum interactive proof system, namely qAM, by augmenting the verifier with a fixed-size quantum register in Arthur-Merlin game. We focus on space-bounded verifiers, and compare our new public system with private-coin interactive proof (IP) system in the same space bounds. We show that qAM systems ... more >>>

Venkatesan Guruswami, Jonathan Mosheiff

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

Carme Alvarez, Joaquim Gabarro, Maria Serna

We study the computational complexity of deciding the existence of a

Pure Nash Equilibrium in multi-player strategic games.

We address two fundamental questions: how can we represent a game?, and

how can we represent a game with polynomial pay-off functions?

Our results show that the computational complexity of

deciding ...
more >>>

Palash Sarkar

We introduce the idea of pushdown automata with the ability to flip

its stack. By bounding the number of times the stack can be flipped

we obtain a hierarchy of language classes from the context free

languages to the recursively enumerable languages. We show that each

class in ...
more >>>