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

**N**

__
TR14-118
| 9th September 2014
__

Albert Atserias, Massimo Lauria, Jakob Nordström#### Narrow Proofs May Be Maximally Long

__
TR05-066
| 4th June 2005
__

Jakob Nordström#### Narrow Proofs May Be Spacious: Separating Space and Width in Resolution

Revisions: 2
,
Comments: 1

__
TR06-005
| 13th December 2005
__

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg#### Nash Equilibria in Graphical Games on Trees Revisited

__
TR94-010
| 12th December 1994
__

Alexander Razborov, Steven Rudich#### Natural Proofs

__
TR10-196
| 8th December 2010
__

Bin Fu#### NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets

__
TR19-126
| 19th September 2019
__

Irit Dinur, Roy Meshulam#### Near Coverings and Cosystolic Expansion -- an example of topological property testing

__
TR18-144
| 18th August 2018
__

Mert Saglam#### Near log-convexity of measured heat in (discrete) time and consequences

__
TR05-001
| 1st January 2005
__

Mario Szegedy#### Near optimality of the priority sampling procedure

__
TR03-001
| 8th January 2003
__

Vince Grolmusz#### Near Quadratic Matrix Multiplication Modulo Composites

Comments: 1

__
TR18-132
| 17th July 2018
__

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse#### Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

Revisions: 2

__
TR15-081
| 12th May 2015
__

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette#### Near-optimal bounds on bounded-round quantum communication complexity of disjointness

__
TR22-150
| 7th November 2022
__

Aaron (Louie) Putterman, Edward Pyne#### Near-Optimal Derandomization of Medium-Width Branching Programs

__
TR09-133
| 9th December 2009
__

Anindya De, Thomas Vidick#### Near-optimal extractors against quantum storage

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR16-135
| 31st August 2016
__

Christoph Berkholz, Jakob Nordström#### Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps

__
TR19-003
| 2nd January 2019
__

Alexander A. Sherstov, Pei Wu#### Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0

__
TR18-183
| 5th November 2018
__

Dean Doron, Pooya Hatami, William Hoza#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

__
TR00-005
| 17th January 2000
__

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson#### Near-Optimal Separation of Treelike and General Resolution

__
TR23-017
| 21st February 2023
__

Deepanshu Kush, Shubhangi Saraf#### Near-Optimal Set-Multilinear Formula Lower Bounds

__
TR18-065
| 8th April 2018
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends

Revisions: 1

__
TR15-076
| 28th April 2015
__

Mahdi Cheraghchi, Piotr Indyk#### Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

__
TR15-155
| 22nd September 2015
__

Venkatesan Guruswami, Euiwoong Lee#### Nearly Optimal NP-Hardness of Unique Coverage

__
TR19-099
| 29th July 2019
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

__
TR15-195
| 3rd December 2015
__

Robin Kothari#### Nearly optimal separations between communication (or query) complexity and partitions

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
TR10-093
| 3rd June 2010
__

Sourav Chakraborty, David García Soriano, Arie Matsliah#### Nearly Tight Bounds for Testing Function Isomorphism

__
TR07-063
| 2nd July 2007
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations

__
TR08-087
| 31st July 2008
__

Tomas Feder, Carlos Subi#### Nearly Tight Bounds on the Number of Hamiltonian Circuits of the Hypercube and Generalizations (revised)

__
TR07-009
| 8th January 2007
__

Nathan Segerlind#### Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

Revisions: 1
,
Comments: 1

__
TR15-026
| 21st February 2015
__

Siyao Guo, Ilan Komargodski#### Negation-Limited Formulas

Revisions: 1

__
TR20-191
| 27th December 2020
__

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay#### Negations Provide Strongly Exponential Savings

__
TR96-037
| 14th June 1996
__

Stasys Jukna, Alexander Razborov#### Neither Reading Few Bits Twice nor Reading Illegally Helps Much

__
TR02-051
| 16th July 2002
__

Chris Pollett#### Nepomnjascij's Theorem and Independence Proofs in Bounded Arithmetic

__
TR04-034
| 12th April 2004
__

April Rasala Lehman, Eric Lehman#### Network Coding: Does the Model Need Tuning?

__
TR96-031
| 30th April 1996
__

#### Networks of Spiking Neurons: The Third Generation of Neural Network Models

__
TR01-071
| 24th October 2001
__

Robert Albin Legenstein#### Neural Circuits for Pattern Recognition with Small Total Wire Length

__
TR94-017
| 12th December 1994
__

#### Neural Nets with Superlinear VC-Dimension

__
TR01-045
| 26th April 2001
__

Michael Schmitt#### Neural Networks with Local Receptive Fields and Superlinear VC Dimension

__
TR20-085
| 5th June 2020
__

Gal Vardi, Ohad Shamir#### Neural Networks with Small Weights and Depth-Separation Barriers

__
TR00-031
| 31st May 2000
__

Eduardo D. Sontag#### Neural Systems as Nonlinear Filters

__
TR12-106
| 27th August 2012
__

Alan Guo, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR12-149
| 8th November 2012
__

Alan Guo, Swastik Kopparty, Madhu Sudan#### New affine-invariant codes from lifting

Comments: 1

__
TR13-108
| 9th August 2013
__

Rahul Santhanam, Ryan Williams#### New Algorithms for QBF Satisfiability and Implications for Circuit Complexity

Revisions: 1

__
TR95-030
| 20th June 1995
__

Marek Karpinski, Alexander Zelikovsky#### New Approximation Algorithms for the Steiner Tree Problems

__
TR18-153
| 22nd August 2018
__

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma#### New Bounds for Energy Complexity of Boolean Functions

Revisions: 1

__
TR20-117
| 4th August 2020
__

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov#### New bounds on the half-duplex communication complexity

Revisions: 3

__
TR00-046
| 19th June 2000
__

Philipp Woelfel#### New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing

__
TR06-108
| 24th August 2006
__

Dan Gutfreund, Amnon Ta-Shma#### New connections between derandomization, worst-case complexity and average-case complexity

__
TR18-205
| 3rd December 2018
__

Siddhesh Chaubal, Anna Gal#### New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

__
TR06-097
| 9th August 2006
__

Emanuele Viola#### New correlation bounds for GF(2) polynomials using Gowers uniformity

__
TR09-090
| 6th October 2009
__

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson#### New Direct-Product Testers and 2-Query PCPs

__
TR20-033
| 12th March 2020
__

Suryajith Chillara#### New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 2

__
TR15-151
| 14th September 2015
__

Eshan Chattopadhyay, David Zuckerman#### New Extractors for Interleaved Sources

Revisions: 1

__
TR16-029
| 7th March 2016
__

Joshua Brakensiek, Venkatesan Guruswami#### New hardness results for graph and hypergraph colorings

__
TR16-159
| 18th October 2016
__

Daniel Grier, Luke Schaeffer#### New Hardness Results for the Permanent Using Linear Optics

__
TR13-045
| 26th March 2013
__

Marek Karpinski, Michael Lampis, Richard Schmied#### New Inapproximability Bounds for TSP

__
TR12-147
| 7th November 2012
__

Xin Li#### New Independent Source Extractors with Exponential Improvement

__
TR17-073
| 28th April 2017
__

Eric Allender, Shuichi Hirahara#### New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems

__
TR12-112
| 7th September 2012
__

Andrew Drucker#### New Limits to Classical and Quantum Instance Compression

Revisions: 3

__
TR06-127
| 7th October 2006
__

Sergey Yekhanin#### New Locally Decodable Codes and Private Information Retrieval Schemes

__
TR23-001
| 5th January 2023
__

