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

**C**

__
TR98-070
| 7th December 1998
__

Rüdiger Reischuk#### Can Large Fanin Circuits Perform Reliable Computations in the Presence of Noise?

__
TR16-059
| 14th April 2016
__

Alon Rosen, Gil Segev, Ido Shahaf#### Can PPAD Hardness be Based on Standard Cryptographic Assumptions?

Revisions: 2

__
TR99-013
| 28th May 1999
__

Oded Goldreich, Amit Sahai, Salil Vadhan#### Can Statistical Zero Knowledge be made Non-Interactive? or On the Relationship of SZK and NISZK

__
TR14-142
| 1st November 2014
__

Subhash Khot, Dana Moshkovitz#### Candidate Lasserre Integrality Gap For Unique Games

__
TR00-090
| 3rd December 2000
__

Oded Goldreich#### Candidate One-Way Functions Based on Expander Graphs

__
TR20-141
| 11th September 2020
__

Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan#### Candidate Tree Codes via Pascal Determinant Cubes

__
TR14-033
| 10th March 2014
__

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

__
TR04-106
| 19th November 2004
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Canonical Disjoint NP-Pairs of Propositional Proof Systems

__
TR20-110
| 22nd July 2020
__

Leonid Gurvits, Jonathan Leake#### Capacity Lower Bounds via Productization

Revisions: 2

__
TR13-118
| 2nd September 2013
__

Mahdi Cheraghchi, Venkatesan Guruswami#### Capacity of Non-Malleable Codes

__
TR19-147
| 31st October 2019
__

Gil Cohen, Shahar Samocha#### Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 2
,
Comments: 1

__
TR20-056
| 17th April 2020
__

James Cook, Ian Mertz#### Catalytic Approaches to the Tree Evaluation Problem

__
TR09-054
| 7th June 2009
__

Emanuele Viola, Emanuele Viola#### Cell-Probe Lower Bounds for Prefix Sums

__
TR17-066
| 20th April 2017
__

Josh Alman, Joshua Wang, Huacheng Yu#### Cell-Probe Lower Bounds from Online Communication Complexity

Revisions: 1

__
TR22-143
| 7th November 2022
__

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny#### Certificate games

Revisions: 1

__
TR23-020
| 3rd March 2023
__

Scott Aaronson, Shih-Han Hung#### Certified Randomness from Quantum Supremacy

__
TR12-153
| 9th November 2012
__

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally#### Certifying Equality With Limited Interaction

Revisions: 1

__
TR12-102
| 16th August 2012
__

Swastik Kopparty, Srikanth Srinivasan#### Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ circuits, with applications

__
TR03-030
| 27th February 2003
__

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich#### Certifying Unsatisfiability of Random 2k-SAT Formulas using Approximation Techniques

__
TR13-119
| 2nd September 2013
__

Emanuele Viola#### Challenges in computational lower bounds

__
TR06-040
| 6th March 2006
__

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu#### Channel assignment in wireless networks and classification of minimum graph homomorphism

__
TR19-081
| 31st May 2019
__

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak#### Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation

Revisions: 1

__
TR16-076
| 27th April 2016
__

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma#### Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Revisions: 2

__
TR09-082
| 20th September 2009
__

T.C. Vijayaraghavan#### Characterization of ModL using Prime Modulus.

Revisions: 1

__
TR20-143
| 16th September 2020
__

Shuichi Hirahara#### Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity

__
TR22-084
| 2nd June 2022
__

Yanyi Liu, Rafael Pass#### Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

__
TR18-121
| 20th June 2018
__

Justin Holmgren, Lisa Yang#### Characterizing Parallel Repetition of Non-Signaling Games: Counterexamples and a Dichotomy Theorem

__
TR15-134
| 19th August 2015
__

Fu Li, Iddo Tzameret, Zhengyu Wang#### Characterizing Propositional Proofs as Non-Commutative Formulas

__
TR11-141
| 2nd November 2011
__

Salil Vadhan, Colin Jia Zheng#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR09-081
| 27th August 2009
__

Olaf Beyersdorff, Zenon Sadowski#### Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

__
TR22-166
| 23rd November 2022
__

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu#### Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

__
TR09-009
| 18th December 2008
__

T.C. Vijayaraghavan#### Checking Equality of Matroid Linear Representations and the Cycle Matching Problem

Revisions: 2

__
TR98-062
| 28th October 1998
__

Oded Goldreich, Dana Ron, Madhu Sudan#### Chinese Remaindering with Errors

Revisions: 4
,
Comments: 1

__
TR18-004
| 3rd January 2018
__

Aayush Ojha, Raghunath Tewari#### Circuit Complexity of Bounded Planar Cutwidth Graph Matching

__
TR98-056
| 31st August 1998
__

Anna Bernasconi, Igor E. Shparlinski#### Circuit Complexity of Testing Square-Free Numbers

__
TR14-052
| 14th April 2014
__

Joshua Grochow, Toniann Pitassi#### Circuit complexity, proof complexity, and polynomial identity testing

__
TR18-192
| 12th November 2018
__

Alexander Golovnev, Alexander Kulikov#### Circuit Depth Reductions

Revisions: 3

__
TR04-004
| 13th January 2004
__

Ramamohan Paturi, Pavel Pudlak#### Circuit lower bounds and linear codes

__
TR13-037
| 15th March 2013
__

Alexander Knop#### Circuit Lower Bounds for Heuristic MA

Revisions: 2

__
TR19-022
| 23rd February 2019
__

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis#### Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Revisions: 1

__
TR07-005
| 17th January 2007
__

Rahul Santhanam#### Circuit Lower Bounds for Merlin-Arthur Classes

__
TR17-188
| 22nd December 2017
__

Cody Murray, Ryan Williams#### Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

__
TR13-077
| 14th May 2013
__

Ján Pich#### Circuit Lower Bounds in Bounded Arithmetics

__
TR09-122
| 23rd November 2009
__

Vikraman Arvind, Srikanth Srinivasan#### Circuit Lower Bounds, Help Functions, and the Remote Point Problem

__
TR99-045
| 16th November 1999
__

Valentine Kabanets, Jin-Yi Cai#### Circuit Minimization Problem

__
TR16-022
| 22nd February 2016
__

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

__
TR02-066
| 24th October 2002
__

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay#### Circuits on Cylinders

__
TR22-050
| 12th April 2022
__

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena#### Circuits Resilient to Short-Circuit Errors

__
TR14-020
| 18th February 2014
__

Pavel Hrubes, Anup Rao#### Circuits with Medium Fan-In

Revisions: 1

__
TR12-145
| 31st October 2012
__

Cenny Wenner#### Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four

__
TR22-036
| 10th March 2022
__

Agnes Schleitzer, Olaf Beyersdorff#### Classes of Hard Formulas for QBF Resolution

Revisions: 1

__
TR12-023
| 19th March 2012
__

Sophie Laplante, Virginie Lerays, Jérémie Roland#### Classical and quantum partition bound and detector inefficiency

__
TR14-136
| 17th October 2014
__

Viliam Geffert, Abuzer Yakaryilmaz#### Classical Automata on Promise Problems

__
TR07-058
| 9th June 2007
__

Dmytro Gavinsky#### Classical Interaction Cannot Replace a Quantum Message

Revisions: 1

__
TR02-062
| 19th November 2002
__

Andrew Chi-Chih Yao#### Classical Physics and the Church-Turing Thesis

__
TR05-016
| 13th January 2005
__

Tomas Feder, Daniel Ford#### Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

__
TR21-107
| 20th July 2021
__

igor razgon#### Classification of OBDD size for monotone 2-CNFs

__
TR01-082
| 24th September 2001
__

Tsuyoshi Morioka#### Classification of Search Problems and Their Definability in Bounded Arithmetic

__
TR21-011
| 13th February 2021
__

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy#### Classification of the streaming approximability of Boolean CSPs

Revisions: 4
,
Comments: 1

__
TR05-102
| 13th September 2005
__

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert#### Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms

__
TR12-039
| 17th April 2012
__

Stasys Jukna#### Clique Problem, Cutting Plane Proofs, and Communication Complexity

__
TR08-092
| 26th August 2008
__

Scott Aaronson, John Watrous#### Closed Timelike Curves Make Quantum and Classical Computing Equivalent

__
TR19-037
| 5th March 2019
__

Chi-Ning Chou, Mrinal Kumar, Noam Solomon#### Closure of VP under taking factors: a short and simple proof

Revisions: 1

__
TR95-035
| 30th June 1995
__

Richard Beigel#### Closure Properties of GapP and #P

__
TR06-160
| 17th December 2006
__

Tomas Feder, Phokion G. Kolaitis#### Closures and dichotomies for quantified constraints

__
TR99-035
| 6th July 1999
__

Leonard Schulman#### Clustering for Edge-Cost Minimization

__
TR13-031
| 22nd February 2013
__

Irit Dinur, Elazar Goldenberg#### Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

__
TR21-112
| 30th July 2021
__

Vikraman Arvind, Venkatesan Guruswami#### CNF Satisfiability in a Subspace and Related Problems

__
TR08-060
| 10th April 2008
__

James R. Lee, Prasad Raghavendra#### Coarse Differentiation and Multi-flows in Planar Graphs

__
TR10-077
| 26th April 2010
__

Venkatesan Guruswami, Adam Smith#### Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate

__
TR20-156
| 22nd October 2020
__

Sankeerth Rao Karingula, Shachar Lovett#### Codes over integers, and the singularity of random matrices with large entries

Revisions: 1

__
TR15-106
| 22nd June 2015
__

Itay Berman, Iftach Haitner, Aris Tentes#### Coin Flipping of Any Constant Bias Implies One-Way Functions

Revisions: 1

__
TR19-087
| 10th June 2019
__

Rohit Agrawal#### Coin Theorems and the Fourier Expansion

Revisions: 1

__
TR17-160
| 29th October 2017
__

Eli Ben-Sasson, Eden Saig#### Collaborative Discovery: A study of Guru-follower dynamics

Revisions: 1

__
TR13-131
| 17th September 2013
__

Nikhil Balaji, Samir Datta#### Collapsing Exact Arithmetic Hierarchies

Revisions: 1

__
TR16-178
| 11th November 2016
__

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price#### Collision-based Testers are Optimal for Uniformity and Closeness

Comments: 1

__
TR96-042
| 26th July 1996
__

Oded Goldreich, Shai Halevi#### Collision-Free Hashing from Lattice Problems

__
TR22-017
| 15th February 2022
__

Ron D. Rothblum, Prashant Nalini Vasudevan#### Collision-Resistance from Multi-Collision-Resistance

Revisions: 2

__
TR94-009
| 12th December 1994
__

Noga Alon, Raphael Yuster, Uri Zwick#### Color-coding

__
TR09-093
| 8th October 2009
__

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

__
TR04-070
| 22nd June 2004
__

Leonid Gurvits#### Combinatorial and algorithmic aspects of hyperbolic polynomials

__
TR07-115
| 19th November 2007
__

Or Meir#### Combinatorial Construction of Locally Testable Codes

Revisions: 1

__
TR10-184
| 19th November 2010
__

Manjish Pal#### Combinatorial Geometry of Graph Partitioning - I

__
TR00-026
| 11th April 2000
__

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin#### Combinatorial Interpretation of Kolmogorov Complexity

__
TR12-017
| 1st March 2012
__

Venkatesan Guruswami, Srivatsan Narayanan#### Combinatorial limitations of a strong form of list decoding

Revisions: 1

__
TR15-007
| 8th January 2015
__

Jonah Brown-Cohen, Prasad Raghavendra#### Combinatorial Optimization Algorithms via Polymorphisms