Prerona Chatterjee, Pavel Hrubes#### New Lower Bounds against Homogeneous Non-Commutative Circuits

__
TR22-183
| 19th December 2022
__

Lijie Chen#### New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

__
TR95-002
| 1st January 1995
__

Detlef Sieling#### New Lower Bounds and Hierarchy Results for Restricted Branching Programs

__
TR07-006
| 12th January 2007
__

David P. Woodruff#### New Lower Bounds for General Locally Decodable Codes

__
TR12-034
| 5th April 2012
__

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett#### New Lower Bounds for Matching Vector Codes

Revisions: 5

__
TR13-015
| 18th January 2013
__

Iordanis Kerenidis, Mathieu Laurière, David Xiao#### New lower bounds for privacy in communication protocols

__
TR20-015
| 18th February 2020
__

Emanuele Viola#### New lower bounds for probabilistic degree and AC0 with parity gates

Revisions: 5

__
TR02-060
| 15th July 2002
__

Ke Yang#### New Lower Bounds for Statistical Query Learning

__
TR22-027
| 22nd February 2022
__

Guy Blanc, Dean Doron#### New Near-Linear Time Decodable Codes Closer to the GV Bound

Revisions: 1

__
TR21-094
| 6th July 2021
__

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas#### New Non-FPT Lower Bounds for Some Arithmetic Formulas

__
TR17-076
| 21st April 2017
__

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee#### New Protocols for Conditional Disclosure of Secrets (and More)

Revisions: 2

__
TR16-167
| 1st November 2016
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

Revisions: 1

__
TR06-059
| 3rd May 2006
__

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami#### New Results for Learning Noisy Parities and Halfspaces

__
TR08-025
| 3rd January 2008
__

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan#### New results on Noncommutative and Commutative Polynomial Identity Testing

Revisions: 2

__
TR04-107
| 24th November 2004
__

Ingo Wegener, Philipp Woelfel#### New Results on the Complexity of the Middle Bit of Multiplication

Revisions: 1

__
TR11-116
| 17th August 2011
__

Andris Ambainis, Xiaoming Sun#### New separation between $s(f)$ and $bs(f)$

__
TR11-024
| 25th February 2011
__

Rahul Jain#### New strong direct product results in communication complexity

__
TR14-035
| 13th March 2014
__

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang#### New Time-Space Upperbounds for Directed Reachability in High-genus and $H$-minor-free Graphs.

__
TR00-037
| 26th May 2000
__

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith#### New Worst-Case Upper Bounds for MAX-2-SAT with Application to MAX-CUT

__
TR11-017
| 8th February 2011
__

Fengming Wang#### NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth

__
TR22-023
| 19th February 2022
__

Erfan Khaniki#### Nisan--Wigderson generators in Proof Complexity: New lower bounds

__
TR10-046
| 22nd March 2010
__

Ján Pich#### Nisan-Wigderson generators in proof systems with forms of interpolation

__
TR18-012
| 20th January 2018
__

Valentine Kabanets, Zhenjian Lu#### Nisan-Wigderson Pseudorandom Generators for Circuits with Polynomial Threshold Gates

__
TR20-035
| 23rd February 2020
__

Justin Holmgren#### No-Signaling MIPs and Faster-Than-Light Communication, Revisited

__
TR19-111
| 16th August 2019
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Noisy Beeps

__
TR08-004
| 2nd January 2008
__

Zeev Dvir, Amir Shpilka#### Noisy Interpolating Sets for Low Degree Polynomials

__
TR11-044
| 25th March 2011
__

Shubhangi Saraf, Sergey Yekhanin#### Noisy Interpolation of Sparse Polynomials, and Applications

__
TR16-021
| 11th February 2016
__

Shachar Lovett, Jiapeng Zhang#### Noisy Population Recovery from Unknown Noise

__
TR16-026
| 20th February 2016
__

Anindya De, Michael Saks, Sijian Tang#### Noisy population recovery in polynomial time

__
TR22-174
| 23rd November 2022
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

Revisions: 2

__
TR04-052
| 14th June 2004
__

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

__
TR17-050
| 15th March 2017
__

Joe Boninger, Joshua Brody, Owen Kephart#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

__
TR17-040
| 4th March 2017
__

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao#### Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers

Revisions: 2

__
TR22-098
| 12th July 2022
__

Nader Bshouty#### Non-Adaptive Proper Learning Polynomials

__
TR22-049
| 4th April 2022
__

Xinyu Mao, Noam Mazor, Jiapeng Zhang#### Non-Adaptive Universal One-Way Hash Functions from Arbitrary One-Way Functions

Revisions: 2

__
TR20-160
| 2nd November 2020
__

Oded Goldreich, Avi Wigderson#### Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model

Revisions: 3

__
TR02-071
| 6th June 2002
__

Bruno Codenotti, Igor E. Shparlinski#### Non-approximability of the Permanent of Structured Matrices over Finite Fields

__
TR13-063
| 19th April 2013
__

Dung Nguyen, Alan Selman#### Non-autoreducible Sets for NEXP

__
TR18-138
| 10th August 2018
__

Shuichi Hirahara#### Non-black-box Worst-case to Average-case Reductions within NP

Revisions: 1

__
TR95-043
| 14th September 1995
__

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay#### Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds

__
TR10-021
| 21st February 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Non-commutative circuits and the sum-of-squares problem

__
TR16-094
| 6th June 2016
__

Guillaume Lagarde, Guillaume Malod#### Non-commutative computations: lower bounds and polynomial identity testing

Comments: 1

__
TR97-048
| 13th October 1997
__

Soren Riis, Meera Sitharam#### Non-constant Degree Lower Bounds imply linear Degree Lower Bounds

__
TR19-031
| 4th March 2019
__

Lijie Chen#### Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits

Revisions: 1

__
TR18-009
| 9th January 2018
__

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs#### Non-Interactive Delegation for Low-Space Non-Deterministic Computation

__
TR18-203
| 1st December 2018
__

Yael Kalai, Dakshita Khurana#### Non-Interactive Non-Malleability from Quantum Supremacy

__
TR13-078
| 28th May 2013
__

Tom Gur, Ron Rothblum#### Non-Interactive Proofs of Proximity

Revisions: 1

__
TR16-077
| 12th May 2016
__

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai#### Non-Interactive RAM and Batch NP Delegation from any PIR

Revisions: 1

__
TR01-052
| 26th April 2001
__

Mikhail V. Vyugin, Vladimir Vyugin#### Non-linear Inequalities between Predictive and Kolmogorov Complexity

__
TR08-076
| 17th June 2008
__

Ryan Williams#### Non-Linear Time Lower Bound for (Succinct) Quantified Boolean Formulas

__
TR19-030
| 19th February 2019
__

Claude Crépeau, Nan Yang#### Non-Locality in Interactive Proofs

__
TR20-023
| 10th February 2020
__

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan#### Non-Malleability against Polynomial Tampering

Revisions: 1

__
TR14-102
| 4th August 2014
__

Eshan Chattopadhyay, David Zuckerman#### Non-Malleable Codes Against Constant Split-State Tampering

__
TR16-180
| 15th November 2016
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions

__
TR18-040
| 21st February 2018
__

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan#### Non-Malleable Codes for Small-Depth Circuits

__
TR13-081
| 6th June 2013
__

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett#### Non-malleable Codes from Additive Combinatorics

__
TR13-121
| 4th September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Non-Malleable Coding Against Bit-wise and Split-State Tampering

Revisions: 1

__
TR15-183
| 16th November 2015
__

Gil Cohen#### Non-Malleable Extractors - New Tools and Improved Constructions

__
TR18-070
| 13th April 2018
__

Eshan Chattopadhyay, Xin Li#### Non-Malleable Extractors and Codes in the Interleaved Split-State Model and More

Revisions: 3

__
TR15-075
| 29th April 2015
__

Eshan Chattopadhyay, Vipul Goyal, Xin Li#### Non-Malleable Extractors and Codes, with their Many Tampered Extensions

Revisions: 1

__
TR11-166
| 4th December 2011
__

Xin Li#### Non-Malleable Extractors for Entropy Rate $<1/2$

Revisions: 1

__
TR16-030
| 7th March 2016
__

Gil Cohen#### Non-Malleable Extractors with Logarithmic Seeds

__
TR11-096
| 2nd July 2011
__

Gil Cohen, Ran Raz, Gil Segev#### Non-Malleable Extractors with Short Seeds and Applications to Privacy Amplification

__
TR14-128
| 10th October 2014
__

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski#### Non-malleable Reductions and Applications

Revisions: 3

__
TR06-090
| 22nd June 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang#### Non-Mitotic Sets

__
TR04-054
| 5th June 2004
__

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin#### Non-reducible descriptions for conditional Kolmogorov complexity

__
TR09-113
| 9th November 2009
__

Anindya De, Luca Trevisan, Madhur Tulsiani#### Non-uniform attacks against one-way functions and PRGs

__
TR02-057
| 19th September 2002
__

Richard J. Lipton, Anastasios Viglas#### Non-uniform Depth of Polynomial Time and Space Simulations

__
TR05-154
| 11th December 2005
__

Albert Atserias#### Non-Uniform Hardness for NP via Black-Box Adversaries

__
TR14-175
| 15th December 2014
__

Abhishek Bhowmick, Shachar Lovett#### Nonclassical polynomials as a barrier to polynomial lower bounds

__
TR14-105
| 9th August 2014
__

Craig Gentry#### Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington’s Theorem

Comments: 1

__
TR15-124
| 3rd August 2015
__

Vikraman Arvind, Pushkar Joglekar, Raja S#### Noncommutative Valiant's Classes: Structure and Complete Problems

Revisions: 1

__
TR12-142
| 3rd November 2012
__

Markus Bläser#### Noncommutativity makes determinants hard

__
TR18-013
| 18th January 2018
__

John Hitchcock, Adewale Sekoni#### Nondeterminisic Sublinear Time Has Measure 0 in P

__
TR19-043
| 12th March 2019
__

Toniann Pitassi, Morgan Shirley, Thomas Watson#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

__
TR12-080
| 18th June 2012
__

Baris Aydinlioglu, Dieter van Melkebeek#### Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

__
TR15-148
| 9th September 2015
__

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

__
TR08-075
| 7th July 2008
__

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller#### Nondeterministic Instance Complexity and Proof Systems with Advice

__
TR19-100
| 31st July 2019
__

Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas#### Nonnegative rank measures and monotone algebraic branching programs

__
TR13-126
| 11th September 2013
__

Arman Fazeli, Shachar Lovett, Alex Vardy#### Nontrivial t-designs over finite fields exist for all t

__
TR15-138
| 25th August 2015
__

Michal Koucky#### Nonuniform catalytic space and the direct sum for space

Revisions: 1

__
TR18-011
| 18th January 2018
__

John Hitchcock, Hadi Shafei#### Nonuniform Reductions and NP-Completeness

__
TR06-064
| 1st May 2006
__

Moses Charikar, Konstantin Makarychev, Yury Makarychev#### Note on MAX 2SAT

__
TR95-014
| 27th January 1995
__

U. Faigle, W. Kern, M. Streng#### Note On the Computational Complexity of $j$-Radii of Polytopes in ${\Re}^n$

__
TR20-102
| 9th July 2020
__

Stasys Jukna#### Notes on Hazard-Free Circuits

Revisions: 2

__
TR97-058
| 2nd December 1997
__

Oded Goldreich#### Notes on Levin's Theory of Average-Case Complexity.

__
TR22-094
| 3rd July 2022
__

Stasys Jukna#### Notes on Monotone Read-k Circuits

Revisions: 2

__
TR12-100
| 23rd July 2012
__

Tomas Jirotka#### NP Search Problems

__
TR04-103
| 19th November 2004
__

Lance Fortnow, Adam Klivans#### NP with Small Advice

__
TR05-026
| 15th February 2005
__

Scott Aaronson#### NP-complete Problems and Physical Reality

__
TR19-050
| 20th March 2019
__

Titus Dose, Christian Glaßer#### NP-Completeness, Proof Systems, and Disjoint NP-Pairs

__
TR08-022
| 9th January 2008
__

Harry Buhrman, John Hitchcock#### NP-Hard Sets are Exponentially Dense Unless NP is contained in coNP/poly

__
TR16-162
| 18th October 2016
__

Joshua Grochow#### NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications

__
TR96-021
| 13th February 1996
__

Yongge Wang#### NP-hard Sets Are Superterse unless NP Is Small

__
TR10-112
| 15th July 2010
__

Subhash Khot, Dana Moshkovitz#### NP-Hardness of Approximately Solving Linear Equations Over Reals

__
TR20-021
| 21st February 2020
__

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira#### NP-Hardness of Circuit Minimization for Multi-Output Functions

__
TR18-073
| 21st April 2018
__

Amey Bhangale#### NP-hardness of coloring $2$-colorable hypergraph with poly-logarithmically many colors

__
TR22-119
| 24th August 2022
__

Shuichi Hirahara#### NP-Hardness of Learning Programs and Partial MCSP

__
TR18-030
| 9th February 2018
__

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam#### NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

__
TR16-176
| 9th November 2016
__

Venkata Gandikota, Badih Ghazi, Elena Grigorescu#### NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem

__
TR98-073
| 14th December 1998
__

Tomoyuki Yamakami, Andrew Chi-Chih Yao#### NQP = co-C_{=}P

Revisions: 2

__
TR20-001
| 31st December 2019
__

Or Meir, Jakob Nordström, Robert Robere, Susanna de Rezende#### Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Revisions: 2

__
TR21-097
| 7th July 2021
__

Jacobo Toran, Florian Wörz#### Number of Variables for Graph Identification and the Resolution of GI Formulas

Albert Atserias, Massimo Lauria, Jakob Nordström

We prove that there are 3-CNF formulas over n variables that can be refuted in resolution in width w but require resolution proofs of size n^Omega(w). This shows that the simple counting argument that any formula refutable in width w must have a proof in size n^O(w) is essentially tight. ... more >>>

Jakob Nordström

The width of a resolution proof is the maximal number of literals in any clause of the proof. The space of a proof is the maximal number of memory cells used if the proof is only allowed to resolve on clauses kept in memory. Both of these measures have previously ... more >>>

Edith Elkind, Leslie Ann Goldberg, Paul Goldberg

Graphical games have been proposed as a game-theoretic model of large-scale

distributed networks of non-cooperative agents. When the number of players is

large, and the underlying graph has low degree, they provide a concise way to

represent the players' payoffs. It has recently been shown that the problem of

finding ...
more >>>

Alexander Razborov, Steven Rudich

We introduce the notion of {\em natural} proof.

We argue that the known proofs of lower bounds on the complexity of explicit

Boolean functions in non-monotone models

fall within our definition of natural.

We show based on a hardness assumption

that natural proofs can't prove superpolynomial lower bounds ...
more >>>

Bin Fu

A long standing open problem in the computational complexity theory

is to separate NE from BPP, which is a subclass of $NP_T (NP\cap P/poly)$.