__
TR11-104
| 3rd August 2011
__

Or Meir#### Combinatorial PCPs with efficient verifiers

Revisions: 3

__
TR13-134
| 25th September 2013
__

Or Meir#### Combinatorial PCPs with Short Proofs

__
TR97-056
| 1st December 1997
__

Oded Goldreich#### Combinatorial Property Testing (a survey).

Comments: 1

__
TR98-041
| 27th July 1998
__

Stasys Jukna#### Combinatorics of Monotone Computations

__
TR18-059
| 6th April 2018
__

Joshua Brakensiek, Venkatesan Guruswami#### Combining LPs and Ring Equations via Structured Polymorphisms

Revisions: 1

__
TR09-003
| 6th January 2009
__

Alex Hertel, Alasdair Urquhart#### Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete

__
TR22-140
| 10th October 2022
__

Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry#### Commitments to Quantum States

Revisions: 1

__
TR13-056
| 30th March 2013
__

Gábor Braun, Sebastian Pokutta#### Common information and unique disjointness

Revisions: 5

__
TR15-156
| 21st September 2015
__

Tim Roughgarden#### Communication Complexity (for Algorithm Designers)

__
TR01-062
| 9th September 2001
__

Moni Naor, Kobbi Nissim#### Communication Complexity and Secure Function Evaluation

__
TR22-096
| 8th July 2022
__

Mika Göös, Siddhartha Jain#### Communication Complexity of Collision

__
TR17-061
| 3rd April 2017
__

Anat Ganor, Karthik C. S.#### Communication Complexity of Correlated Equilibrium in Two-Player Games

__
TR15-087
| 30th May 2015
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Communication Complexity of Permutation-Invariant Functions

__
TR14-055
| 17th April 2014
__

Mika Göös, Thomas Watson#### Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

__
TR16-170
| 3rd November 2016
__

Thomas Watson#### Communication Complexity of Statistical Distance

Revisions: 1

__
TR07-072
| 2nd July 2007
__

Alexander A. Sherstov#### Communication Complexity under Product and Nonproduct Distributions

__
TR20-054
| 22nd April 2020
__

Marshall Ball, Oded Goldreich, Tal Malkin#### Communication Complexity with Defective Randomness

Revisions: 3

__
TR16-148
| 23rd September 2016
__

Thomas Watson#### Communication Complexity with Small Advantage

Revisions: 1

__
TR13-084
| 8th June 2013
__

Shachar Lovett#### Communication is bounded by root of rank

Revisions: 1

__
TR13-005
| 2nd January 2013
__

Alexander A. Sherstov#### Communication Lower Bounds Using Directional Derivatives

__
TR08-057
| 14th May 2008
__

Alexander A. Sherstov#### Communication Lower Bounds Using Dual Polynomials

__
TR15-064
| 19th April 2015
__

Ilan Komargodski, Pravesh Kothari, Madhu Sudan#### Communication with Contextual Uncertainty

Revisions: 1

__
TR14-153
| 14th November 2014
__

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan#### Communication with Imperfectly Shared Randomness

Revisions: 2

__
TR18-150
| 27th August 2018
__

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan#### Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation

__
TR15-035
| 22nd February 2015
__

Sunil K S, Balagopal Komarath, Jayalal Sarma#### Comparator Circuits over Finite Bounded Posets

Revisions: 1

__
TR20-171
| 12th November 2020
__

Russell Impagliazzo, Sam McGuire#### Comparing computational entropies below majority (or: When is the dense model theorem false?)

__
TR98-063
| 4th November 1998
__

Oded Goldreich, Salil Vadhan#### Comparing Entropies in Statistical Zero-Knowledge with Applications to the Structure of SZK

__
TR06-039
| 28th February 2006
__

John Hitchcock, A. Pavan#### Comparing Reductions to NP-Complete Sets

__
TR14-143
| 3rd November 2014
__

Ronald de Haan, Stefan Szeider#### Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

__
TR11-122
| 14th September 2011
__

Gillat Kol, Ran Raz#### Competing Provers Protocols for Circuit Evaluation

__
TR17-136
| 10th September 2017
__

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo#### Complete Classification of Generalized Santha-Vazirani Sources

__
TR16-171
| 3rd November 2016
__

Daniel Minahan, Ilya Volkovich#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

__
TR06-036
| 7th February 2006
__

Tobias Riege, Jörg Rothe#### Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems

Revisions: 1

__
TR03-060
| 7th September 2003
__

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen#### Completeness in Two-Party Secure Computation - A Computational View

__
TR97-057
| 3rd November 1997
__

Petr Savicky#### Complexity and Probability of some Boolean Formulas

__
TR16-039
| 15th March 2016
__

Adam Bouland, Laura Mancinska, Xue Zhang#### Complexity Classification of Two-Qubit Commuting Hamiltonians

__
TR11-093
| 8th June 2011
__

Pinyan Lu#### Complexity Dichotomies of Counting Problems

__
TR97-046
| 3rd October 1997
__

Alexander Barg#### Complexity Issues in Coding Theory

__
TR11-138
| 24th October 2011
__

Guy Moshkovitz#### Complexity Lower Bounds through Balanced Graph Properties

__
TR13-125
| 11th September 2013
__

Venkatesan Guruswami, Euiwoong Lee#### Complexity of approximating CSP with Balance / Hard Constraints

__
TR16-031
| 7th March 2016
__

Titus Dose#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

__
TR08-044
| 2nd April 2008
__

Miki Hermann, Reinhard Pichler#### Complexity of Counting the Optimal Solutions

__
TR15-174
| 18th October 2015
__

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov#### Complexity of distributions and average-case hardness

__
TR04-035
| 10th April 2004
__

Scott Contini, Ernie Croot, Igor E. Shparlinski#### Complexity of Inverting the Euler Function

__
TR19-002
| 31st December 2018
__

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii#### Complexity of Linear Operators

__
TR15-018
| 31st January 2015
__

Eric Allender, Ian Mertz#### Complexity of Regular Functions

Revisions: 1

__
TR01-103
| 14th December 2001
__

Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik#### Complexity of semi-algebraic proofs

Revisions: 3

__
TR02-068
| 10th December 2002
__

Tobias Riege, Jörg Rothe#### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

Revisions: 2

__
TR18-039
| 23rd February 2018
__

Md Lutfar Rahman, Thomas Watson#### Complexity of Unordered CNF Games

Revisions: 1

__
TR94-013
| 12th December 1994
__

Pavel Pudlak#### Complexity Theory and Genetics

__
TR18-001
| 2nd January 2018
__

Tim Roughgarden#### Complexity Theory, Game Theory, and Economics

Revisions: 2

__
TR16-200
| 18th December 2016
__

Scott Aaronson, Lijie Chen#### Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Revisions: 1

__
TR17-014
| 23rd January 2017
__

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay#### Composition and Simulation Theorems via Pseudo-random Properties

__
TR09-042
| 5th May 2009
__

Irit Dinur, Prahladh Harsha#### Composition of low-error 2-query PCPs using decodable PCPs

__
TR11-070
| 1st May 2011
__

Eli Ben-Sasson, Michael Viderman#### Composition of semi-LTCs by two-wise Tensor Products

__
TR03-065
| 19th June 2003
__

Wee, Hoeteck#### Compressibility Lower Bounds in Oracle Settings

__
TR15-092
| 31st May 2015
__

Yael Tauman Kalai, Ilan Komargodski#### Compressing Communication in Distributed Protocols

Revisions: 2

__
TR16-081
| 20th May 2016
__

Alexander A. Sherstov#### Compressing interactive communication under product distributions

__
TR13-024
| 7th February 2013
__

Valentine Kabanets, Antonina Kolokolova#### Compression of Boolean Functions

__
TR05-012
| 17th January 2005
__

Luca Trevisan, Salil Vadhan, David Zuckerman#### Compression of Samplable Sources

__
TR08-031
| 14th January 2008
__

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers#### Computability and Complexity in Self-Assembly

__
TR16-146
| 18th September 2016
__

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini#### Computability Theory of Closed Timelike Curves

__
TR03-081
| 10th October 2003
__

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini#### Computation of the Lov\'asz Theta Function for Circulant Graphs

__
TR21-001
| 1st January 2021
__

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena#### Computation Over the Noisy Broadcast Channel with Malicious Parties

__
TR20-067
| 30th April 2020
__

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin#### Computational and proof complexity of partial string avoidability

__
TR06-137
| 13th November 2006
__

Prashant Joshi, Eduardo D. Sontag#### Computational aspects of feedback in neural circuits

__
TR11-114
| 8th August 2011
__

Varun Kanade#### Computational Bottlenecks for Evolvability

__
TR94-007
| 12th December 1994
__

Oded Goldreich, Rafail Ostrovsky, Erez Petrank#### Computational Complexity and Knowledge Complexity

__
TR06-159
| 3rd October 2006
__

Predrag Tosic#### Computational Complexity of Some Enumeration Problems About Uniformly Sparse Boolean Network Automata

__
TR04-111
| 30th November 2004
__

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott#### Computational Complexity of Some Restricted Instances of 3SAT

__
TR02-014
| 10th December 2001
__

Klaus Weihrauch#### Computational Complexity on Computable Metric Spaces

Revisions: 1

__
TR12-009
| 28th November 2011
__

Prabhu Manyem, Julien Ugon#### Computational Complexity, NP Completeness and Optimization Duality: A Survey

__
TR96-067
| 20th December 1996
__

Oded Goldreich, Bernd Meyer#### Computational Indistinguishability -- Algorithms vs. Circuits.

__
TR98-017
| 29th March 1998
__

Oded Goldreich, Madhu Sudan#### Computational Indistinguishability: A Sample Hierarchy.

__
TR97-028
| 12th July 1997
__

Scott E. Decatur, Oded Goldreich, Dana Ron#### Computational Sample Complexity

__
TR18-071
| 15th April 2018
__

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak#### Computational Two-Party Correlation

Revisions: 1

__
TR15-042
| 30th March 2015
__

Ilya Volkovich#### Computations beyond Exponentiation Gates and Applications

__
TR07-067
| 22nd May 2007
__

Paul Spirakis, haralampos tsaknakis#### Computing 1/3-approximate Nash equilibria of bimatrix games in polynomial time.

Revisions: 2

__
TR12-126
| 23rd September 2012
__

Shiva Kintali, Sinziana Munteanu#### Computing Bounded Path Decompositions in Logspace

__
TR02-052
| 3rd September 2002
__

Vince Grolmusz#### Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Revisions: 1

__
TR15-153
| 21st September 2015
__

Tim Roughgarden#### Computing Equilibria: A Computational Complexity Perspective

__
TR20-092
| 16th June 2020
__

Ashish Dwivedi, Nitin Saxena#### Computing Igusa's local zeta function of univariates in deterministic polynomial-time

__
TR16-158
| 9th October 2016
__

Alexander Kulikov, Vladimir Podolskii#### Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates

__
TR06-023
| 7th February 2006
__

Xi Chen, Xiaotie Deng, Shang-Hua Teng#### Computing Nash Equilibria: Approximation and Smoothed Complexity

__
TR14-106
| 9th August 2014
__

Craig Gentry#### Computing on the edge of chaos: Structure and randomness in encrypted computation

__
TR11-094
| 20th June 2011
__

Shachar Lovett#### Computing polynomials with few multiplications

__
TR16-179
| 15th November 2016
__

Avishay Tal#### Computing Requires Larger Formulas than Approximating

__
TR96-027
| 20th February 1996
__

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

__
TR94-025
| 12th December 1994
__

David P. Dobkin, Dimitrios Gunopulos#### Computing the Maximum Bichromatic Discrepancy with applications to Computer Graphics and Machine Learning

__
TR18-020
| 30th January 2018
__

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari#### Computing the maximum using $(\min, +)$ formulas

Comments: 1

__
TR14-053
| 15th April 2014
__

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman#### Computing with a full memory: Catalytic space

Revisions: 1

__
TR08-054
| 13th May 2008
__

Venkatesan Guruswami, Atri Rudra#### Concatenated codes can achieve list-decoding capacity

__
TR07-002
| 8th November 2006
__

Moti Yung, Yunlei Zhao#### Concurrent Knowledge-Extraction in the Public-Key Model

Comments: 2

__
TR06-095
| 25th July 2006
__

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti#### Concurrent Non-Malleable Witness Indistinguishability and its Applications

Revisions: 1

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

__
TR01-091
| 27th November 2001
__

Oded Goldreich#### Concurrent Zero-Knowledge With Timing, Revisited

__
TR21-026
| 23rd February 2021
__

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep#### Conditional Dichotomy of Boolean Ordered Promise CSPs

__
TR17-189
| 25th December 2017
__

Benny Applebaum, Barak Arkis#### Conditional Disclosure of Secrets and $d$-Uniform Secret Sharing with Constant Information Rate

Revisions: 1

__
TR17-038
| 23rd February 2017
__

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan#### Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations

Revisions: 1

__
TR05-039
| 13th April 2005
__

Irit Dinur, Elchanan Mossel, Oded Regev#### Conditional Hardness for Approximate Coloring

__
TR09-125
| 24th November 2009
__

David Steurer, Nisheeth Vishnoi#### Connections Between Unique Games and Multicut

__
TR19-077
| 30th May 2019
__

Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek#### Consistency of circuit lower bounds with bounded theories

__
TR16-197
| 7th December 2016
__

Igor Carboni Oliveira, Rahul Santhanam#### Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness

__
TR20-183
| 6th December 2020
__

Rahul Ilango#### Constant Depth Formula and Partial Function Versions of MCSP are Hard

__
TR13-085
| 13th June 2013
__

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth#### Constant rate PCPs for circuit-SAT with sublinear query complexity

__
TR03-025
| 14th April 2003
__

Kristoffer Arnsfelt Hansen#### Constant width planar computation characterizes ACC0

__
TR05-087
| 9th August 2005
__

Alexander Healy, Emanuele Viola#### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

__
TR22-116
| 17th August 2022
__

Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii#### Constant-Depth Sorting Networks

__
TR18-133
| 26th July 2018
__

Emanuele Viola#### Constant-error pseudorandomness proofs from hardness require majority

Revisions: 1

__
TR15-197
| 7th December 2015
__

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Constant-rate coding for multiparty interactive communication is impossible

__
TR17-095
| 26th May 2017
__

Ran Gelles, Yael Tauman Kalai#### Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks

__
TR05-048
| 11th April 2005
__

Moti Yung, Yunlei Zhao#### Constant-Round Concurrently-Secure rZK in the (Real) Bare Public-Key Model

Revisions: 3

__
TR18-069
| 14th April 2018
__

Oded Goldreich, Guy Rothblum#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

__
TR16-061
| 17th April 2016
__

Omer Reingold, Ron Rothblum, Guy Rothblum#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 2

__
TR11-003
| 10th January 2011
__

Yehuda Lindell#### Constant-Round Zero-Knowledge Proofs of Knowledge

Revisions: 1

__
TR05-005
| 20th December 2004
__

Tomas Feder#### Constraint Satisfaction on Finite Groups with Near Subgroups

__
TR08-008
| 8th February 2008
__

Venkatesan Guruswami, Prasad Raghavendra#### Constraint Satisfaction over a Non-Boolean Domain: Approximation algorithms and Unique-Games hardness

Revisions: 1

__
TR07-055
| 22nd May 2007
__

Oliver Kullmann#### Constraint satisfaction problems in clausal form: Autarkies and minimal unsatisfiability

Revisions: 1

__
TR06-021
| 10th February 2006
__

Tomas Feder#### Constraint satisfaction: a personal perspective

__
TR96-064
| 11th December 1996
__

Sanjeev Khanna, Madhu Sudan, Luca Trevisan#### Constraint satisfaction: The approximability of minimization problems.

__
TR12-114
| 15th July 2012
__

Mikhail Anokhin#### Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption

Revisions: 5

__
TR14-140
| 31st October 2014
__

Hong Van Le#### Constructing elusive functions with help of evaluation mappings

__
TR18-212
| 26th December 2018
__

Prerona Chatterjee, Ramprasad Saptharishi#### Constructing Faithful Homomorphisms over Fields of Finite Characteristic

Revisions: 1

__
TR13-129
| 17th September 2013
__

Adam Klivans, Pravesh Kothari, Igor Oliveira#### Constructing Hard Functions from Learning Algorithms

Revisions: 1

__
TR20-192
| 27th December 2020
__

Oded Goldreich, Avi Wigderson#### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

__
TR15-019
| 3rd February 2015
__

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira#### Constructing Near Spanning Trees with Few Local Inspections

__
TR05-143
| 29th November 2005
__

Parikshit Gopalan#### Constructing Ramsey Graphs from Boolean Function Representations

__
TR01-002
| 6th December 2000
__

Venkatesan Guruswami#### Constructions of Codes from Number Fields

__
TR05-155
| 10th December 2005
__

Amir Shpilka#### Constructions of low-degree and error-correcting epsilon-biased sets

__
TR98-055
| 4th September 1998
__

Luca Trevisan#### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

Comments: 1

__
TR10-072
| 19th April 2010
__

Russell Impagliazzo, Valentine Kabanets#### Constructive Proofs of Concentration Bounds

__
TR21-159
| 15th November 2021
__

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams#### Constructive Separations and Their Consequences

__
TR08-047
| 17th March 2008
__

Vijay V. Vazirani, Wang Lei#### Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models

__
TR09-136
| 9th December 2009
__

Michael Burr, Felix Krahmer, Chee Yap#### Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique

__
TR20-080
| 19th May 2020
__

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang#### Continuous LWE

Revisions: 1

__
TR18-170
| 4th October 2018
__

Nicola Galesi, Navid Talebanfard, Jacobo Toran#### Cops-Robber games and the resolution of Tseitin formulas

__
TR12-172
| 8th December 2012
__

Mahdi Cheraghchi, Anna Gal, Andrew Mills#### Correctness and Corruption of Locally Decodable Codes

Revisions: 1

__
TR22-142
| 3rd November 2022
__

Emanuele Viola#### Correlation bounds against polynomials

__
TR14-184
| 29th December 2014
__

Ruiwen Chen, Valentine Kabanets#### Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

__
TR15-122
| 29th July 2015
__

Shiteng Chen, Periklis Papakonstantinou#### Correlation lower bounds from correlation upper bounds

__
TR11-029
| 6th March 2011
__

Hamed Hatami, Shachar Lovett#### Correlation testing for affine invariant properties on $\mathbb{F}_p^n$ in the high error regime

Revisions: 1

__
TR18-134
| 24th July 2018
__

Tali Kaufman, David Mass#### Cosystolic Expanders over any Abelian Group

__
TR18-046
| 9th March 2018
__

Oded Goldreich, Guy Rothblum#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

__
TR19-033
| 20th February 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

__
TR10-101
| 25th June 2010
__

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer#### Counting Classes and the Fine Structure between NC$^1$ and L.

__
TR05-091
| 11th August 2005
__

Predrag Tosic#### Counting Fixed Points and Gardens of Eden of Sequential Dynamical Systems on Planar Bipartite Graphs

Revisions: 1

__
TR97-034
| 3rd September 1997
__

Jui-Lin Lee#### Counting in uniform $TC^0$

__
TR10-103
| 28th June 2010
__

Andreas Krebs, Nutan Limaye, Meena Mahajan#### Counting paths in VPA is complete for \#NC$^1$

__
TR09-083
| 24th September 2009
__

Dana Ron, Mira Gonen, Yuval Shavitt#### Counting Stars and Other Small Subgraphs in Sublinear Time

__
TR20-177
| 12th October 2020
__

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira#### Counting Subgraphs in Degenerate Graphs

__
TR14-079
| 11th June 2014
__

Simon Straub, Thomas Thierauf, Fabian Wagner#### Counting the Number of Perfect Matchings in $K_5$-free Graphs

__
TR04-011
| 16th January 2004
__

Christian Glaßer#### Counting with Counterfree Automata

__
TR19-180
| 6th December 2019
__

Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi#### Covering Codes for Insertions and Deletions

Revisions: 1

__
TR12-088
| 7th July 2012
__

Irit Dinur, Gillat Kol#### Covering CSPs

__
TR22-182
| 16th December 2022
__

Prahladh Harsha, Tulasi mohan Molli, A. Shankar#### Criticality of AC0-Formulae

Revisions: 1

__
TR17-047
| 10th March 2017
__

Kasper Green Larsen, Omri Weinstein, Huacheng Yu#### Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds

__
TR04-101
| 28th September 2004
__

Miroslav Chlebik, Janka Chlebíková#### Crown reductions for the Minimum Weighted Vertex Cover problem

__
TR09-123
| 23rd November 2009
__

Hemanta Maji, Manoj Prabhakaran, Mike Rosulek#### Cryptographic Complexity Classes and Computational Intractability Assumptions

__
TR08-050
| 12th March 2008
__

Manoj Prabhakaran, Mike Rosulek#### Cryptographic Complexity of Multi-party Computation Problems: Classifications and Separations

__
TR02-017
| 12th March 2002
__

Aggelos Kiayias, Moti Yung#### Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications

__
TR15-027
| 25th February 2015
__

Benny Applebaum#### Cryptographic Hardness of Random Local Functions -- Survey

Revisions: 1

__
TR06-057
| 19th April 2006
__

Adam Klivans, Alexander A. Sherstov#### Cryptographic Hardness Results for Learning Intersections of Halfspaces

__
TR21-010
| 11th February 2021
__

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle#### Cryptographic Hardness under Projections for Time-Bounded Kolmogorov Complexity

Revisions: 2

__
TR20-044
| 8th April 2020
__

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan#### Cryptography from Information Loss

Revisions: 1

__
TR21-055
| 20th April 2021
__

Yanyi Liu, Rafael Pass#### Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity

__
TR08-104
| 23rd November 2008
__

Madhur Tulsiani#### CSP Gaps and Reductions in the Lasserre Hierarchy

__
TR19-013
| 31st January 2019
__

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami#### CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations

__
TR16-205
| 22nd December 2016
__

Amey Bhangale, Irit Dinur, Inbal Livni Navon#### Cube vs. Cube Low Degree Test

__
TR18-160
| 12th September 2018
__

Anna Gal, Avishay Tal, Adrian Trejo Nuñez#### Cubic Formula Size Lower Bounds Based on Compositions with Majority

__
TR23-005
| 13th January 2023
__

Paul Beame, Niels Kornerup#### Cumulative Memory Lower Bounds for Randomized and Quantum Computation

__
TR08-037
| 29th February 2008
__

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo#### Curves That Must Be Retraced

Revisions: 1

Rüdiger Reischuk

For ordinary circuits with a fixed upper bound on the maximal fanin

of gates it has been shown that logarithmic redundancy is necessary and

sufficient to overcome random hardware faults.

Here, we consider the same question for unbounded fanin circuits that

in the noiseless case can compute ...
more >>>

Alon Rosen, Gil Segev, Ido Shahaf

We consider the question of whether average-case PPAD hardness can be based on standard cryptographic assumptions, such as the existence of one-way functions or public-key encryption. This question is particularly well-motivated in light of new devastating attacks on obfuscation candidates and their underlying building blocks, which are currently the only ... more >>>