In this paper, we show that $NE\not\subseteq NP_T (NP \cap$ Nonexponentially-Dense-Class),

where Nonexponentially-Dense-Class is the class of languages A without exponential density

(for ...
more >>>

Irit Dinur, Roy Meshulam

We study the stability of covers of simplicial complexes. Given a map f:Y?X that satisfies almost all of the local conditions of being a cover, is it close to being a genuine cover of X? Complexes X for which this holds are called cover-stable. We show that this is equivalent ... more >>>

Mert Saglam

Let $u,v \in \mathbb{R}^\Omega_+$ be positive unit vectors and $S\in\mathbb{R}^{\Omega\times\Omega}_+$ be a symmetric substochastic matrix. For an integer $t\ge 0$, let $m_t = \smash{\left\langle v,S^tu\right\rangle}$, which we view as the heat measured by $v$ after an initial heat configuration $u$ is let to diffuse for $t$ time steps according to ... more >>>

Mario Szegedy

Based on experimental results N. Duffield, C. Lund and M. Thorup \cite{dlt2} conjectured

that the variance of their highly successful priority sampling procedure

is not larger than the variance of the threshold sampling procedure with sample size one smaller.

The conjecture's significance is that the latter procedure is provably optimal ...
more >>>

Vince Grolmusz

We show how one can use non-prime-power, composite moduli for

computing representations of the product of two $n\times n$ matrices

using only $n^{2+o(1)}$ multiplications.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S| > s$. Thus, there is a deterministic polynomial identity test (PIT) for all degree-$s$ size-$s$ ... more >>>

Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao, Dave Touchette

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with $r$ rounds, we prove a lower bound of $\tilde{\Omega}(n/r)$ on the communication required for computing disjointness of input size $n$, which is optimal up to logarithmic factors. The previous best lower bound ... more >>>

Aaron (Louie) Putterman, Edward Pyne

We give a deterministic white-box algorithm to estimate the expectation of a read-once branching program of length $n$ and width $w$ in space

$$\tilde{O}\left(\log n+\sqrt{\log n}\cdot\log w\right).$$

In particular, we obtain an almost optimal space $\tilde{O}(\log n)$ derandomization of programs up to width $w=2^{\sqrt{\log n}}$.

Previously, ...
more >>>

Anindya De, Thomas Vidick

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.

Moreover, the queries we use are comparison ...
more >>>

Christoph Berkholz, Jakob Nordström

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least n^?(k/log k). Our trade-offs also apply to first-order counting logic, and ... more >>>

Alexander A. Sherstov, Pei Wu

The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum ... more >>>

Dean Doron, Pooya Hatami, William Hoza

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

We present the best known separation

between tree-like and general resolution, improving

on the recent $\exp(n^\epsilon)$ separation of \cite{BEGJ98}.

This is done by constructing a natural family of contradictions, of

size $n$, that have $O(n)$-size resolution

refutations, but only $\exp (\Omega(n/\log n))$-size tree-like refutations.

This result ...
more >>>

Deepanshu Kush, Shubhangi Saraf

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this paper, we make ... more >>>

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

A code $\mathcal{C}$ is $(1-\tau,L)$ erasure list-decodable if for every codeword $w$, after erasing any $1-\tau$ fraction of the symbols of $w$,

the remaining $\tau$-fraction of its symbols have at most $L$ possible completions into codewords of $\mathcal{C}$.

Non-explicitly, there exist binary $(1-\tau,L)$ erasure list-decodable codes having rate $O(\tau)$ and ...
more >>>

Mahdi Cheraghchi, Piotr Indyk

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

Venkatesan Guruswami, Euiwoong Lee

The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

Robin Kothari

We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Göös, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) ... more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Sourav Chakraborty, David García Soriano, Arie Matsliah

In this paper we study the problem of testing structural equivalence (isomorphism) between a pair of Boolean

functions $f,g:\zo^n \to \zo$. Our main focus is on the most studied case, where one of the functions is given (explicitly), and the other function can be queried.

We prove that for every ... more >>>

Tomas Feder, Carlos Subi

We conjecture that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$

such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove this conjecture in the case where there are

two dimensions ...
more >>>

Tomas Feder, Carlos Subi

It has been shown that for every perfect matching $M$ of the $d$-dimensional

$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching

$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the

$d$-dimensional hypercube. We prove a generalization of a special case of ...
more >>>

Nathan Segerlind

We demonstrate a family of propositional formulas in conjunctive normal form

so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$

to refute using the tree-like OBDD refutation system of

Atserias, Kolaitis and Vardi

with respect to all variable orderings.

All known symbolic quantifier elimination algorithms for satisfiability

generate ...
more >>>

Siyao Guo, Ilan Komargodski

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>

Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

Stasys Jukna, Alexander Razborov

We first consider so-called {\em $(1,+s)$-branching programs}

in which along every consistent path at most $s$ variables are tested

more than once. We prove that any such program computing a

characteristic function of a linear code $C$ has size at least

more >>>

Chris Pollett

The use of Nepomnjascij's Theorem in the proofs of independence results

for bounded arithmetic theories is investigated. Using this result and similar ideas, the following statements are proven: (1) At least one of S_1 or TLS does not prove the Matiyasevich-Davis-Robinson-Putnam Theorem and (2) TLS does not prove Sigma^b_{1,1}=Pi^b_{1,1}. Here ...
more >>>

April Rasala Lehman, Eric Lehman

We consider the general network information flow problem, which was

introduced by Ahlswede et. al. We show a periodicity effect: for

every integer m greater than 1, there exists an instance of the

network information flow problem that admits a solution if and only if

the alphabet size is a ...
more >>>

The computational power of formal models for

networks of spiking neurons is compared with

that of other neural network models based on

McCulloch Pitts neurons (i.e. threshold gates)

respectively sigmoidal gates. In particular it

is shown that networks of spiking neurons are

...
more >>>

Robert Albin Legenstein

One of the most basic pattern recognition problems is whether a

certain local feature occurs in some linear array to the left of

some other local feature. We construct in this article circuits that

solve this problem with an asymptotically optimal number of

threshold gates. Furthermore it is shown that ...
more >>>

It has been known for quite a while that the Vapnik-Chervonenkis dimension

(VC-dimension) of a feedforward neural net with linear threshold gates is at

most O(w log w), where w is the total number of weights in the neural net.

We show in this paper that this bound is in ...
more >>>

Michael Schmitt

Local receptive field neurons comprise such well-known and widely

used unit types as radial basis function neurons and neurons with

center-surround receptive field. We study the Vapnik-Chervonenkis

(VC) dimension of feedforward neural networks with one hidden layer

of these units. For several variants of local receptive field

neurons we show ...
more >>>

Gal Vardi, Ohad Shamir

In studying the expressiveness of neural networks, an important question is whether there are functions which can only be approximated by sufficiently deep networks, assuming their size is bounded. However, for constant depths, existing results are limited to depths $2$ and $3$, and achieving results for higher depths has been ... more >>>

Eduardo D. Sontag

Experimental data show that biological synapses behave quite

differently from the symbolic synapses in all common artificial

neural network models. Biological synapses are dynamic, i.e., their

``weight'' changes on a short time scale by several hundred percent

in dependence of the past input to the synapse. ...
more >>>

Alan Guo, Madhu Sudan

In this work we explore error-correcting codes derived from

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Alan Guo, Swastik Kopparty, Madhu Sudan

the ``lifting'' of ``affine-invariant'' codes.

Affine-invariant codes are simply linear codes whose coordinates

are a vector space over a field and which are invariant under

affine-transformations of the coordinate space. Lifting takes codes

defined over a vector space of small dimension ...
more >>>