Oded Goldreich, Amit Sahai, Salil Vadhan

We extend the study of non-interactive statistical zero-knowledge

proofs. Our main focus is to compare the class NISZK of problems

possessing such non-interactive proofs to the class SZK of problems

possessing interactive statistical zero-knowledge proofs. Along these

lines, we first show that if statistical zero knowledge is non-trivial

then so ...
more >>>

Subhash Khot, Dana Moshkovitz

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.

Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ...
more >>>

Oded Goldreich

We suggest a candidate one-way function using combinatorial

constructs such as expander graphs. These graphs are used to

determine a sequence of small overlapping subsets of input bits,

to which a hard-wired random predicate is applied.

Thus, the function is extremely easy to evaluate:

all that is needed ...
more >>>

Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan

Tree codes are combinatorial structures introduced by Schulman (STOC 1993) as key ingredients in interactive coding schemes. Asymptotically-good tree codes are long known to exist, yet their explicit construction remains a notoriously hard open problem. Even proposing a plausible construction, without the burden of proof, is difficult and the defining ... more >>>

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

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

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to

the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is

identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ...
more >>>

Leonid Gurvits, Jonathan Leake

The purpose of this note is to state and prove a lower bound on the capacity of a real stable polynomial $p(x)$ which is based only on its value and gradient at $x=1$. This result implies a sharp improvement to a similar inequality proved by Linial-Samorodnitsky-Wigderson in 2000. Such inequalities ... more >>>

Mahdi Cheraghchi, Venkatesan Guruswami

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), encode messages $s$ in a manner so that tampering the codeword causes the decoder to either output $s$ or a message that is independent of $s$. While this is an impossible goal to achieve against unrestricted tampering functions, rather surprisingly ... more >>>

Gil Cohen, Shahar Samocha

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>

James Cook, Ian Mertz

The study of branching programs for the Tree Evaluation Problem, introduced by S. Cook et al. (TOCT 2012), remains one of the most promising approaches to separating L from P. Given a label in $[k]$ at each leaf of a complete binary tree and an explicit function in $[k]^2 \to ... more >>>

Emanuele Viola, Emanuele Viola

We prove that to store n bits x so that each

prefix-sum query Sum(i) := sum_{k < i} x_k can be answered

by non-adaptively probing q cells of log n bits, one needs

memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +

n/log^{Omega(q)} ...
more >>>

Josh Alman, Joshua Wang, Huacheng Yu

In this work, we introduce an online model for communication complexity. Analogous to how online algorithms receive their input piece-by-piece, our model presents one of the players Bob his input piece-by-piece, and has the players Alice and Bob cooperate to compute a result it presents Bob with the next piece. ... more >>>

Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

The \textsc{equality} problem is usually one's first encounter with

communication complexity and is one of the most fundamental problems in the

field. Although its deterministic and randomized communication complexity

were settled decades ago, we find several new things to say about the

problem by focusing on two subtle aspects. The ...
more >>>

Swastik Kopparty, Srikanth Srinivasan

In this paper, we introduce and develop the method of certifying polynomials for proving $\mathrm{AC}^0[\oplus]$ circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by $\mathrm{AC}^0[\oplus]$ circuits of size $n^{1+o(1)}$. This implies a separation between the power of $\mathrm{AC}^0[\oplus]$ circuits of near-linear size and ... more >>>

Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich

Abstract. It is known that random k-SAT formulas with at least

(2^k*ln2)*n random clauses are unsatisfiable with high probability. This

result is simply obtained by bounding the expected number of satisfy-

ing assignments of a random k-SAT instance by an expression tending

to 0 when n, the number of variables ...
more >>>

Emanuele Viola

We draw two incomplete, biased maps of challenges in

computational complexity lower bounds. Our aim is to put

these challenges in perspective, and to present some

connections which do not seem widely known.

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

We study the problem of assigning different communication channels to

acces points in a wireless Local Area Network. Each access point will

be assigned a specific radio frequency channel. Since channels with

similar frequencies interfere, it is desirable to assign far apart

channels (frequencies) to nearby access points. Our goal ...
more >>>

Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak

Consider a PPT two-party protocol ?=(A,B) in which the parties get no private inputs and obtain outputs O^A,O^B?{0,1}, and let V^A and V^B denote the parties’ individual views. Protocol ? has ?-agreement if Pr[O^A=O^B]=1/2+?. The leakage of ? is the amount of information a party obtains about the event {O^A=O^B}; ... more >>>

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 1992), who showed that proving lower bounds for $pd(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudlak, ... more >>>

T.C. Vijayaraghavan

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that ... more >>>

Shuichi Hirahara

We exactly characterize the average-case complexity of the polynomial-time hierarchy (PH) by the worst-case (meta-)complexity of GapMINKT(PH), i.e., an approximation version of the problem of determining if a given string can be compressed to a short PH-oracle efficient program. Specifically, we establish the following equivalence:

DistPH is contained in ... more >>>

Yanyi Liu, Rafael Pass

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>

Justin Holmgren, Lisa Yang

Non-signaling games are an important object of study in the theory of computation, for their role both in quantum information and in (classical) cryptography. In this work, we study the behavior of these games under parallel repetition.

We show that, unlike the situation both for classical games and for two-player ... more >>>

Fu Li, Iddo Tzameret, Zhengyu Wang

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

Salil Vadhan, Colin Jia Zheng

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Motivated by the question of how to define an analog of interactive

proofs in the setting of logarithmic time- and space-bounded

computation, we study complexity classes defined in terms of

operators quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Olaf Beyersdorff, Zenon Sadowski

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?

Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>

Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena, Huacheng Yu

We study boolean constraint satisfaction problems (CSPs) $\mathrm{Max}\text{-}\mathrm{CSP}^f_n$ for all predicates $f: \{ 0, 1 \} ^k \to \{ 0, 1 \}$. In these problems, given an integer $v$ and a list of constraints over $n$ boolean variables, each obtained by applying $f$ to a sequence of literals, we wish ... more >>>

T.C. Vijayaraghavan

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

Oded Goldreich, Dana Ron, Madhu Sudan

The Chinese Remainder Theorem states that a positive

integer m is uniquely specified by its remainder modulo

k relatively prime integers p_1,...,p_k, provided

m < \prod_{i=1}^k p_i. Thus the residues of m modulo

relatively prime integers p_1 < p_2 < ... < p_n

form a redundant representation of m if ...
more >>>

Aayush Ojha, Raghunath Tewari

Recently, perfect matching in bounded planar cutwidth bipartite graphs

$BGGM$ was shown to be in ACC$^0$ by Hansen et al.. They also conjectured that

the problem is in AC$^0$.

In this paper, we disprove their conjecture by showing that the problem is

not in AC$^0[p^{\alpha}]$ for every prime $p$. ...
more >>>

Anna Bernasconi, Igor E. Shparlinski

In this paper we extend the area of applications of

the Abstract Harmonic Analysis to the field of Boolean function complexity.

In particular, we extend the class of functions to which

a spectral technique developed in a series of works of the first author

can be applied.

This extension ...
more >>>

Joshua Grochow, Toniann Pitassi

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>

Alexander Golovnev, Alexander Kulikov

The best known circuit lower bounds against unrestricted circuits remained around $3n$ for several decades. Moreover, the only known technique for proving lower bounds in this model, gate elimination, is inherently limited to proving lower bounds of less than $5n$. In this work, we suggest a first non-gate-elimination approach for ... more >>>

Ramamohan Paturi, Pavel Pudlak

In 1977 Valiant proposed a graph theoretical method for proving lower

bounds on algebraic circuits with gates computing linear functions.

He used this method to reduce the problem of proving

lower bounds on circuits with linear gates to to proving lower bounds

on the rigidity of a matrix, a ...
more >>>

Alexander Knop

Santhanam (2007) proved that MA/1 does not have circuits of size $n^k$. We translate his result to the heuristic setting by proving that there is a constant $a$ such that for any $k$, there is a language in HeurMA that cannot be solved by circuits of size $n^k$ on more ... more >>>

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis

The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function $f$ can be computed by a Boolean circuit of size at most $\theta$, for a given parameter $\theta$. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a ... more >>>

Rahul Santhanam

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

Cody Murray, Ryan Williams

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>

Ján Pich

We prove that $T_{NC^1}$, the true universal first-order theory in the language containing names for all uniform $NC^1$ algorithms, cannot prove that for sufficiently large $n$, SAT is not computable by circuits of size $n^{2kc}$ where $k\geq 1, c\geq 4$ unless each function $f\in SIZE(n^k)$ can be approximated by formulas ... more >>>

Vikraman Arvind, Srikanth Srinivasan

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

Valentine Kabanets, Jin-Yi Cai

We study the complexity of the circuit minimization problem:

given the truth table of a Boolean function f and a parameter s, decide

whether f can be realized by a Boolean circuit of size at most s. We argue

why this problem is unlikely to be in P (or ...
more >>>

Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... more >>>

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V Vinay

We consider the computational power of constant width polynomial

size cylindrical circuits and nondeterministic branching programs.

We show that every function computed by a Pi2 o MOD o AC0 circuit

can also be computed by a constant width polynomial size cylindrical

nondeterministic branching program (or cylindrical circuit) and

that ...
more >>>

Klim Efremenko, Bernhard Haeupler, Yael Kalai, Pritish Kamath, Gillat Kol, Nicolas Resch, Raghuvansh Saxena

Given a Boolean circuit $C$, we wish to convert it to a circuit $C'$ that computes the same function as $C$ even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

Pavel Hrubes, Anup Rao

We consider boolean circuits in which every gate may compute an arbitrary boolean function of $k$ other gates, for a parameter $k$. We give an explicit function $f:\bits^n \rightarrow \bits$ that requires at least $\Omega(\log^2 n)$ non-input gates when $k = 2n/3$. When the circuit is restricted to being depth ... more >>>

Cenny Wenner

Håstad established that any predicate $P \subseteq \{0,1\}^m$ containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang ... more >>>

Agnes Schleitzer, Olaf Beyersdorff

To date, we know only a few handcrafted quantified Boolean formulas (QBFs) that are hard for central QBF resolution systems such as Q and QU, and only one specific QBF family to separate Q and QU.

Here we provide a general method to construct hard formulas for Q and ... more >>>

Sophie Laplante, Virginie Lerays, Jérémie Roland

In communication complexity, two players each have an input and they wish to compute some function of the joint inputs. This has been the object of much study and a wide variety of lower bound methods have been introduced to address the problem of showing lower bounds on communication. Recently, ... more >>>

Viliam Geffert, Abuzer Yakaryilmaz

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

Dmytro Gavinsky

We demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost O(log n) but requires exponentially more communication in the classical interactive (two-way) model.

more >>>Andrew Chi-Chih Yao

Would physical laws permit the construction of computing machines

that are capable of solving some problems much faster than the

standard computational model? Recent evidence suggests that this

might be the case in the quantum world. But the question is of

great interest even in the realm of classical physics. ...
more >>>

Tomas Feder, Daniel Ford

Matroid intersection has a known polynomial time algorithm using an

oracle. We generalize this result to delta-matroids that do not have

equality as a restriction, and give a polynomial time algorithm for

delta-matroid intersection on delta-matroids without equality using an

oracle. We note that when equality is present, delta-matroid intersection

more >>>

igor razgon

We introduce a new graph parameter called linear upper maximum induced

matching width \textsc{lu-mim width}, denoted for a graph $G$ by $lu(G)$.

We prove that the smallest size of the \textsc{obdd} for $\varphi$,

the monotone 2-\textsc{cnf} corresponding to $G$, is sandwiched

between $2^{lu(G)}$ and $n^{O(lu(G))}$.

The upper bound ...
more >>>

Tsuyoshi Morioka

We present a new framework for the study of search problems and their

definability in bounded arithmetic. We identify two notions of

complexity of search problems: verification complexity and

computational complexity. Notions of exact solvability and exact

reducibility are developed, and exact $\Sigma^b_i$-definability of

search problems in bounded arithmetic ...
more >>>

Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Santhoshini Velusamy

A Boolean constraint satisfaction problem (CSP), Max-CSP$(f)$, is a maximization problem specified by a constraint $f:\{-1,1\}^k\to\{0,1\}$. An instance of the problem consists of $m$ constraint applications on $n$ Boolean variables, where each constraint application applies the constraint to $k$ literals chosen from the $n$ variables and their negations. The goal ... more >>>

Evgeny Dantsin, Edward Hirsch, Alexander Wolpert

We give a deterministic algorithm for testing satisfiability of formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [Dantsin and Wolpert, SAT 2005]. In comparison with the randomized algorithm in ... more >>>

Stasys Jukna

Motivated by its relation to the length of cutting plane proofs for the Maximum Biclique problem, here we consider the following communication game on a given graph G, known to both players. Let K be the maximal number of vertices in a complete bipartite subgraph of G (which is not ... more >>>

Scott Aaronson, John Watrous

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to nontrivial insights in general relativity, quantum information, and other areas. In this paper we show that if CTCs existed, then quantum computers would be no more powerful than classical computers: both would have the ... more >>>

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an n variate degree $d$ polynomial f can be computed by an arithmetic circuit of size s, then each of its factors can ... more >>>

Richard Beigel

We classify the univariate functions that are relativizable

closure properties of GapP, solving a problem posed by Hertrampf,

Vollmer, and Wagner (Structures '95). We also give a simple proof of

their classification of univariate functions that are relativizable

closure properties of #P.

Tomas Feder, Phokion G. Kolaitis

Quantified constraint satisfaction is the generalization of

constraint satisfaction that allows for both universal and existential

quantifiers over constrained variables, instead

of just existential quantifiers.

We study quantified constraint satisfaction problems ${\rm CSP}(Q,S)$, where $Q$ denotes

a pattern of quantifier alternation ending in exists or the set of all possible

more >>>

Leonard Schulman

We address the problem of partitioning a set of $n$ points into

clusters, so as to minimize the sum, over all intracluster pairs of

points, of the cost associated with each pair. We obtain a randomized

approximation algorithm for this problem, for the cost functions

$\ell_2^2,\ell_1$ and $\ell_2$, as ...
more >>>

Irit Dinur, Elazar Goldenberg

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

Vikraman Arvind, Venkatesan Guruswami

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>

James R. Lee, Prasad Raghavendra

We show that the multi-commodity max-flow/min-cut gap for series-parallel graphs can be as bad as 2, matching a recent upper bound by Chakrabarti.et.al for this class, and resolving one side of a conjecture of Gupta, Newman, Rabinovich, and Sinclair.

This also improves the largest known gap for planar graphs ... more >>>

Venkatesan Guruswami, Adam Smith

In this paper, we consider coding schemes for computationally bounded channels, which can introduce an arbitrary set of errors as long as (a) the fraction of errors is bounded with high probability by a parameter p and (b) the process which adds the errors can be described by a sufficiently ... more >>>

Sankeerth Rao Karingula, Shachar Lovett

The prototypical construction of error correcting codes is based on linear codes over finite fields. In this work, we make first steps in the study of codes defined over integers. We focus on Maximum Distance Separable (MDS) codes, and show that MDS codes with linear rate and distance can be ... more >>>

Itay Berman, Iftach Haitner, Aris Tentes

We show that the existence of a coin-flipping protocol safe against any non-trivial constant bias (e.g., $.499$) implies the existence of one-way functions. This improves upon a recent result of Haitner and Omri [FOCS '11], who proved this implication for protocols with bias $\frac{\sqrt2 -1}2 - o(1) \approx .207$. Unlike ... more >>>

Rohit Agrawal

In this note we compare two measures of the complexity of a class $\mathcal F$ of Boolean functions studied in (unconditional) pseudorandomness: $\mathcal F$'s ability to distinguish between biased and uniform coins (the coin problem), and the norms of the different levels of the Fourier expansion of functions in $\mathcal ... more >>>

Eli Ben-Sasson, Eden Saig

Gurus are individuals who claim to possess mental powers of insight and prediction that far surpass those of the average person; they compete over followers, offering them insight in return for continued devotion. Followers wish to harness a (true) Guru’s predictive power but (i) have limited attention span and (ii) ... more >>>

Nikhil Balaji, Samir Datta

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$

for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]

more >>>

Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price

We study the fundamental problems of (i) uniformity testing of a discrete distribution,

and (ii) closeness testing between two discrete distributions with bounded $\ell_2$-norm.

These problems have been extensively studied in distribution testing

and sample-optimal estimators are known for them~\cite{Paninski:08, CDVV14, VV14, DKN:15}.

In this work, we show ... more >>>

Oded Goldreich, Shai Halevi

Recently Ajtai described a construction of one-way functions whose

security is equivalent to the difficulty of some well known approximation

problems in lattices. We show that essentially the same

construction can also be used to obtain collision-free hashing.

Ron D. Rothblum, Prashant Nalini Vasudevan

Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even ... more >>>

Noga Alon, Raphael Yuster, Uri Zwick

We describe a novel randomized method, the method of

{\em color-coding\/} for finding simple paths and cycles of a specified

length $k$, and other small subgraphs, within a given graph $G=(V,E)$.

The randomized algorithms obtained using this method can be

derandomized using families of {\em perfect hash functions\/}. ...
more >>>

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

Leonid Gurvits

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$

be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.

The support of such polynomial $p(x_1,...,x_n)$

is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ...
more >>>

Or Meir

An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by ... more >>>

Manjish Pal

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced ... more >>>

Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

The very first Kolmogorov's paper on algorithmic

information theory was entitled `Three approaches to the

definition of the quantity of information'. These three

approaches were called combinatorial, probabilistic and

algorithmic. Trying to establish formal connections

between combinatorial and algorithmic approaches, we

prove that any ...
more >>>

Venkatesan Guruswami, Srivatsan Narayanan

We prove the following results concerning the combinatorics of list decoding, motivated by the exponential gap between the known upper bound (of $O(1/\gamma)$) and lower bound (of $\Omega_p(\log (1/\gamma))$) for the list-size needed to decode up to radius $p$ with rate $\gamma$ away from capacity, i.e., $1-h(p)-\gamma$ (here $p\in (0,1/2)$ ... more >>>

Jonah Brown-Cohen, Prasad Raghavendra

An elegant characterization of the complexity of constraint satisfaction problems has emerged in the form of the the algebraic dichotomy conjecture of [BKJ00]. Roughly speaking, the characterization asserts that a CSP $\Lambda$ is tractable if and only if there exist certain non-trivial operations known as polymorphisms to combine solutions to ... more >>>

Or Meir

The PCP theorem asserts the existence of proofs that can be verified by a verifier that reads only a very small part of the proof. The theorem was originally proved by Arora and Safra (J. ACM 45(1)) and Arora et al. (J. ACM 45(3)) using sophisticated algebraic tools. More than ... more >>>

Or Meir

The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the ... more >>>

Oded Goldreich

We consider the question of determining whether

a given object has a predetermined property or is ``far'' from any

object having the property.

Specifically, objects are modeled by functions,

and distance between functions is measured as the fraction

of the domain on which the functions differ.

We ...
more >>>

Stasys Jukna

We consider a general model of monotone circuits, which

we call d-local. In these circuits we allow as gates:

(i) arbitrary monotone Boolean functions whose minterms or

maxterms (or both) have length at most <i>d</i>, and

(ii) arbitrary real-valued non-decreasing functions on ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami

Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>>

Alex Hertel, Alasdair Urquhart

We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>

Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry

What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the ... more >>>

Gábor Braun, Sebastian Pokutta

We provide a new framework for establishing strong lower bounds on the nonnega- tive rank of matrices by means of common information, a notion previously introduced in Wyner [1975]. Common information is a natural lower bound for the nonnegative rank of a matrix and by combining it with Hellinger distance ... more >>>

Tim Roughgarden

This document collects the lecture notes from my course ``Communication Complexity (for Algorithm Designers),'' taught at

Stanford in the winter quarter of 2015. The two primary goals of the course are:

1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). ... more >>>

Moni Naor, Kobbi Nissim

A secure function evaluation protocol allows two parties to jointly compute a function $f(x,y)$ of their inputs in a manner not leaking more information than necessary. A major result in this field is: ``any function $f$ that can be computed using polynomial resources can be computed securely using polynomial resources'' ... more >>>

Mika Göös, Siddhartha Jain

The Collision problem is to decide whether a given list of numbers $(x_1,\ldots,x_n)\in[n]^n$ is $1$-to-$1$ or $2$-to-$1$ when promised one of them is the case. We show an $n^{\Omega(1)}$ randomised communication lower bound for the natural two-party version of Collision where Alice holds the first half of the bits of ... more >>>

Anat Ganor, Karthik C. S.

We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player $N \times N$ game called the 2-cycle game and show that the randomized communication complexity of finding a 1/poly($N$)-approximate correlated equilibrium of the 2-cycle game is $\Omega(N)$. For ... more >>>

Badih Ghazi, Pritish Kamath, Madhu Sudan

Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of ''permutation-invariant'' functions. A partial function $f:\{0,1\}^n \times \{0,1\}^n\to \{0,1,?\}$ is permutation-invariant if for every bijection $\pi:\{1,\ldots,n\} \to \{1,\ldots,n\}$ and every $\mathbf{x}, \mathbf{y} \in \{0,1\}^n$, it is the case that $f(\mathbf{x}, \mathbf{y}) ... more >>>

Mika Göös, Thomas Watson

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>>

Thomas Watson

We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there ... more >>>

Alexander A. Sherstov

We solve an open problem of Kushilevitz and Nisan

(1997) in communication complexity. Let $R_{eps}(f)$

and $D^{mu}_{eps}(f)$ denote the randomized and

$mu$-distributional communication complexities of

f, respectively ($eps$ a small constant). Yao's

well-known Minimax Principle states that

R_{eps}(f) = max_{mu} { D^{mu}_{eps}(f) }.

Kushilevitz and Nisan (1997) ask whether ...
more >>>

Marshall Ball, Oded Goldreich, Tal Malkin

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.

Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ...
more >>>

Thomas Watson

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>>

Shachar Lovett

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

Alexander A. Sherstov

We prove that the set disjointness problem has randomized communication complexity

$\Omega(\sqrt{n}/2^{k}k)$ in the number-on-the-forehead model with $k$ parties, a quadratic improvement

on the previous bound $\Omega(\sqrt{n}/2^{k})^{1/2}$. Our result remains valid for quantum

protocols, where it is essentially tight. Proving it was an open problem since 1997, ...
more >>>

Alexander A. Sherstov

Representations of Boolean functions by real polynomials

play an important role in complexity theory. Typically,

one is interested in the least degree of a polynomial

p(x_1,...,x_n) that approximates or sign-represents

a given Boolean function f(x_1,...,x_n). This article

surveys a new and growing body of work in communication

complexity that centers ...
more >>>

Ilan Komargodski, Pravesh Kothari, Madhu Sudan

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information $x$ and Bob gets $y$, where $(x,y)$ is drawn from a known distribution, and Bob ... more >>>

Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

The communication complexity of many fundamental problems reduces greatly

when the communicating parties share randomness that is independent of the

inputs to the communication task. Natural communication processes (say between

humans) however often involve large amounts of shared correlations among the

communicating players, but rarely allow for perfect sharing of ...
more >>>

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $\mu$. They ... more >>>

Sunil K S, Balagopal Komarath, Jayalal Sarma

Comparator circuit model was originally introduced by Mayr and Subramanian (1992) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem We know ... more >>>

Russell Impagliazzo, Sam McGuire

Computational pseudorandomness studies the extent to which a random variable $\bf{Z}$ looks like the uniform distribution according to a class of tests $\cal{F}$. Computational entropy generalizes computational pseudorandomness by studying the extent which a random variable looks like a \emph{high entropy} distribution. There are different formal definitions of computational entropy ... more >>>

Oded Goldreich, Salil Vadhan

We consider the following (promise) problem, denoted ED (for Entropy

Difference): The input is a pairs of circuits, and YES instances (resp.,

NO instances) are such pairs in which the first (resp., second) circuit

generates a distribution with noticeably higher entropy.

On one hand we show that any language ... more >>>

John Hitchcock, A. Pavan

Under the assumption that NP does not have p-measure 0, we

investigate reductions to NP-complete sets and prove the following:

- Adaptive reductions are more powerful than nonadaptive

reductions: there is a problem that is Turing-complete for NP but

not truth-table-complete.

- Strong nondeterministic reductions are more powerful ... more >>>

Ronald de Haan, Stefan Szeider

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These parameterized problems are based on problems whose complexity lies at the second level of the Polynomial Hierarchy or higher. The list will be updated as ... more >>>

Gillat Kol, Ran Raz

Let $C$ be a (fan-in $2$) Boolean circuit of size $s$ and depth $d$, and let $x$ be an input for $C$. Assume that a verifier that knows $C$ but doesn't know $x$ can access the low degree extension of $x$ at one random point. Two competing provers try to ... more >>>

Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

Daniel Minahan, Ilya Volkovich

In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the

operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain ...
more >>>

Tobias Riege, Jörg Rothe

This paper surveys some of the work that was inspired by Wagner's general technique to prove completeness in the levels of the boolean hierarchy over NP and some related results. In particular, we show that it is DP-complete to decide whether or not a given graph can be colored with ... more >>>

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

A Secure Function Evaluation (SFE) of a two-variable function f(.,.) is a protocol that allows two parties with inputs x and y to evaluate

f(x,y) in a manner where neither party learns ``more than is necessary". A rich body of work deals with the study of completeness for secure ...
more >>>

Petr Savicky

For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the ...
more >>>

Adam Bouland, Laura Mancinska, Xue Zhang

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian $H$ which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one ... more >>>

Pinyan Lu

In order to study the complexity of counting problems, several interesting frameworks have been proposed, such as Constraint Satisfaction Problems (#CSP) and Graph Homomorphisms. Recently, we proposed and explored a novel alternative framework, called Holant Problems. It is a refinement with a more explicit role for constraint functions. Both graph ... more >>>

Alexander Barg

This is a research-expository paper. It deals with

complexity issues in the theory of linear block codes. The main

emphasis is on the theoretical performance limits of the

best known codes. Therefore, the main subject of the paper are

families of asymptotically good codes, i.e., codes whose rate and

relative ...
more >>>

Guy Moshkovitz

In this paper we present a combinatorial approach for proving complexity lower bounds. We mainly focus on the following instantiation of it. Consider a pair of properties of $m$-edge regular hypergraphs. Suppose they are ``indistinguishable'' with respect to hypergraphs with $m-t$ edges, in the sense that every such hypergraph has ... more >>>

Venkatesan Guruswami, Euiwoong Lee

We study two natural extensions of Constraint Satisfaction Problems (CSPs). {\em Balance}-Max-CSP requires that in any feasible assignment each element in the domain is used an equal number of times. An instance of {\em Hard}-Max-CSP consists of {\em soft constraints} and {\em hard constraints}, and the goal is to maximize ... more >>>

Titus Dose

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>

Miki Hermann, Reinhard Pichler

Following the approach of Hemaspaandra and Vollmer, we can define

counting complexity classes #.C for any complexity class C of decision

problems. In particular, the classes #.Pi_{k}P with k >= 1

corresponding to all levels of the polynomial hierarchy have thus been

studied. However, for a large variety of counting ...
more >>>

Dmitry Itsykson, Alexander Knop, Dmitry Sokolov

We address a natural question in average-case complexity: does there exist a language $L$ such that for all easy distributions $D$ the distributional problem $(L, D)$ is easy on the average while there exists some more hard distribution $D'$ such that $(L, D')$ is hard on the average? We consider ... more >>>

Scott Contini, Ernie Croot, Igor E. Shparlinski

We present an algorithm to invert the Euler function $\varphi(m)$. The algorithm, for a given integer $n\ge 1$, in polynomial time ``on average'', finds theset $\Psi(n)$ of all solutions $m$ to the equation $\varphi(m) =n$. In fact, in the worst case the set $\Psi(n)$ is exponentially large and cannot be ... more >>>

Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

Eric Allender, Ian Mertz

We give complexity bounds for various classes of functions computed by cost register automata.

more >>>Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik

It is a known approach to translate propositional formulas into

systems of polynomial inequalities and to consider proof systems

for the latter ones. The well-studied proof systems of this kind

are the Cutting Planes proof system (CP) utilizing linear

inequalities and the Lovasz-Schrijver calculi (LS) utilizing

quadratic ...
more >>>

Tobias Riege, Jörg Rothe

We prove that the exact versions of the domatic number problem are complete

for the levels of the boolean hierarchy over NP. The domatic number

problem, which arises in the area of computer networks, is the problem of

partitioning a given graph into a maximum number ...
more >>>

Md Lutfar Rahman, Thomas Watson

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>

Pavel Pudlak

We introduce a population genetics model in which the operators

are effectively computable -- computable in polynomial time on

Probabilistic Turing Machines. We shall show that in this model

a population can encode easily large amount of information

from enviroment into genetic code. Then it can process the

information as ...
more >>>

Tim Roughgarden

This document collects the lecture notes from my mini-course "Complexity Theory, Game Theory, and Economics," taught at the Bellairs Research Institute of McGill University, Holetown, Barbados, February 19-23, 2017, as the 29th McGill Invitational Workshop on Computational Complexity.

The goal of this mini-course is twofold: (i) to explain how complexity ... more >>>

Scott Aaronson, Lijie Chen

In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis ... more >>>

Arkadev Chattopadhyay, Michal Koucky, Bruno Loff, Sagnik Mukhopadhyay

We prove a randomized communication-complexity lower bound for a composed OrderedSearch $\circ$ IP — by lifting the randomized query-complexity lower-bound of OrderedSearch to the communication-complexity setting. We do this by extending ideas from a paper of Raz and Wigderson. We think that the techniques we develop will be useful in ... more >>>

Irit Dinur, Prahladh Harsha

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

Eli Ben-Sasson, Michael Viderman

In this paper we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the First composition theorem showing that repeating the two-wise tensor operation any constant number of times still results in a locally testable code, improving upon previous ... more >>>

Wee, Hoeteck

A source is compressible if we can efficiently compute short

descriptions of strings in the support and efficiently

recover the strings from the descriptions. In this paper, we

present a technique for proving lower bounds on

compressibility in an oracle setting, which yields the

following results:

- We ...
more >>>

Yael Tauman Kalai, Ilan Komargodski

We show how to compress communication in distributed protocols in which parties do not have private inputs. More specifically, we present a generic method for converting any protocol in which parties do not have private inputs, into another protocol where each message is "short" while preserving the same number of ... more >>>

Alexander A. Sherstov

We study the problem of compressing interactive communication to its

information content $I$, defined as the amount of information that the

participants learn about each other's inputs. We focus on the case when

the participants' inputs are distributed independently and show how to

compress the communication to $O(I\log^{2}I)$ bits, with ...
more >>>

Valentine Kabanets, Antonina Kolokolova

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

Luca Trevisan, Salil Vadhan, David Zuckerman

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers

This paper explores the impact of geometry on computability =

and complexity in

Winfree's model of nanoscale self-assembly. We work in the =

two-dimensional

tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our =

first

main theorem says that there is a roughly quadratic function f ...
more >>>

Scott Aaronson, Mohammad Bavarian, Giulio Gueltrini

We ask, and answer, the question of what's computable by Turing machines equipped with time travel into the past: that is, closed timelike curves or CTCs (with no bound on their size). We focus on a model for CTCs due to Deutsch, which imposes a probabilistic consistency condition to avoid ... more >>>

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts ... more >>>

Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin

The partial string avoidability problem is stated as follows: given a finite set of strings with possible ``holes'' (wildcard symbols), determine whether there exists a two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol. The problem is known to be NP-hard and in ... more >>>

Prashant Joshi, Eduardo D. Sontag

It had previously been shown that generic cortical microcircuit

models can perform complex real-time computations on continuous

input streams, provided that these computations can be carried out

with a rapidly fading memory. We investigate in this article the

computational capability of such circuits in the ...
more >>>

Varun Kanade

Valiant (2007) proposed a computational model for evolution and suggested that evolvability be studied in the framework of computational learning theory. Feldman (2008) showed that Valiant’s evolution model is equivalent to the correlational statistical query (CSQ) learning model, which is a restricted setting of the statistical query (SQ) model. Evolvability ... more >>>

Oded Goldreich, Rafail Ostrovsky, Erez Petrank

We study the computational complexity of languages which have

interactive proofs of logarithmic knowledge complexity. We show that

all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior

to this work, for languages with greater-than-zero knowledge

complexity (and specifically, even for knowledge complexity 1) only

trivial computational complexity bounds ...
more >>>

Predrag Tosic

We study the computational complexity of counting the fixed point configurations (FPs), the predecessor configurations and the ancestor configurations in certain classes of graph or network automata viewed as discrete dynamical systems. Early results of this investigation are presented in two recent ECCC reports [39, 40]. In particular, it is ... more >>>

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>Klaus Weihrauch

We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of ${\rm TIME}$ as the maximum of a generally infinite ... more >>>

Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>

Oded Goldreich, Bernd Meyer

We present a simple proof to the existence of a probability ensemble

with tiny support which cannot be distinguished from the uniform ensemble

by any recursive computation.

Since the support is tiny (i.e, sub-polynomial),

this ensemble can be distinguish from the uniform ensemble

by a (non-uniform) family ...
more >>>

Oded Goldreich, Madhu Sudan

We consider the existence of pairs of probability ensembles which

may be efficiently distinguished given $k$ samples

but cannot be efficiently distinguished given $k'<k$ samples.

It is well known that in any such pair of ensembles it cannot be that

both are efficiently computable

(and that such phenomena ...
more >>>

Scott E. Decatur, Oded Goldreich, Dana Ron

In a variety of PAC learning models, a tradeoff between time and

information seems to exist: with unlimited time, a small amount of

information suffices, but with time restrictions, more information

sometimes seems to be required.

In addition, it has long been known that there are

concept classes ...
more >>>

Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, Jad Silbak

Let $\pi$ be an efficient two-party protocol that given security parameter $\kappa$, both parties output single bits $X_\kappa$ and $Y_\kappa$, respectively. We are interested in how $(X_\kappa,Y_\kappa)$ ``appears'' to an efficient adversary that only views the transcript $T_\kappa$. We make the following contributions:

\begin{itemize}

\item We develop new tools to ...
more >>>

Ilya Volkovich

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.

Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).

In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.

That is, beyond an exponentiation gate. As ...
more >>>

Paul Spirakis, haralampos tsaknakis

In this paper we propose a methodology for determining approximate Nash equilibria of non-cooperative bimatrix games and, based on that, we provide a polynomial time algorithm that computes $\frac{1}{3} + \frac{1}{p(n)} $ -approximate equilibria, where $p(n)$ is a polynomial controlled by our algorithm and proportional to its running time. The ... more >>>

Shiva Kintali, Sinziana Munteanu

We present a logspace algorithm to compute path decompositions of bounded pathwidth graphs, thus settling its complexity. Prior to our work, the best known upper bound to compute such decompositions was linear time. We also show that deciding if the pathwidth of a graph is at most a given constant ... more >>>

Vince Grolmusz

Elementary symmetric polynomials $S_n^k$ are used as a

benchmark for the bounded-depth arithmetic circuit model of computation.

In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$

can be computed with much fewer multiplications than over any field, if

the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ...
more >>>

Tim Roughgarden

Computational complexity is the subfield of computer science that rigorously studies the intrinsic difficulty of computational problems. This survey explains how complexity theory defines “hard problems”; applies these concepts to several equilibrium computation problems; and discusses implications for computation, games, and behavior. We assume minimal prior background in computer science.

... more >>>Ashish Dwivedi, Nitin Saxena

Igusa's local zeta function $Z_{f,p}(s)$ is the generating function that counts the number of integral roots, $N_{k}(f)$, of $f(\mathbf x) \bmod p^k$, for all $k$. It is a famous result, in analytic number theory, that $Z_{f,p}$ is a rational function in $\mathbb{Q}(p^s)$. We give an elementary proof of this fact ... more >>>

Alexander Kulikov, Vladimir Podolskii

We study the following computational problem: for which values of $k$, the majority of $n$ bits $\text{MAJ}_n$ can be computed with a depth two formula whose each gate computes a majority function of at most $k$ bits? The corresponding computational model is denoted by $\text{MAJ}_k \circ \text{MAJ}_k$. We observe that ... more >>>

Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

Craig Gentry

This survey, aimed mainly at mathematicians rather than practitioners, covers recent developments in homomorphic encryption (computing on encrypted data) and program obfuscation (generating encrypted but functional programs). Current schemes for encrypted computation all use essentially the same "noisy" approach: they encrypt via a noisy encoding of the message, they decrypt ... more >>>

Shachar Lovett

A folklore result in arithmetic complexity shows that the number of multiplications required to compute some $n$-variate polynomial of degree $d$ is $\sqrt{{n+d \choose n}}$. We complement this by an almost matching upper bound, showing that any $n$-variate polynomial of degree $d$ over any field can be computed with only ... more >>>

Avishay Tal

A de Morgan formula over Boolean variables $x_1, \ldots, x_n$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that ... more >>>

Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Is there an NP function that, when given a satisfiable formula

as input, outputs one satisfying assignment uniquely? That is, can a

nondeterministic function cull just one satisfying assignment from a

possibly exponentially large collection of assignments? We show that if

there is such a nondeterministic function, then the polynomial ...
more >>>

David P. Dobkin, Dimitrios Gunopulos

Computing the maximum bichromatic discrepancy is an interesting

theoretical problem with important applications in computational

learning theory, computational geometry and computer graphics.

In this paper we give algorithms to compute the maximum

bichromatic discrepancy for simple geometric ranges, including

rectangles and halfspaces.

In addition, we give ...
more >>>

Meena Mahajan, Prajakta Nimbhorkar, Anuj Tawari

We study computation by formulas over $(min, +)$. We consider the computation of $\max\{x_1,\ldots,x_n\}$

over $\mathbb{N}$ as a difference of $(\min, +)$ formulas, and show that size $n + n \log n$ is sufficient and necessary. Our proof also shows that any $(\min, +)$ formula computing the minimum of all ...
more >>>

Harry Buhrman, Richard Cleve, Michal Koucky, Bruno Loff, Florian Speelman

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state ... more >>>

Venkatesan Guruswami, Atri Rudra

We prove that binary linear concatenated codes with an outer algebraic code (specifically, a folded Reed-Solomon code) and independently and randomly chosen linear inner codes achieve the list-decoding capacity with high probability. In particular, for any $0 < \rho < 1/2$ and $\epsilon > 0$, there exist concatenated codes of ... more >>>

Moti Yung, Yunlei Zhao

Knowledge extraction is a fundamental notion, modeling knowledge possession in a computational complexity sense. The notion provides a tool for cryptographic protocol design and analysis, enabling one to argue about the internal state of protocol players. We define and

investigate the relative power of the notion of ``concurrent knowledge-extraction'' ...
more >>>

Rafail Ostrovsky, Giuseppe Persiano, Ivan Visconti

One of the central questions in Cryptography today is proving security of the protocols ``on the Internet'', i.e., in a concurrent setting where there are multiple interactions between players, and where the adversary can play so called ``man-in-the-middle'' attacks, forwarding and modifying messages between two or more unsuspecting players. Indeed, ... more >>>

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

We provide <i>unconditional</i> constructions of <i>concurrent</i>

statistical zero-knowledge proofs for a variety of non-trivial

problems (not known to have probabilistic polynomial-time

algorithms). The problems include Graph Isomorphism, Graph

Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a

restricted version of Statistical Difference, and approximate

versions of the (<b>coNP</b> forms of the) Shortest Vector ...
more >>>

Oded Goldreich

Following Dwork, Naor, and Sahai (30th STOC, 1998),

we consider concurrent execution of protocols in a

semi-synchronized network. Specifically, we assume that each party

holds a local clock such that a constant bound on the relative rates

of these clocks is a-priori known, and consider protocols that

employ ...
more >>>

Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their ... more >>>

Benny Applebaum, Barak Arkis

Consider the following secret-sharing problem. Your goal is to distribute a long file $s$ between $n$ servers such that $(d-1)$-subsets cannot recover the file, $(d+1)$-subsets can recover the file, and $d$-subsets should be able to recover $s$ if and only if they appear in some predefined list $L$. How small ... more >>>

Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan

In the \emph{conditional disclosure of secrets} problem (Gertner et al., J. Comput. Syst. Sci., 2000) Alice and Bob, who hold inputs $x$ and $y$ respectively, wish to release a common secret $s$ to Carol (who knows both $x$ and $y$) if only if the input $(x,y)$ satisfies some predefined predicate ... more >>>

Irit Dinur, Elchanan Mossel, Oded Regev

We study the approximate-coloring(q,Q) problem: Given a graph G, decide

whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional

hardness for this problem for any constant 3\le q < Q. For q \ge

4, our result is based on Khot's 2-to-1 conjecture [Khot'02].

For q=3, we base our hardness ...
more >>>

David Steurer, Nisheeth Vishnoi

In this paper we demonstrate a close connection between UniqueGames and

MultiCut.

%

In MultiCut, one is given a ``network graph'' and a ``demand

graph'' on the same vertex set and the goal is to remove as few

edges from the network graph as ...
more >>>

Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajicek

Proving that there are problems in $P^{NP}$ that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are known for larger complexity classes, existing results only show that the corresponding problems are hard on infinitely many input lengths. For instance, proving almost-everywhere ... more >>>

Igor Carboni Oliveira, Rahul Santhanam

We prove several results giving new and stronger connections between learning theory, circuit complexity and pseudorandomness. Let C be any typical class of Boolean circuits, and C[s(n)] denote n-variable C-circuits of size at most s(n). We show:

Learning Speedups: If C[$n^{O(1)}$] admits a randomized weak learning algorithm under the uniform ... more >>>

Rahul Ilango

Attempts to prove the intractability of the Minimum Circuit Size Problem (MCSP) date as far back as the 1950s and are well-motivated by connections to cryptography, learning theory, and average-case complexity. In this work, we make progress, on two fronts, towards showing MCSP is intractable under worst-case assumptions.

While ... more >>>

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up ... more >>>

Kristoffer Arnsfelt Hansen

We obtain a characterization of ACC0 in terms of a natural class of

constant width circuits, namely in terms of constant width polynomial

size planar circuits. This is shown via a characterization of the

class of acyclic digraphs which can be embedded on a cylinder surface

in such a way ...
more >>>

Alexander Healy, Emanuele Viola

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.

We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

... more >>>Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii

In this paper, we address sorting networks that are constructed from comparators of arity $k > 2$. That is, in our setting the arity of the comparators -- or, in other words, the number of inputs that can be sorted at the unit cost -- is a parameter. We study ... more >>>

Emanuele Viola

Research in the 80's and 90's showed how to construct a pseudorandom

generator from a function that is hard to compute on more than $99\%$

of the inputs. A more recent line of works showed however that if

the generator has small error, then the proof of correctness cannot

be ...
more >>>

Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

We study coding schemes for multiparty interactive communication over synchronous networks that suffer from stochastic noise, where each bit is independently flipped with probability $\epsilon$. We analyze the minimal overhead that must be added by the coding scheme in order to succeed in performing the computation despite the noise.

Our ... more >>>

Ran Gelles, Yael Tauman Kalai

Multiparty interactive coding allows a network of $n$ parties to perform distributed computations when the communication channels suffer from noise. Previous results (Rajagopalan and Schulman, STOC '94) obtained a multiparty interactive coding protocol, resilient to random noise, with a blowup of $O(\log(\Delta+1))$ for networks whose topology has a maximal degree ... more >>>

Moti Yung, Yunlei Zhao

We present constant-round concurrently secure (sound) resettable

zero-knowledge (rZK-CS) arguments in the bare public-key (BPK)

model. Our constructions deal with general NP ZK-arguments as well

as with highly efficient ZK-arguments for number-theoretic

languages, most relevant to identification scenarios. These are the

first constant-round protocols of ...
more >>>

Oded Goldreich, Guy Rothblum

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.

Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than

the work of Reingold, Rothblum, and Rothblum (STOC, 2016).

Our proof system for AC0[2] supports a more ...
more >>>

Omer Reingold, Ron Rothblum, Guy Rothblum

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

Yehuda Lindell

In this note, we show the existence of \emph{constant-round} computational zero-knowledge \emph{proofs of knowledge} for all $\cal NP$. The existence of constant-round zero-knowledge proofs was proven by Goldreich and Kahan (Journal of Cryptology, 1996), and the existence of constant-round zero-knowledge \emph{arguments} of knowledge was proven by Feige and Shamir (CRYPTO ... more >>>

Tomas Feder

Constraint satisfaction on finite groups, with subgroups and their cosets

described by generators, has a polynomial time algorithm. For any given

group, a single additional constraint type that is not a coset of a near

subgroup makes the problem NP-complete. We consider constraint satisfaction on

groups with subgroups, near subgroups, ...
more >>>

Venkatesan Guruswami, Prasad Raghavendra

We study the approximability of the \maxcsp problem over non-boolean domains, more specifically over $\{0,1,\ldots,q-1\}$ for some integer $q$. We obtain a approximation algorithm that achieves a ratio of $C(q) \cdot k/q^k$ for some constant $C(q)$ depending only on $q$. Further, we extend the techniques of Samorodnitsky and Trevisan to ... more >>>

Oliver Kullmann

We consider the next step from boolean conjunctive normal forms to

arbitrary constraint satisfaction problems (with arbitrary constraints), namely "generalised clause-sets" (or "sets of no-goods"), which allow negative literals "v <> e" for variables v and values e --- this level of generality appears to be the right level for ...
more >>>

Tomas Feder

Attempts at classifying computational problems as polynomial time

solvable, NP-complete, or belonging to a higher level in the polynomial

hierarchy, face the difficulty of undecidability. These classes, including

NP, admit a logic formulation. By suitably restricting the formulation, one

finds the logic class MMSNP, or monotone monadic strict NP without

more >>>

Sanjeev Khanna, Madhu Sudan, Luca Trevisan

This paper continues the work initiated by Creignou [Cre95] and

Khanna, Sudan and Williamson [KSW96] who classify maximization

problems derived from boolean constraint satisfaction. Here we

study the approximability of {\em minimization} problems derived

thence. A problem in this framework is characterized by a

collection F ...
more >>>

Mikhail Anokhin

We construct a provably pseudo-free family of finite computational groups under the general integer factoring intractability assumption. Moreover, this family has exponential size. But each element of a group in our pseudo-free family is represented by many bit strings.

more >>>Hong Van Le

We develop a method to construct elusive functions using techniques of commutative algebra and algebraic geometry. The key notions of this method are elusive subsets and evaluation mappings. We also develop the effective elimination theory combined with algebraic number field theory in order to construct concrete points outside the image ... more >>>

Prerona Chatterjee, Ramprasad Saptharishi

We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests ... more >>>

Adam Klivans, Pravesh Kothari, Igor Oliveira

Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class $\mathcal{C} \subseteq P/poly$ of Boolean circuits is exactly learnable with membership and equivalence queries in polynomial-time, then $EXP^{NP} \not \subseteq \mathcal{C}$ (the class $EXP^{NP}$ was subsequently improved to $P$ by Hitchcock and ... more >>>

Oded Goldreich, Avi Wigderson

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).

Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ...
more >>>

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let $G$ be a connected bounded-degree graph. Given an edge $e$ in $G$ we would like ... more >>>

Parikshit Gopalan

Explicit construction of Ramsey graphs or graphs with no large clique or independent set has remained a challenging open problem for a long time. While Erdos's probabilistic argument shows the existence of graphs on 2^n vertices with no clique or independent set of size 2n, the best known explicit constructions ... more >>>

Venkatesan Guruswami

We define number-theoretic error-correcting codes based on algebraic

number fields, thereby providing a generalization of Chinese Remainder

Codes akin to the generalization of Reed-Solomon codes to

Algebraic-geometric codes. Our construction is very similar to

(and in fact less general than) the one given by (Lenstra 1986), but

the ...
more >>>

Amir Shpilka

In this work we give two new constructions of $\epsilon$-biased

generators. Our first construction answers an open question of

Dodis and Smith, and our second construction

significantly extends a result of Mossel et al.

In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

Luca Trevisan

We introduce a new approach to construct extractors -- combinatorial

objects akin to expander graphs that have several applications.

Our approach is based on error correcting codes and on the Nisan-Wigderson

pseudorandom generator. An application of our approach yields a

construction that is simple to ...
more >>>

Russell Impagliazzo, Valentine Kabanets

We give a simple combinatorial proof of the Chernoff-Hoeffding concentration bound~\cite{Chernoff, Hof63}, which says that the sum of independent $\{0,1\}$-valued random variables is highly concentrated around the expected value. Unlike the standard proofs,

our proof does not use the method of higher moments, but rather uses a simple ...
more >>>

Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

Vijay V. Vazirani, Wang Lei

Following up on the work of Megiddo and Vazirani \cite{MV.2007}, who

determined continuity properties of equilibrium prices and

allocations for perhaps the simplest market model, Fisher's linear

case, we do the same for:

\begin{itemize}

\item

Fisher's model with piecewise-linear, concave utilities

\item

Fisher's model with spending constraint utilities

\item

Arrow-Debreu's ...
more >>>

Michael Burr, Felix Krahmer, Chee Yap

Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of $f$ in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation.

more >>>

Joan Bruna, Oded Regev, Min Jae Song, Yi Tang

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues ... more >>>

Nicola Galesi, Navid Talebanfard, Jacobo Toran

We characterize several complexity measures for the resolution of Tseitin formulas in terms of a two person cop-robber game. Our game is a slight variation of the one Seymour and Thomas used in order to characterize the tree-width parameter. For any undirected graph, by counting the number of cops needed ... more >>>

Mahdi Cheraghchi, Anna Gal, Andrew Mills

Locally decodable codes (LDCs) are error correcting codes with the extra property that it is sufficient to read just a small number of positions of a possibly corrupted codeword in order to recover any one position of the input. To achieve this, it is necessary to use randomness in the ... more >>>

Emanuele Viola

A survey on correlation bounds against polynomials.

more >>>Ruiwen Chen, Valentine Kabanets

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

Shiteng Chen, Periklis Papakonstantinou

We show that for any coprime $m,r$ there is a circuit of the form $\text{MOD}_m\circ \text{AND}_{d(n)}$ whose correlation with $\text{MOD}_r$ is at least $2^{-O\left( \frac{n}{d(n)} \right) }$. This is the first correlation lower bound for arbitrary $m,r$, whereas previously lower bounds were known for prime $m$. Our motivation is the ... more >>>

Hamed Hatami, Shachar Lovett

Recently there has been much interest in Gowers uniformity norms from the perspective of theoretical computer science. This is mainly due to the fact that these norms provide a method for testing whether the maximum correlation of a function $f:\mathbb{F}_p^n \rightarrow \mathbb{F}_p$ with polynomials of degree at most $d \le ... more >>>

Tali Kaufman, David Mass

In this work we show a general reduction from high dimensional complexes to their links based on the spectral properties of the links. We use this reduction to show that if a certain property is testable in the links, then it is also testable in the complex. In particular, we ... more >>>

Oded Goldreich, Guy Rothblum

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}

\item{\em A worst-case to average-case reduction}:

We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ...
more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Predrag Tosic

We study counting various types of con gurations in certain classes of graph

automata viewed as discrete dynamical systems. The graph automata models

of our interest are Sequential and Synchronous Dynamical Systems (SDSs and

SyDSs, respectively). These models have been proposed as a mathematical foun-

dation for a theory of ...
more >>>

Jui-Lin Lee

In this paper we first give a uniform $AC^0$ algorithm which uses

partial sums to compute multiple addition. Then we use it to show

that multiple addition is computable in uniform $TC^0$ by using

$count$ only once sequentially. By constructing bit matrix for

multiple addition, ...
more >>>

Andreas Krebs, Nutan Limaye, Meena Mahajan

We give a \#NC$^1$ upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran (BCGR: SICOMP 21(4), 1992). We also show that the problem is \#NC$^1$ hard. Our ... more >>>

Dana Ron, Mira Gonen, Yuval Shavitt

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

We consider the problem of counting the number of copies of a fixed graph $H$ within an input graph $G$. This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input $G$ has {\em bounded degeneracy}. ... more >>>

Simon Straub, Thomas Thierauf, Fabian Wagner

Counting the number of perfect matchings in arbitrary graphs is a $\#$P-complete problem. However, for some restricted classes of graphs the problem can be solved efficiently. In the case of planar graphs, and even for $K_{3,3}$-free graphs, Vazirani showed that it is in NC$^2$. The technique there is to compute ... more >>>

Christian Glaßer

We study the power of balanced regular leaf-languages.

First, we investigate (i) regular languages that are

polylog-time reducible to languages in dot-depth 1/2 and

(ii) regular languages that are polylog-time decidable.

For both classes we provide

- forbidden-pattern characterizations, and

- characterizations in terms of regular expressions.

Both ... more >>>

Andreas Lenz, Cyrus Rashtchian, Paul Siegel, Eitan Yaakobi

A covering code is a set of codewords with the property that the union of balls, suitably defined, around these codewords covers an entire space. Generally, the goal is to find the covering code with the minimum size codebook. While most prior work on covering codes has focused on the ... more >>>

Irit Dinur, Gillat Kol

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>

Prahladh Harsha, Tulasi mohan Molli, A. Shankar

Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function $f : \{0, 1\}^n\to \{0, 1\}$ is the minimum $\lambda \geq 1$ such that for all positive integers $t$,

\[Pr_{\rho\sim R_p} [\text{DT}_{\text{depth}}(f|_\rho) \geq t] \leq (p\lambda)^t.\]

.

Håstad’s celebrated switching lemma ...
more >>>

Kasper Green Larsen, Omri Weinstein, Huacheng Yu

This paper proves the first super-logarithmic lower bounds on the cell probe complexity of dynamic \emph{boolean} (a.k.a. decision) data structure problems, a long-standing milestone in data structure lower bounds.

We introduce a new method for proving dynamic cell probe lower bounds and use it to prove a $\tilde{\Omega}(\log^{1.5} ...
more >>>

Miroslav Chlebik, Janka Chlebíková

Hemanta Maji, Manoj Prabhakaran, Mike Rosulek

Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question.

We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ...
more >>>

Manoj Prabhakaran, Mike Rosulek

We develop new tools to study the relative complexities of secure

multi-party computation tasks (functionalities) in the Universal

Composition framework. When one task can be securely realized using

another task as a black-box, we interpret this as a

qualitative, complexity-theoretic reduction between the two tasks.

Virtually all previous characterizations of ...
more >>>

Aggelos Kiayias, Moti Yung

We investigate the decoding problem of Reed-Solomon Codes (aka: the Polynomial Reconstruction Problem -- PR) from a cryptographic hardness perspective. First, following the standard methodology for constructing cryptographically strong primitives, we formulate a decisional intractability assumption related to the PR problem. Then, based on this assumption we show: (i) hardness ... more >>>

Benny Applebaum

Constant parallel-time cryptography allows to perform complex cryptographic tasks at an ultimate level of parallelism, namely, by local functions that each of their output bits depend on a constant number of input bits. A natural way to obtain local cryptographic constructions is to use \emph{random local functions} in which each ... more >>>

Adam Klivans, Alexander A. Sherstov

We give the first representation-independent hardness results for

PAC learning intersections of halfspaces, a central concept class

in computational learning theory. Our hardness results are derived

from two public-key cryptosystems due to Regev, which are based on the

worst-case hardness of well-studied lattice problems. Specifically, we

prove that a polynomial-time ...
more >>>

Eric Allender, John Gouwar, Shuichi Hirahara, Caleb Robelle

A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexity of MCSP hold also for MKTP (the problem of computing the KT ... more >>>

Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Vasudevan

Reductions between problems, the mainstay of theoretical computer science, efficiently map an instance of one problem to an instance of another in such a way that solving the latter allows solving the former. The subject of this work is ``lossy'' reductions, where the reduction loses some information about the input ... more >>>

Yanyi Liu, Rafael Pass

Let $\mktp[s]$ be the set of strings $x$ such that $K^t(x) \leq s(|x|)$, where $K^t(x)$ denotes the $t$-bounded Kolmogorov complexity of the truthtable described by $x$. Our main theorem shows that for an appropriate notion of mild average-case hardness, for every $\varepsilon>0$, polynomial $t(n) \geq (1+\varepsilon)n$, and every ``nice'' class ... more >>>

Madhur Tulsiani

We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck recently showed the first integrality gaps for these

problems, showing that for MAX k-XOR, the ratio of the SDP optimum to the integer optimum may be as large as ...
more >>>

Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2SAT, HornSAT, ... more >>>

Amey Bhangale, Irit Dinur, Inbal Livni Navon

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a ... more >>>

Anna Gal, Avishay Tal, Adrian Trejo Nuñez

We define new functions based on the Andreev function and prove that they require $n^{3}/polylog(n)$ formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the ... more >>>

Paul Beame, Niels Kornerup

Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of ... more >>>

Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo

We exhibit a polynomial time computable plane curve GAMMA that has finite length, does not intersect itself, and is smooth except at one endpoint, but has the following property. For every computable parametrization f of GAMMA and every positive integer n, there is some positive-length subcurve of GAMMA that f ... more >>>