Rahul Santhanam, Ryan Williams

We revisit the complexity of the satisfiability problem for quantified Boolean formulas. We show that satisfiability

of quantified CNFs of size $\poly(n)$ on $n$ variables with $O(1)$

quantifier blocks can be solved in time $2^{n-n^{\Omega(1)}}$ by zero-error

randomized algorithms. This is the first known improvement over brute force search in ...
more >>>

Marek Karpinski, Alexander Zelikovsky

The Steiner tree problem asks for the shortest tree connecting

a given set of terminal points in a metric space. We design

new approximation algorithms for the Steiner tree problems

using a novel technique of choosing Steiner points in dependence

on the possible deviation from ...
more >>>

Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{0,1\}^n$ the numbers of gates of the circuit $C$ (excluding the inputs) that output a one. Energy Complexity ... more >>>

Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov

In this work, we continue the research started in [HIMS18], where the authors suggested to study the half-duplex communication complexity. Unlike the classical model of communication complexity introduced by Yao, in the half-duplex model, Alice and Bob can speak or listen simultaneously, as if they were talking using a walkie-talkie. ... more >>>

Philipp Woelfel

Ordered binary decision diagrams (OBDDs) belong to the most important

representation types for Boolean functions. Although they allow

important operations such as satisfiability test and equality test to

be performed efficiently, their limitation lies in the fact, that they

may require exponential size for important functions. Bryant ...
more >>>

Dan Gutfreund, Amnon Ta-Shma

We show that a mild derandomization assumption together with the

worst-case hardness of NP implies the average-case hardness of a

language in non-deterministic quasi-polynomial time. Previously such

connections were only known for high classes such as EXP and

PSPACE.

There has been a long line of research trying to explain ... more >>>

Siddhesh Chaubal, Anna Gal

Nisan and Szegedy conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a ... more >>>

Emanuele Viola

We study the correlation between low-degree GF(2) polynomials p and explicit functions. Our main results are the following:

(I) We prove that the Mod_m unction on n bits has correlation at most exp(-Omega(n/4^d)) with any GF(2) polynomial of degree d, for any fixed odd integer m. This improves on the ... more >>>

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and ...
more >>>

Suryajith Chillara

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

Eshan Chattopadhyay, David Zuckerman

We study how to extract randomness from a $C$-interleaved source, that is, a source comprised of $C$ independent sources whose bits or symbols are interleaved. We describe a simple approach for constructing such extractors that yields:

(1) For some $\delta>0, c > 0$,

explicit extractors for $2$-interleaved sources on $\{ ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami

Finding a proper coloring of a $t$-colorable graph $G$ with $t$ colors is a classic NP-hard problem when $t\ge 3$. In this work, we investigate the approximate coloring problem in which the objective is to find a proper $c$-coloring of $G$ where $c \ge t$. We show that for all ... more >>>

Daniel Grier, Luke Schaeffer

In 2011, Aaronson gave a striking proof, based on quantum linear optics, showing that the problem of computing the permanent of a matrix is #P-hard. Aaronson's proof led naturally to hardness of approximation results for the permanent, and it was arguably simpler than Valiant's seminal proof of the same fact ... more >>>

Marek Karpinski, Michael Lampis, Richard Schmied

In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. For weak sources on $n$ bits with min-entropy $k$, perviously the best known extractor needs to use at least $\frac{\log n}{\log k}$ independent sources \cite{Rao06, BarakRSW06}. In this paper we give a new extractor that only ... more >>>

Eric Allender, Shuichi Hirahara

The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) ... more >>>

Andrew Drucker

Given an instance of a hard decision problem, a limited goal is to $compress$ that instance into a smaller, equivalent instance of a second problem. As one example, consider the problem where, given Boolean formulas $\psi^1, \ldots, \psi^t$, we must determine if at least one $\psi^j$ is satisfiable. An $OR-compression ... more >>>

Sergey Yekhanin

A q-query Locally Decodable Code (LDC) encodes an n-bit message

x as an N-bit codeword C(x), such that one can

probabilistically recover any bit x_i of the message

by querying only q bits of the codeword C(x), even after

some constant fraction of codeword bits has been corrupted.

We give ... more >>>

Prerona Chatterjee, Pavel Hrubes

We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log ... more >>>

Lijie Chen

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ...
more >>>

Detlef Sieling

In unrestricted branching programs all variables may be tested

arbitrarily often on each path. But exponential lower bounds are only

known, if on each path the number of tests of each variable is bounded

(Borodin, Razborov and Smolensky (1993)). We examine branching programs

in which for each path the ...
more >>>

David P. Woodruff

For any odd integer q > 1, we improve the lower bound for general q-query locally decodable codes C: {0,1}^n -> {0,1}^m from m = Omega(n/log n)^{(q+1)/(q-1)} to m = Omega(n^{(q+1)/(q-1)})/log n. For example, for q = 3 we improve the previous bound from Omega(n^2/log^2 n) to Omega(n^2/log n). For ... more >>>

Abhishek Bhowmick, Zeev Dvir, Shachar Lovett

We prove new lower bounds on the encoding length of Matching Vector (MV) codes. These recently discovered families of Locally Decodable Codes (LDCs) originate in the works of Yekhanin [Yek] and Efremenko [Efr] and are the only known families of LDCs with a constant number of queries and sub-exponential encoding ... more >>>

Iordanis Kerenidis, Mathieu Laurière, David Xiao

Communication complexity is a central model of computation introduced by Yao in 1979, where

two players, Alice and Bob, receive inputs x and y respectively and want to compute $f(x; y)$ for some fixed

function f with the least amount of communication. Recently people have revisited the question of the ...
more >>>

Emanuele Viola

We prove new lower bounds for computing some functions $f:\{0,1\}^{n}\to\{0,1\}$ in $E^{NP}$ by polynomials modulo $2$, constant-depth circuits with parity gates ($AC^{0}[\oplus]$), and related classes. Results include:

(1) $\Omega(n/\log^{2}n)$ lower bounds probabilistic degree. This is optimal up to a factor $O(\log^{2}n)$. The previous best lower bound was $\Omega(\sqrt{n})$ proved in ... more >>>

Ke Yang

We prove two lower bounds on the Statistical Query (SQ) learning

model. The first lower bound is on weak-learning. We prove that for a

concept class of SQ-dimension $d$, a running time of

$\Omega(d/\log d)$ is needed. The SQ-dimension of a concept class is

defined to be the maximum number ...
more >>>

Guy Blanc, Dean Doron

We construct a family of binary codes of relative distance $\frac{1}{2}-\varepsilon$ and rate $\varepsilon^{2} \cdot 2^{-\log^{\alpha}(1/\varepsilon)}$ for $\alpha \approx \frac{1}{2}$ that are decodable, probabilistically, in near linear time. This improves upon the rate of the state-of-the-art near-linear time decoding near the GV bound due to Jeronimo, Srivastava, and Tulsiani, who ... more >>>

Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

An Algebraic Formula for a polynomial $P\in F[x_1,\ldots,x_N]$ is an algebraic expression for $P(x_1,\ldots,x_N)$ using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class $\mathrm{NC}^1.$ Proving lower bounds against this model is thus an important problem.

It is known that, to prove ... more >>>

Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee

We present new protocols for conditional disclosure of secrets (CDS),

where two parties want to disclose a secret to a third party if and

only if their respective inputs satisfy some predicate.

- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,

we present two protocols that achieve ...
more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

The problem of dynamic connectivity in graphs has been extensively studied in the cell probe model. The task is to design a data structure that supports addition of edges and checks connectivity between arbitrary pair of vertices. Let $w, t_q, t_u$ denote the cell width, expected query time and worst ... more >>>

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

We address well-studied problems concerning the learnability of parities and halfspaces in the presence of classification noise.

Learning of parities under the uniform distribution with random classification noise,also called the noisy parity problem is a famous open problem in computational learning. We reduce a number of basic problems regarding ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan

Using ideas from automata theory we design a new efficient

(deterministic) identity test for the \emph{noncommutative}

polynomial identity testing problem (first introduced and studied by

Raz-Shpilka in 2005 and Bogdanov-Wee in 2005). More precisely,

given as input a noncommutative

circuit $C(x_1,\cdots,x_n)$ computing a ...
more >>>

Ingo Wegener, Philipp Woelfel

It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}.

This paper contains several new results on its complexity.

First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated.

A randomized algorithm for MUL_{n-1,n} with k=O(log ...
more >>>

Andris Ambainis, Xiaoming Sun

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.

more >>>Rahul Jain

We show two new direct product results in two different models of communication complexity. Our first result is in the model of one-way public-coin model. Let $f \subseteq X \times Y \times Z $ be a relation and $\epsilon >0$ be a constant. Let $R^{1,pub}_{\epsilon}(f)$ represent the communication complexity of ... more >>>

Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, Lin Yang

We obtain the following new simultaneous time-space upper bounds for the directed reachability problem.

(1) A polynomial-time,

$\tilde{O}(n^{2/3}g^{1/3})$-space algorithm for directed graphs embedded on orientable surfaces of genus $g$. (2) A polynomial-time, $\tilde{O}(n^{2/3})$-space algorithm for all $H$-minor-free graphs given the tree decomposition, and (3) for $K_{3, 3}$-free and ...
more >>>

Jens Gramm, Edward Hirsch, Rolf Niedermeier, Peter Rossmanith

The maximum 2-satisfiability problem (MAX-2-SAT) is:

given a Boolean formula in $2$-CNF, find a truth

assignment that satisfies the maximum possible number

of its clauses. MAX-2-SAT is MAXSNP-complete.

Recently, this problem received much attention in the

contexts of approximation (polynomial-time) algorithms

...
more >>>

Fengming Wang

$\mbox{ACC}_m$ circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of $\mbox{ACC}_m$ circuits of quasi-polynomial size and ... more >>>

Erfan Khaniki

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

Ján Pich

We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.

more >>>Valentine Kabanets, Zhenjian Lu

We show how the classical Nisan-Wigderson (NW) generator [Nisan & Wigderson, 1994] yields a nontrivial pseudorandom generator (PRG) for circuits with sublinearly many polynomial threshold function (PTF) gates. For the special case of a single PTF of degree $d$ on $n$ inputs, our PRG for error $\epsilon$ has the seed ... more >>>

Justin Holmgren

We revisit one original motivation for the study of no-signaling multi-prover

interactive proofs (NS-MIPs): specifically, that two spatially separated

provers are guaranteed to be no-signaling by the physical principle that

information cannot travel from one point to another faster than light.

We observe that with ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

We study the effect of noise on the $n$-party beeping model. In this model, in every round, each party may decide to either `beep' or not. All parties hear a beep if and only if at least one party beeps. The beeping model is becoming increasingly popular, as it offers ... more >>>

Zeev Dvir, Amir Shpilka

A Noisy Interpolating Set (NIS) for degree $d$ polynomials is a

set $S \subseteq \F^n$, where $\F$ is a finite field, such that

any degree $d$ polynomial $q \in \F[x_1,\ldots,x_n]$ can be

efficiently interpolated from its values on $S$, even if an

adversary corrupts a constant fraction of the values. ...
more >>>

Shubhangi Saraf, Sergey Yekhanin

Let $f\in F_q[x]$ be a polynomial of degree $d\leq q/2.$ It is well-known that $f$ can be uniquely recovered from its values at some $2d$ points even after some small fraction of the values are corrupted. In this paper we establish a similar result for sparse polynomials. We show that ... more >>>

Shachar Lovett, Jiapeng Zhang

The noisy population recovery problem is a statistical inference problem, which is a special case of the problem of learning mixtures of product distributions. Given an unknown distribution on $n$-bit strings with support of size $k$, and given access only to noisy samples from it, where each bit is flipped ... more >>>

Anindya De, Michael Saks, Sijian Tang

In the noisy population recovery problem of Dvir et al., the goal is to learn

an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,

a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with

more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Much of today's communication is carried out over large wireless systems with different input-output behaviors. In this work, we compare the power of central abstractions of wireless communication through the general notion of boolean symmetric $f$-channels: In every round of the $f$-channel, each of its $n$ parties decides to either ... more >>>

Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

In this paper, we study two questions related to

the problem of testing whether a function is close to a homomorphism.

For two finite groups $G,H$ (not necessarily Abelian),

an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,

say that $f$ is $\epsilon$-close to a homomorphism ...
more >>>

Joe Boninger, Joshua Brody, Owen Kephart

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao

We prove new cell-probe lower bounds for data structures that maintain a subset of $\{1,2,...,n\}$, and compute the median of the set. The data structure is said to handle insertions non-adaptively if the locations of memory accessed depend only on the element being inserted, and not on the contents of ... more >>>

Nader Bshouty

We give the first polynomial-time *non-adaptive* proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. Our algorithm, for $s$-sparse polynomial over $n$ variables, makes $q=(s/\epsilon)^{\gamma(s,\epsilon)}\log n$ queries where $2.66\le \gamma(s,\epsilon)\le 6.922$ and runs in $\tilde O(n)\cdot poly(s,1/\epsilon)$ time. We also show that for any $\epsilon=1/s^{O(1)}$ any non-adaptive ... more >>>

Xinyu Mao, Noam Mazor, Jiapeng Zhang

Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). The three major efficiency measures of these primitives are: seed length, number of calls to the one-way function, and adaptivity of these calls. Although a long ... more >>>

Oded Goldreich, Avi Wigderson

We study the relation between the query complexity of adaptive and non-adaptive testers in the dense graph model.

It has been known for a couple of decades that the query complexity of non-adaptive testers is at most quadratic in the query complexity of adaptive testers.

We show that ...
more >>>

Bruno Codenotti, Igor E. Shparlinski

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

Dung Nguyen, Alan Selman

We investigate autoreducibility properties of complete sets for $\cNEXP$ under different polynomial reductions.

Specifically, we show under some polynomial reductions that there is are complete sets for

$\cNEXP$ that are not autoreducible. We obtain the following results:

- There is a $\reduction{p}{tt}$-complete set for $\cNEXP$ that is not $\reduction{p}{btt}$-autoreducible.

more >>>

Shuichi Hirahara

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP: Several results suggest that black-box worst-case to average-case reductions are not likely to be used for reducing any worst-case problem outside coNP to a distributional NP problem.

This paper overcomes the barrier. We ... more >>>

Eric Allender, Jia Jiao, Meena Mahajan, V Vinay

We investigate the phenomenon of depth-reduction in commutative

and non-commutative arithmetic circuits. We prove that in the

commutative setting, uniform semi-unbounded arithmetic circuits of

logarithmic depth are as powerful as uniform arithmetic circuits of

polynomial degree; earlier proofs did not work in the ...
more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

Guillaume Lagarde, Guillaume Malod

In the setting of non-commutative arithmetic computations, we define a class of circuits that gener-

alize algebraic branching programs (ABP). This model is called unambiguous because it captures the

polynomials in which all monomials are computed in a similar way (that is, all the parse trees are iso-

morphic).

We ...
more >>>

Soren Riis, Meera Sitharam

The semantics of decision problems are always essentially independent of the

underlying representation. Thus the space of input data (under appropriate

indexing) is closed

under action of the symmetrical group $S_n$ (for a specific data-size)

and the input-output relation is closed under the action of $S_n$.

more >>>

Lijie Chen

Following the seminal work of [Williams, J. ACM 2014], in a recent breakthrough, [Murray and Williams, STOC 2018] proved that NQP (non-deterministic quasi-polynomial time) does not have polynomial-size ACC^0 circuits.

We strengthen the above lower bound to an average case one, by proving that for all constants c, ...
more >>>

Saikrishna Badrinarayanan, Yael Kalai, Dakshita Khurana, Amit Sahai, Daniel Wichs

We construct a delegation scheme for verifying non-deterministic computations, with complexity proportional only to the non-deterministic space of the computation. Specifi cally, letting $n$ denote the input length, we construct a delegation scheme for any language veri fiable in non-deterministic time and space $(T(n);S(n))$ with communication complexity $poly(S(n))$, verifi er ... more >>>

Yael Kalai, Dakshita Khurana

We construct non-interactive non-malleable commitments with respect to replacement, without setup in the plain model, under well-studied assumptions.

First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon>0$, under the following assumptions:

- Sub-exponential hardness of factoring or discrete ... more >>>

Tom Gur, Ron Rothblum

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

Zvika Brakerski, Justin Holmgren, Yael Tauman Kalai

We present an adaptive and non-interactive protocol for verifying arbitrary efficient computations in fixed polynomial time. Our protocol is computationally sound and can be based on any computational PIR scheme, which in turn can be based on standard polynomial-time cryptographic assumptions (e.g. the worst case hardness of polynomial-factor approximation of ... more >>>

Mikhail V. Vyugin, Vladimir Vyugin

Predictive complexity is a generalization of Kolmogorov complexity

which gives a lower bound to ability of any algorithm to predict

elements of a sequence of outcomes. A variety of types of loss

functions makes it interesting to study relations between corresponding

predictive complexities.

Non-linear inequalities between predictive complexity of ... more >>>

Ryan Williams

We prove a model-independent non-linear time lower bound for a slight generalization of the quantified Boolean formula problem (QBF). In particular, we give a reduction from arbitrary languages in alternating time t(n) to QBFs describable in O(t(n)) bits by a reasonable (polynomially) succinct encoding. The reduction works for many reasonable ... more >>>

Claude Crépeau, Nan Yang

In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call “contamination” by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new ... more >>>

Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan

We present the first explicit construction of a non-malleable code that can handle tampering functions that are bounded-degree polynomials.

Prior to our work, this was only known for degree-1 polynomials (affine tampering functions), due to Chattopadhyay and Li (STOC 2017). As a direct corollary, we obtain an explicit non-malleable ... more >>>

Eshan Chattopadhyay, David Zuckerman

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10} as an elegant generalization of the classical notions of error detection, where the corruption of a codeword is viewed as a tampering function acting on it. Informally, a non-malleable code with respect to a family of tampering functions $\mathcal{F}$ consists ... more >>>

Eshan Chattopadhyay, Xin Li

Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs as an elegant relaxation of error correcting codes, where the motivation is to handle more general forms of tampering while still providing meaningful guarantees. This has led to many elegant constructions and applications in cryptography. However, most works so far only ... more >>>

Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i.e.~$\mathsf{AC^0}$ tampering functions), our codes have codeword length $n = k^{1+o(1)}$ for a $k$-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay ... more >>>

Divesh Aggarwal, Yevgeniy Dodis, Shachar Lovett

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>

Gil Cohen

A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>>

Eshan Chattopadhyay, Xin Li

We present explicit constructions of non-malleable codes with respect to the following tampering classes. (i) Linear functions composed with split-state adversaries: In this model, the codeword is first tampered by a split-state adversary, and then the whole tampered codeword is further tampered by a linear function. (ii) Interleaved split-state adversary: ... more >>>

Eshan Chattopadhyay, Vipul Goyal, Xin Li

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami ... more >>>

Xin Li

Dodis and Wichs \cite{DW09} introduced the notion of a non-malleable extractor to study the problem of privacy amplification with an active adversary. A non-malleable extractor is a much stronger version of a strong extractor. Given a weakly-random string $x$ and a uniformly random seed $y$ as the inputs, the non-malleable ... more >>>

Gil Cohen

We construct non-malleable extractors with seed length $d = O(\log{n}+\log^{3}(1/\epsilon))$ for $n$-bit sources with min-entropy $k = \Omega(d)$, where $\epsilon$ is the error guarantee. In particular, the seed length is logarithmic in $n$ for $\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>>

Gil Cohen, Ran Raz, Gil Segev

Motivated by the classical problem of privacy amplification, Dodis and Wichs (STOC '09) introduced the notion of a non-malleable extractor, significantly strengthening the notion of a strong extractor. A non-malleable extractor is a function $nmExt : \{0,1\}^n \times \{0,1\}^d \rightarrow \{0,1\}^m$ that takes two inputs: a weak source $W$ and ... more >>>

Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either ... more >>>

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

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Let a program p on input a output b. We are looking for a

shorter program p' having the same property (p'(a)=b). In

addition, we want p' to be simple conditional to p (this

means that the conditional Kolmogorov complexity K(p'|p) is

negligible). In the present paper, we prove that ...
more >>>

Anindya De, Luca Trevisan, Madhur Tulsiani

We study the power of non-uniform attacks against one-way

functions and pseudorandom generators.

Fiat and Naor show that for every function

$f: [N]\to [N]$

there is an algorithm that inverts $f$ everywhere using

(ignoring lower order factors)

time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Richard J. Lipton, Anastasios Viglas

We discuss some connections between polynomial time and non-uniform, small depth circuits. A connection is shown with simulating deterministic time in small space. The well known result of Hopcroft, Paul and Valiant showing that space is more powerful than time can be improved, by making an assumption about the connection ... more >>>

Albert Atserias

We may believe SAT does not have small Boolean circuits.

But is it possible that some language with small circuits

looks indistiguishable from SAT to every polynomial-time

bounded adversary? We rule out this possibility. More

precisely, assuming SAT does not have small circuits, we

show that ...
more >>>

Abhishek Bhowmick, Shachar Lovett

The problem of constructing explicit functions which cannot be approximated by low degree polynomials has been extensively studied in computational complexity, motivated by applications in circuit lower bounds, pseudo-randomness, constructions of Ramsey graphs and locally decodable codes. Still, most of the known lower bounds become trivial for polynomials of ...
more >>>

Craig Gentry

We show that, for many noncommutative algebras A, the hardness of computing the determinant of matrices over A follows almost immediately from Barrington’s Theorem. Barrington showed how to express a NC1 circuit as a product program over any non-solvable group. We construct a simple matrix directly from Barrington’s product program ... more >>>

Vikraman Arvind, Pushkar Joglekar, Raja S

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and

$\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some

striking connections to classical formal language theory. Our main

results are the following:

(1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for ... more >>>

Markus Bläser

We consider the complexity of computing the determinant over arbitrary finite-dimensional algebras. We first consider the case that $A$ is fixed. We obtain the following dichotomy: If $A/rad(A)$ is noncommutative, then computing the determinant over $A$ is hard. ``Hard'' here means $\#P$-hard over fields of characteristic $0$ and $ModP_p$-hard over ... more >>>

John Hitchcock, Adewale Sekoni

The measure hypothesis is a quantitative strengthening of the P $\neq$ NP conjecture which asserts that NP is a nonnegligible subset of EXP. Cai, Sivakumar, and Strauss (1997) showed that the analogue of this hypothesis in P is false. In particular, they showed that NTIME[$n^{1/11}$] has measure 0 in P. ... more >>>

Toniann Pitassi, Morgan Shirley, Thomas Watson

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

Baris Aydinlioglu, Dieter van Melkebeek

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>

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

Motivated by strong Karp-Lipton collapse results in bounded arithmetic, Cook and Krajicek have recently introduced the notion of propositional proof systems with advice.

In this paper we investigate the following question: Do there exist polynomially bounded proof systems with advice for arbitrary languages?

Depending on the complexity of the ...
more >>>

Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas

Inspired by Nisan's characterization of noncommutative complexity (Nisan 1991), we study different notions of nonnegative rank, associated complexity measures and their link with monotone computations. In particular we answer negatively an open question of Nisan asking whether nonnegative rank characterizes monotone noncommutative complexity for algebraic branching programs. We also prove ... more >>>

Arman Fazeli, Shachar Lovett, Alex Vardy

A $t$-$(n,k,\lambda)$ design over $\mathbb{F}_q$ is a collection of $k$-dimensional subspaces of $\mathbb{F}_q^n$, ($k$-subspaces, for short), called blocks, such that each $t$-dimensional subspace of $\mathbb{F}_q^n$ is contained in exactly $\lambda$ blocks. Such $t$-designs over $\mathbb{F}_q$ are the $q$-analogs of conventional combinatorial designs. Nontrivial $t$-$(n,k,\lambda)$ designs over $\mathbb{F}_q$ are currently known ... more >>>

Michal Koucky

This paper initiates the study of $k$-catalytic branching programs, a nonuniform model of computation that is the counterpart to the uniform catalytic space model of Buhrman, Cleve, Koucky, Loff and Speelman (STOC 2014). A $k$-catalytic branching program computes $k$ boolean functions simultaneously on the same $n$-bit input. Each function has ... more >>>

John Hitchcock, Hadi Shafei

Nonuniformity is a central concept in computational complexity with powerful connections to circuit complexity and randomness. Nonuniform reductions have been used to study the isomorphism conjecture for NP and completeness for larger complexity classes. We study the power of nonuniform reductions for NP-completeness, obtaining both separations and upper bounds for ... more >>>

Moses Charikar, Konstantin Makarychev, Yury Makarychev

In this note we present an approximation algorithm for MAX 2SAT that given a (1 - epsilon) satisfiable instance finds an assignment of variables satisfying a 1 - O(sqrt{epsilon}) fraction of all constraints. This result is optimal assuming the Unique Games Conjecture.

The best previously known result, due ... more >>>

U. Faigle, W. Kern, M. Streng

We show that, for fixed dimension $n$, the approximation of

inner and outer $j$-radii of polytopes in ${\Re}^n$, endowed

with the Euclidean norm, is polynomial.

Stasys Jukna

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... more >>>

Oded Goldreich

In 1984, Leonid Levin has initiated a theory of average-case complexity.

We provide an exposition of the basic definitions suggested by Levin,

and discuss some of the considerations underlying these definitions.

Stasys Jukna

A monotone Boolean $(\lor,\land)$ circuit $F$ computing a Boolean function $f$ is a read-$k$ circuit if the polynomial produced (purely syntactically) by the arithmetic $(+,\times)$ version of $F$ has the property that for every prime implicant of $f$, the polynomial contains a monomial with the same set of variables, each ... more >>>

Tomas Jirotka

The thesis summarizes known results in the field of NP search problems. We discuss the complexity of integer factoring in detail, and we propose new results which place the problem in known classes and aim to separate it from PLS in some sense. Furthermore, we define several new search problems.

more >>>Lance Fortnow, Adam Klivans

We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>>

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe?

I survey proposals including soap bubbles, protein folding, quantum

computing, quantum advice, quantum adiabatic algorithms,

quantum-mechanical nonlinearities, hidden variables, relativistic time

dilation, analog computing, Malament-Hogarth spacetimes, quantum

gravity, closed timelike curves, and "anthropic computing." The ...
more >>>

Titus Dose, Christian Glaßer

The article investigates the relation between three well-known hypotheses.

1) Hunion: the union of disjoint complete sets for NP is complete for NP

2) Hopps: there exist optimal propositional proof systems

3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:

a) The hypotheses are pairwise independent ...
more >>>

Harry Buhrman, John Hitchcock

We show that hard sets S for NP must have exponential density, i.e. |S<sub>=n</sub>| ≥ 2<sup>n<sup>ε</sup></sup> for some ε > 0 and infinitely many n, unless coNP ⊆ NP\poly and the polynomial-time hierarchy collapses. This result holds for Turing reductions that make n<sup>1-ε</sup> queries.

In addition we study the instance ... more >>>

Joshua Grochow

Mahaney's Theorem states that, assuming P $\neq$ NP, no NP-hard set can have a polynomially bounded number of yes-instances at each input length. We give an exposition of a very simple unpublished proof of Manindra Agrawal whose ideas appear in Agrawal-Arvind ("Geometric sets of low information content," Theoret. Comp. Sci., ... more >>>

Yongge Wang

We show that the class of sets which can be polynomial

time truth table reduced to some $p$-superterse sets has

$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard

for $E$. Also we give a partial affirmative answer to

the conjecture by Beigel, Kummer and ...
more >>>

Subhash Khot, Dana Moshkovitz

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Can we design efficient algorithms for finding fast algorithms? This question is captured by various circuit minimization problems, and algorithms for the corresponding tasks have significant practical applications. Following the work of Cook and Levin in the early 1970s, a central question is whether minimizing the circuit size of an ... more >>>

Amey Bhangale

We give very short and simple proofs of the following statements: Given a $2$-colorable $4$-uniform hypergraph on $n$ vertices,

(1) It is NP-hard to color it with $\log^\delta n$ colors for some $\delta>0$.

(2) It is $quasi$-NP-hard to color it with $O\left({\log^{1-o(1)} n}\right)$ colors.

In terms of ... more >>>

Shuichi Hirahara

A long-standing open question in computational learning theory is to prove NP-hardness of learning efficient programs, the setting of which is in between proper learning and improper learning. Ko (COLT'90, SICOMP'91) explicitly raised this open question and demonstrated its difficulty by proving that there exists no relativizing proof of NP-hardness ... more >>>

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

The Minimum Circuit Size Problem (MCSP) asks for the size of the smallest boolean circuit that computes a given truth table. It is a prominent problem in NP that is believed to be hard, but for which no proof of NP-hardness has been found. A significant number of works have ... more >>>

Venkata Gandikota, Badih Ghazi, Elena Grigorescu

Establishing the complexity of {\em Bounded Distance Decoding} for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when ... more >>>

Tomoyuki Yamakami, Andrew Chi-Chih Yao

Adleman, DeMarrais, and Huang introduced the

nondeterministic quantum polynomial-time complexity class NQP as an

analogue of NP. It is known that, with restricted amplitudes, NQP is

characterized in terms of the classical counting complexity class

C_{=}P. In this paper we prove that, with unrestricted amplitudes,

NQP indeed coincides with the ...
more >>>

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

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph $G$ can be reversibly pebbled in time $t$ and space $s$ if and only if there is a Nullstellensatz refutation of the pebbling formula over $G$ in size $t+1$ ... more >>>

Jacobo Toran, Florian Wörz

We show that the number of variables and the quantifier depth needed to distinguish a pair of graphs by first-order logic sentences exactly match the complexity measures of clause width and positive depth needed to refute the corresponding graph isomorphism formula in propositional narrow resolution.

Using this connection, we ... more >>>