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

**E**

__
TR07-048
| 3rd April 2007
__

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer#### Earth Mover Distance over High-Dimensional Spaces

__
TR18-021
| 30th January 2018
__

Omri Ben-Eliezer, Eldar Fischer#### Earthmover Resilience and Testing in Ordered Structures

__
TR18-080
| 6th March 2018
__

Moritz Gobbert#### Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games

__
TR05-163
| 19th December 2005
__

Dvir Falik, Alex Samorodnitsky#### Edge-isoperimetric inequalities and influences

__
TR23-116
| 12th August 2023
__

Amey Bhangale, Subhash Khot, Dor Minzer#### Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$

__
TR10-089
| 26th May 2010
__

Iftach Haitner, Omer Reingold, Salil Vadhan#### Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

__
TR07-094
| 3rd August 2007
__

Christian Glaßer, Heinz Schmitz, Victor Selivanov#### Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

__
TR06-033
| 2nd March 2006
__

Amit Agarwal, Elad Hazan#### Efficient Algorithms for Online Game Playing and Universal Portfolio Management

__
TR01-053
| 17th July 2001
__

Piotr Berman, Marek Karpinski#### Efficient Amplifiers and Bounded Degree Optimization

__
TR02-045
| 8th July 2002
__

Daniele Micciancio, Erez Petrank#### Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol

__
TR09-079
| 21st September 2009
__

Victor Chen, Elena Grigorescu, Ronald de Wolf#### Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

__
TR94-016
| 12th December 1994
__

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu#### Efficient Average-Case Algorithms for the Modular Group

__
TR18-022
| 1st February 2018
__

Omer Reingold, Guy Rothblum, Ron Rothblum#### Efficient Batch Verification for UP

__
TR19-063
| 28th April 2019
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Efficient Black-Box Identity Testing for Free Group Algebra

__
TR05-158
| 12th December 2005
__

Chris Peikert, Alon Rosen#### Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

__
TR00-011
| 27th January 2000
__

Sotiris Nikoletseas, Paul Spirakis#### Efficient Communication Establishment in Extremely Unreliable Large Networks

__
TR10-083
| 13th May 2010
__

Mark Braverman, Anup Rao#### Efficient Communication Using Partial Information

Revisions: 1

__
TR06-012
| 17th January 2006
__

Bruno Codenotti, Mauro Leoncini, Giovanni Resta#### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

__
TR22-088
| 15th June 2022
__

Anthony Leverrier, Gilles Zémor#### Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes

Revisions: 1

__
TR13-173
| 28th November 2013
__

Anindya De, Rocco Servedio#### Efficient deterministic approximate counting for low degree polynomial threshold functions

__
TR11-109
| 9th August 2011
__

Zvika Brakerski, Vinod Vaikuntanathan#### Efficient Fully Homomorphic Encryption from (Standard) LWE

__
TR17-074
| 29th April 2017
__

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S#### Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

__
TR15-047
| 2nd April 2015
__

Swastik Kopparty, Mrinal Kumar, Michael Saks#### Efficient indexing of necklaces and irreducible polynomials over finite fields

__
TR22-095
| 5th July 2022
__

Meghal Gupta, Rachel Zhang#### Efficient Interactive Coding Achieving Optimal Error Resilience Over the Binary Channel

__
TR12-043
| 16th April 2012
__

Zvika Brakerski, Yael Tauman Kalai#### Efficient Interactive Coding Against Adversarial Noise

Revisions: 1

__
TR23-097
| 2nd July 2023
__

Joshua Cook, Ron D. Rothblum#### Efficient Interactive Proofs for Non-Deterministic Bounded Space

Revisions: 1

__
TR20-025
| 20th February 2020
__

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari#### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

__
TR22-122
| 29th August 2022
__

Young Kun Ko#### Efficient Linearization Implies the Multiphase Conjecture

__
TR20-169
| 11th November 2020
__

Zeyu Guo, Noga Ron-Zewi#### Efficient List-Decoding with Constant Alphabet and List Sizes

Revisions: 1

__
TR15-116
| 21st July 2015
__

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky#### Efficient Low-Redundancy Codes for Correcting Multiple Deletions

Revisions: 1

__
TR22-025
| 15th February 2022
__

Oliver Korten#### Efficient Low-Space Simulations From the Failure of the Weak Pigeonhole Principle

Revisions: 3

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR21-118
| 11th August 2021
__

Daniel Augot, Sarah Bordage, Jade Nardi#### Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Revisions: 1

__
TR07-053
| 27th April 2007
__

Jens Groth, Amit Sahai#### Efficient Non-interactive Proof Systems for Bilinear Groups

__
TR11-073
| 3rd May 2011
__

Andrew Drucker#### Efficient Probabilistically Checkable Debates

__
TR20-125
| 17th August 2020
__

Gaurav Sinha#### Efficient reconstruction of depth three circuits with top fan-in two

Revisions: 2

__
TR22-148
| 11th November 2022
__

Peter Ivanov, Raghu Meka, Emanuele Viola#### Efficient resilient functions

__
TR10-155
| 14th October 2010
__

Brendan Juba, Madhu Sudan#### Efficient Semantic Communication via Compatible Beliefs

__
TR00-034
| 5th June 2000
__

Valentine Kabanets, Charles Rackoff, Stephen Cook#### Efficiently Approximable Real-Valued Functions

__
TR11-042
| 25th March 2011
__

Ankur Moitra#### Efficiently Coding for Interactive Communication

Revisions: 1

__
TR19-008
| 20th January 2019
__

Ashish Dwivedi, Rajat Mittal, Nitin Saxena#### Efficiently factoring polynomials modulo $p^4$

__
TR06-029
| 21st February 2006
__

Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani#### Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

__
TR13-127
| 15th September 2013
__

Paul Beame, Raphael Clifford, Widad Machmouchi#### Element Distinctness, Frequency Moments, and Sliding Windows

__
TR97-018
| 8th May 1997
__

Oded Goldreich, Shai Halevi#### Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

__
TR20-088
| 9th June 2020
__

Bill Fefferman, Zachary Remscrim#### Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

__
TR21-087
| 22nd June 2021
__

Uma Girish, Ran Raz#### Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

__
TR21-103
| 18th July 2021
__

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit#### Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields

Revisions: 1

__
TR08-001
| 5th January 2008
__

Ran Raz#### Elusive Functions and Lower Bounds for Arithmetic Circuits

__
TR14-063
| 23rd April 2014
__

Adam Klivans, Pravesh Kothari#### Embedding Hard Learning Problems into Gaussian Space

__
TR17-012
| 17th January 2017
__

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau#### Emptiness Problems for Integer Circuits

__
TR13-080
| 4th June 2013
__

Dmytro Gavinsky, Shachar Lovett#### En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

__
TR21-054
| 14th April 2021
__

James Cook, Ian Mertz#### Encodings and the Tree Evaluation Problem

__
TR06-138
| 13th November 2006
__

Kei Uchizawa, Rodney Douglas#### Energy Complexity and Entropy of Threshold Circuits

__
TR11-159
| 27th November 2011
__

Oded Goldreich, Ron Rothblum#### Enhancements of Trapdoor Permutations

Revisions: 1
,
Comments: 1

__
TR08-019
| 6th March 2008
__

Stasys Jukna#### Entropy of operators or why matrix multiplication is hard for small depth circuits

Revisions: 1

__
TR14-112
| 23rd August 2014
__

Louay Bazzi#### Entropy of weight distributions of small-bias spaces and pseudobinomiality

Revisions: 1

__
TR01-018
| 23rd February 2001
__

Omer Reingold, Salil Vadhan, Avi Wigderson#### Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

__
TR04-015
| 24th February 2004
__

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet#### Enumerations of the Kolmogorov Function

__
TR18-206
| 3rd December 2018
__

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals#### Equality Alone Does Not Simulate Randomness

Revisions: 1

__
TR07-136
| 28th November 2007
__

Felix Brandt, Felix Fischer, Markus Holzer#### Equilibria of Graphical Games with Symmetries

__
TR10-010
| 16th January 2010
__

Shachar Lovett#### Equivalence of polynomial conjectures in additive combinatorics

__
TR14-001
| 4th January 2014
__

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka#### Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

__
TR19-143
| 25th October 2019
__

Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian#### Equivalence of Systematic Linear Data Structures and Matrix Rigidity

__
TR09-108
| 31st October 2009
__

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky#### Equivalence of Uniform Key Agreement and Composition Insecurity

Revisions: 1

__
TR22-099
| 14th July 2022
__

Nikhil Gupta, Chandan Saha, Bhargav Thankey#### Equivalence Test for Read-Once Arithmetic Formulas

__
TR20-190
| 29th November 2020
__

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma#### Erasure-Resilient Sublinear-Time Graph Algorithms

__
TR18-195
| 18th November 2018
__

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma#### Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

__
TR11-081
| 15th May 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar#### Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

__
TR20-038
| 15th March 2020
__

Ofer Grossman, Justin Holmgren#### Error Correcting Codes for Uncompressed Messages

__
TR22-117
| 23rd August 2022
__

Ronen Shaltiel, Jad Silbak#### Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

__
TR21-020
| 15th February 2021
__

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

__
TR01-001
| 31st December 2000
__

Jin-Yi Cai#### Essentially every unimodular matrix defines an expander

__
TR13-087
| 4th June 2013
__

Hamed Hatami, Shachar Lovett#### Estimating the distance from testable affine-invariant properties

__
TR10-180
| 18th November 2010
__

Gregory Valiant, Paul Valiant#### Estimating the unseen: A sublinear-sample canonical estimator of distributions

__
TR20-135
| 9th September 2020
__

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen#### Estimation of Graph Isomorphism Distance in the Query World

Revisions: 3

__
TR15-074
| 29th April 2015
__

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein#### ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

__
TR18-093
| 10th May 2018
__

Irit Dinur, Pasin Manurangsi#### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

__
TR06-009
| 10th January 2006
__

Nutan Limaye, Meena Mahajan, Jayalal Sarma#### Evaluating Monotone Circuits on Cylinders, Planes and Tori

__
TR22-147
| 10th November 2022
__

Samir Datta, Chetan Gupta#### Evaluating Monotone Circuits on Surfaces

Revisions: 3

__
TR13-140
| 8th October 2013
__

Atri Rudra, Mary Wootters#### Every list-decodable code for high noise has abundant near-optimal rate puncturings

__
TR12-184
| 26th December 2012
__

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett#### Every locally characterized affine-invariant property is testable.

Revisions: 1

__
TR08-010
| 17th January 2008
__

Itai Benjamini, Oded Schramm, Asaf Shapira#### Every Minor-Closed Property of Sparse Graphs is Testable

__
TR18-050
| 15th March 2018
__

Irit Dinur, Oded Goldreich, Tom Gur#### Every set in P is strongly testable under a suitable encoding

__
TR06-120
| 12th September 2006
__

Leslie G. Valiant#### Evolvability

__
TR01-014
| 7th February 2001
__

Marcos Kiwi, Frederic Magniez, Miklos Santha#### Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

__
TR16-139
| 8th September 2016
__

Ludwig Staiger#### Exact constructive and computable dimensions

Revisions: 1

__
TR11-074
| 27th April 2011
__

Ludwig Staiger#### Exact constructive dimension

Revisions: 1

__
TR07-049
| 1st June 2007
__

Beate Bollig, Niko Range, Ingo Wegener#### Exact OBDD Bounds for some Fundamental Functions

__
TR13-112
| 12th August 2013
__

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf#### Exact Perfect Matching in Complete Graphs

__
TR18-116
| 18th June 2018
__

Xue Chen, David Zuckerman#### Existence of Simple Extractors

Revisions: 1

__
TR05-138
| 22nd November 2005
__

Peter Bürgisser, Felipe Cucker#### Exotic quantifiers, complexity classes, and complete problems

__
TR16-144
| 15th September 2016
__

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky#### Expander Construction in VNC${}^1$

Revisions: 2

__
TR20-163
| 5th November 2020
__

Gil Cohen, Noam Peri, Amnon Ta-Shma#### Expander Random Walks: A Fourier-Analytic Approach

__
TR21-091
| 29th June 2021
__

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma#### Expander Random Walks: The General Case and Limitations

__
TR18-159
| 11th September 2018
__

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell#### Expander-Based Cryptography Meets Natural Proofs

Revisions: 2

__
TR05-079
| 25th July 2005
__

Stasys Jukna#### Expanders and time-restricted branching programs

__
TR11-140
| 31st October 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev#### Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

__
TR20-136
| 11th September 2020
__

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani#### Explicit and structured sum of squares lower bounds from high dimensional expanders

__
TR18-032
| 14th February 2018
__

Gil Cohen, Bernhard Haeupler, Leonard Schulman#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Revisions: 1

__
TR21-154
| 10th November 2021
__

Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz#### Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

__
TR05-133
| 17th November 2005
__

Venkatesan Guruswami, Atri Rudra#### Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

__
TR09-121
| 22nd November 2009
__

Zohar Karnin, Yuval Rabani, Amir Shpilka#### Explicit Dimension Reduction and Its Applications

__
TR23-058
| 23rd April 2023
__

Xin Li, Yan Zhong#### Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs

__
TR21-148
| 3rd November 2021
__

Benjamin Diamond, Amir Yehudayoff#### Explicit Exponential Lower Bounds for Exact Hyperplane Covers

Revisions: 1

__
TR20-106
| 15th July 2020
__

Eshan Chattopadhyay, Jesse Goodman#### Explicit Extremal Designs and Applications to Extractors

Revisions: 5

__
TR16-134
| 29th August 2016
__

Ronen Shaltiel, Jad Silbak#### Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

Revisions: 1

__
TR09-088
| 29th September 2009
__

Shachar Lovett, Yoav Tzur#### Explicit lower bound for fooling polynomials by the sum of small-bias generators

__
TR22-077
| 13th May 2022
__

Max Hopkins, Ting-Chun Lin#### Explicit Lower Bounds Against $\Omega(n)$-Rounds of Sum-of-Squares

__
TR13-104
| 20th July 2013
__

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin#### Explicit Maximally Recoverable Codes with Locality

__
TR13-033
| 1st March 2013
__

Michael Forbes, Amir Shpilka#### Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

__
TR14-069
| 5th May 2014
__

Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran#### Explicit Non-Malleable Codes Resistant to Permutations

__
TR16-036
| 13th March 2016
__

Eshan Chattopadhyay, Xin Li#### Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols

Revisions: 3

__
TR12-016
| 24th February 2012
__

Anindya De, Elchanan Mossel#### Explicit Optimal hardness via Gaussian stability results

Revisions: 3

__
TR13-170
| 2nd December 2013
__

Venkatesan Guruswami, Carol Wang#### Explicit rank-metric codes list-decodable with optimal redundancy

__
TR12-117
| 17th September 2012
__

Loïck Magnin, Jérémie Roland#### Explicit relation between all lower bound techniques for quantum query complexity

__
TR15-144
| 1st September 2015
__

Raghu Meka#### Explicit resilient functions matching Ajtai-Linial

Revisions: 1

__
TR23-124
| 24th August 2023
__

Zander Kelley, Shachar Lovett, Raghu Meka#### Explicit separations between randomized and deterministic Number-on-Forehead communication

__
TR15-020
| 31st January 2015
__

Michael Viderman#### Explicit Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 3

__
TR13-060
| 10th April 2013
__

Venkatesan Guruswami, Swastik Kopparty#### Explicit Subspace Designs

__
TR15-119
| 23rd July 2015
__

Eshan Chattopadhyay, David Zuckerman#### Explicit Two-Source Extractors and Resilient Functions

Revisions: 5

__
TR16-088
| 1st June 2016
__

Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma#### Explicit two-source extractors for near-logarithmic min-entropy

__
TR20-047
| 16th April 2020
__

Ronen Shaltiel, Jad Silbak#### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity

Revisions: 2

__
TR17-041
| 6th March 2017
__

Amnon Ta-Shma#### Explicit, almost optimal, epsilon-balanced codes

__
TR02-059
| 9th August 2002
__

Iordanis Kerenidis, Ronald de Wolf#### Exponential Lower Bound for 2-Query Locally Decodable Codes

__
TR07-107
| 26th October 2007
__

Nathan Segerlind#### Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures

__
TR16-064
| 19th April 2016
__

Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman#### Exponential Lower Bounds for Monotone Span Programs

__
TR13-018
| 29th January 2013
__

Luke Friedman, Yixin Xu#### Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

__
TR97-007
| 21st February 1997
__

Stasys Jukna#### Exponential Lower Bounds for Semantic Resolution

__
TR04-041
| 18th May 2004
__

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson#### Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

__
TR13-110
| 12th August 2013
__

Xiaoming Sun, Marcos Villagra#### Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity

__
TR19-174
| 2nd December 2019
__

Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov#### Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs

__
TR17-176
| 15th November 2017
__

Kamil Khadiev, Aliya Khadiev, Alexander Knop#### Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

__
TR18-204
| 30th November 2018
__

Makrand Sinha, Ronald de Wolf#### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank

Comments: 1

__
TR19-089
| 21st June 2019
__

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal#### Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

__
TR15-088
| 31st May 2015
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Communication and External Information

__
TR14-049
| 11th April 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication

Revisions: 1

__
TR14-113
| 27th August 2014
__

Anat Ganor, Gillat Kol, Ran Raz#### Exponential Separation of Information and Communication for Boolean Functions

__
TR07-074
| 7th August 2007
__

Dmytro Gavinsky, Pavel Pudlak#### Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

__
TR04-036
| 27th March 2004
__

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

__
TR06-086
| 25th July 2006
__

Dmytro Gavinsky, Julia Kempe, Ronald de Wolf#### Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

__
TR98-035
| 8th May 1998
__

Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen#### Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

__
TR13-072
| 3rd May 2013
__

Jan Johannsen#### Exponential Separations in a Hierarchy of Clause Learning Proof Systems

__
TR10-078
| 27th April 2010
__

Holger Dell, Thore Husfeldt, Martin Wahlén#### Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

__
TR04-064
| 25th June 2004
__

Piotr Faliszewski#### Exponential time reductions and sparse languages in NEXP

__
TR13-096
| 25th June 2013
__

Dana Ron, Rocco Servedio#### Exponentially improved algorithms and lower bounds for testing signed majorities

__
TR17-096
| 30th May 2017
__

Irit Dinur, Inbal Livni Navon#### Exponentially Small Soundness for the Direct Product Z-test

__
TR17-063
| 10th April 2017
__

Benny Applebaum#### Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

__
TR10-138
| 17th September 2010
__

Eric Allender, Luke Friedman, William Gasarch#### Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

__
TR23-007
| 3rd February 2023
__

Jan Krajicek#### Extended Nullstellensatz proof systems

__
TR22-002
| 11th December 2021
__

Sravanthi Chede, Anil Shukla#### Extending Merge Resolution to a Family of Proof Systems

Revisions: 1

__
TR07-041
| 20th April 2007
__

Nicola Galesi, Massimo Lauria#### Extending Polynomial Calculus to $k$-DNF Resolution

Revisions: 1

__
TR16-070
| 24th April 2016
__

Mika Göös, Rahul Jain, Thomas Watson#### Extension Complexity of Independent Set Polytopes

Revisions: 1

__
TR16-005
| 22nd January 2016
__

Olaf Beyersdorff, Leroy Chew, Mikolas Janota#### Extension Variables in QBF Resolution

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR99-046
| 17th November 1999
__

Ran Raz, Omer Reingold, Salil Vadhan#### Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

__
TR98-047
| 21st August 1998
__

Salil Vadhan#### Extracting All the Randomness from a Weakly Random Source

Revisions: 1
,
Comments: 1

__
TR05-105
| 24th September 2005
__

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang#### Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

__
TR23-092
| 28th June 2023
__

Swastik Kopparty, Vishvajeet N#### Extracting Mergers and Projections of Partitions

__
TR00-059
| 11th August 2000
__

Omer Reingold, Ronen Shaltiel, Avi Wigderson#### Extracting Randomness via Repeated Condensing

__
TR10-118
| 27th July 2010
__

Maurice Jansen#### Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods

Revisions: 2

__
TR19-173
| 28th November 2019
__

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz#### Extractor Lower Bounds, Revisited

Revisions: 1

__
TR17-121
| 31st July 2017
__

Sumegha Garg, Ran Raz, Avishay Tal#### Extractor-Based Time-Space Lower Bounds for Learning

Revisions: 1

__
TR06-134
| 18th October 2006
__

Venkatesan Guruswami, Chris Umans, Salil Vadhan#### Extractors and condensers from univariate polynomials

Revisions: 1

__
TR11-037
| 18th March 2011
__

Anindya De, Thomas Watson#### Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

__
TR00-009
| 21st February 2000
__

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson#### Extractors and pseudo-random generators with optimal seed length

__
TR07-056
| 10th July 2007
__

Zeev Dvir, Ariel Gabizon, Avi Wigderson#### Extractors and Rank Extractors for Polynomial Sources

__
TR13-025
| 6th February 2013
__

Xin Li#### Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

__
TR05-106
| 26th September 2005
__

Anup Rao#### Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

Revisions: 1

__
TR19-184
| 13th December 2019
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Extractors for Adversarial Sources via Extremal Hypergraphs

__
TR15-121
| 25th July 2015
__

Xin Li#### Extractors for Affine Sources with Polylogarithmic Entropy

__
TR11-056
| 14th April 2011
__

Emanuele Viola#### Extractors for circuit sources

__
TR22-169
| 26th November 2022
__

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman#### Extractors for Images of Varieties

Revisions: 1

__
TR08-015
| 23rd January 2008
__

Anup Rao#### Extractors for Low-Weight Affine Sources

__
TR16-014
| 3rd February 2016
__

Gil Cohen, Leonard Schulman#### Extractors for Near Logarithmic Min-Entropy

__
TR23-140
| 20th September 2023
__

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani#### Extractors for Polynomial Sources over $\mathbb{F}_2$

__
TR11-129
| 22nd September 2011
__

Eli Ben-Sasson, Ariel Gabizon#### Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

__
TR19-058
| 16th April 2019
__

Pavel Pudlak, Vojtech Rodl#### Extractors for small zero-fixing sources

__
TR21-147
| 22nd October 2021
__

Eshan Chattopadhyay, Jyun-Jie Liao#### Extractors for Sum of Two Sources

Revisions: 1

__
TR15-178
| 10th November 2015
__

Eshan Chattopadhyay, Xin Li#### Extractors for Sumset Sources

__
TR12-047
| 24th April 2012
__

Emanuele Viola#### Extractors for Turing-machine sources

__
TR01-036
| 2nd May 2001
__

Amnon Ta-Shma, David Zuckerman, Shmuel Safra#### Extractors from Reed-Muller Codes

__
TR04-099
| 11th November 2004
__

Ran Raz#### Extractors with Weak Random Seeds

__
TR21-150
| 7th November 2021
__

Eldon Chung, Maciej Obremski, Divesh Aggarwal#### Extractors: Low Entropy Requirements Colliding With Non-Malleability

__
TR21-158
| 12th November 2021
__

Noah Fleming, Toniann Pitassi, Robert Robere#### Extremely Deep Proofs

Revisions: 1

__
TR22-086
| 9th June 2022
__

Lijie Chen, Jiatu Li, Tianqi Yang#### Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs

Revisions: 1

Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

The Earth Mover Distance (EMD) between two equal-size sets

of points in R^d is defined to be the minimum cost of a

bipartite matching between the two pointsets. It is a natural metric

for comparing sets of features, and as such, it has received

significant interest in computer vision. Motivated ...
more >>>

Omri Ben-Eliezer, Eldar Fischer

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>>

Moritz Gobbert

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... more >>>

Dvir Falik, Alex Samorodnitsky

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).The methods of the proof are then used to recover additional isoperimetric results for the cube, with ... more >>>

Amey Bhangale, Subhash Khot, Dor Minzer

For a prime $p$, a restricted arithmetic progression in $\mathbb{F}_p^n$ is a triplet of vectors $x, x+a, x+2a$ in which the common difference $a$ is a non-zero element from $\{0,1,2\}^n$. What is the size of the largest $A\subseteq \mathbb{F}_p^n$ that is free of restricted arithmetic progressions? We show that the ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

Christian Glaßer, Heinz Schmitz, Victor Selivanov

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

Amit Agarwal, Elad Hazan

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

Piotr Berman, Marek Karpinski

This paper studies the existence of efficient (small size)

amplifiers for proving explicit inaproximability results for bounded degree

and bounded occurrence combinatorial optimization problems, and gives

an explicit construction for such amplifiers. We use this construction

also later to improve the currently best known approximation lower bounds

more >>>

Daniele Micciancio, Erez Petrank

We show how to efficiently transform any public coin honest verifier

zero knowledge proof system into a proof system that is concurrent

zero-knowledge with respect to any (possibly cheating) verifier via

black box simulation. By efficient we mean that our transformation

incurs only an additive overhead, ...
more >>>

Victor Chen, Elena Grigorescu, Ronald de Wolf

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the

decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ...
more >>>

Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

The modular group occupies a central position in many branches of

mathematical sciences. In this paper we give average polynomial-time

algorithms for the unbounded and bounded membership problems for

finitely generated subgroups of the modular group. The latter result

affirms a conjecture of Gurevich.

Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Hrubeš and Wigderson [HW14] initiated the study of

noncommutative arithmetic circuits with division computing a

noncommutative rational function in the free skew field, and

raised the question of rational identity testing. It is now known

that the problem can be solved in deterministic polynomial time in

more >>>

Chris Peikert, Alon Rosen

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i

a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$

elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists

of $m$ coefficients from a specified subset $S \subseteq R$.

Micciancio ...
more >>>

Sotiris Nikoletseas, Paul Spirakis

We consider here a large network of $n$ nodes which supports

only the following unreliable basic communication primitive:

when a node requests communication then this request

{\em may fail}, independently of other requests, with probability

$f<1$. Even if it succeeds, the request is answered by returning

a stable link to ...
more >>>

Mark Braverman, Anup Rao

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.

We ... more >>>

Bruno Codenotti, Mauro Leoncini, Giovanni Resta

It is known that finding a Nash equilibrium for win-lose bimatrix

games, i.e., two-player games where the players' payoffs are zero

and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash

equilibrium for win-lose bimatrix games where the number of winning

positions ...
more >>>

Anthony Leverrier, Gilles Zémor

We introduce and analyse an efficient decoder for the quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n \log n})$. We also work on the link between quantum Tanner codes and the Lifted ... more >>>

Anindya De, Rocco Servedio

We give a deterministic algorithm for

approximately counting satisfying assignments of a degree-$d$ polynomial threshold function

(PTF).

Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$

and a parameter $\epsilon > 0$, our algorithm approximates

$

\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]

$

to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ...
more >>>

Zvika Brakerski, Vinod Vaikuntanathan

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

Swastik Kopparty, Mrinal Kumar, Michael Saks

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

Meghal Gupta, Rachel Zhang

Given a noiseless protocol $\pi_0$ computing a function $f(x, y)$ of Alice and Bob's private inputs $x, y$, the goal of interactive coding is to construct an error-resilient protocol $\pi$ computing $f$ such that even if some fraction of the communication is adversarially corrupted, both parties still learn $f(x, y)$. ... more >>>

Zvika Brakerski, Yael Tauman Kalai

In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given ... more >>>

Joshua Cook, Ron D. Rothblum

The celebrated $\mathbf{IP}=\mathbf{PSPACE}$ Theorem gives an efficient interactive proof for any bounded-space algorithm. In this work we study interactive proofs for non-deterministic bounded space computations. While Savitch's Theorem shows that nondeterministic bounded-space algorithms can be simulated by deterministic bounded-space algorithms, this simulation has a quadratic overhead. We give interactive protocols ... more >>>

Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari

We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists.

As a consequence, we obtain that deciding whether the ... more >>>

Young Kun Ko

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... more >>>

Zeyu Guo, Noga Ron-Zewi

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate $R$, over an alphabet of size ... more >>>

Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

Oliver Korten

A recurring challenge in the theory of pseudorandomness and circuit complexity is the explicit construction of ``incompressible strings,'' i.e. finite objects which lack a specific type of structure or simplicity. In most cases, there is an associated NP search problem which we call the ``compression problem,'' where we are given ... more >>>

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Daniel Augot, Sarah Bordage, Jade Nardi

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an

oracle function $f : L^m \rightarrow \mathbb F_q$, where $L\subset \mathbb F_q$, a verifier distinguishes whether $f$ is the evaluation of a ...
more >>>

Jens Groth, Amit Sahai

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as ... more >>>

Andrew Drucker

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

Gaurav Sinha

In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree $2$. Such circuits naturally compute polynomials of the form $G\times(T_1 + T_2)$, ... more >>>

Peter Ivanov, Raghu Meka, Emanuele Viola

An $n$-bit boolean function is resilient to coalitions of size $q$

if no fixed set of $q$ bits is likely to influence the value of the

function when the other $n-q$ bits are chosen uniformly at random,

even though the function is nearly balanced. We construct explicit

functions resilient to ...
more >>>

Brendan Juba, Madhu Sudan

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

Valentine Kabanets, Charles Rackoff, Stephen Cook

We consider a class, denoted APP, of real-valued functions

f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to

within any epsilon>0, by a probabilistic Turing machine running in

time poly(n,1/epsilon). We argue that APP can be viewed as a

generalization of BPP, and show that APP contains a natural

complete ...
more >>>

Ankur Moitra

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>>

Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani

We study the structure of EG[2], the class of Eisenberg-Gale markets

with two agents. We prove that all markets in this class are rational and they

admit strongly polynomial algorithms whenever

the polytope containing the set of feasible utilities of the two agents can be described

via a combinatorial LP. ...
more >>>

Paul Beame, Raphael Clifford, Widad Machmouchi

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

Oded Goldreich, Shai Halevi

Following Ajtai's lead, Ajtai and Dwork have recently introduced a

public-key encryption scheme which is secure under the assumption

that a certain computational problem on lattices is hard on the

worst-case. Their encryption method may cause decryption errors,

though with small probability (i.e., inversely proportional to the

more >>>

Bill Fefferman, Zachary Remscrim

A foundational result in the theory of quantum computation known as the ``principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>>

Uma Girish, Ran Raz

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can ... more >>>

Ran Raz

A basic fact in linear algebra is that the image of the curve

$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any

$m-1$ dimensional affine subspace of $C^m$. In other words, the image

of $f$ is not contained in the image of any polynomial-mapping

$G:C^{m-1} ---> C^m$ ...
more >>>

Adam Klivans, Pravesh Kothari

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

Dmytro Gavinsky, Shachar Lovett

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... more >>>

James Cook, Ian Mertz

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>Kei Uchizawa, Rodney Douglas

Circuits composed of threshold gates (McCulloch-Pitts neurons, or

perceptrons) are simplified models of neural circuits with the

advantage that they are theoretically more tractable than their

biological counterparts. However, when such threshold circuits are

designed to perform a specific computational task they usually

differ ...
more >>>

Oded Goldreich, Ron Rothblum

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

Stasys Jukna

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

Louay Bazzi

A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

Omer Reingold, Salil Vadhan, Avi Wigderson

The main contribution of this work is a new type of graph product, which we call the zig-zag

product. Taking a product of a large graph with a small graph, the resulting graph inherits

(roughly) its size from the large one, its degree from the small one, and ...
more >>>

Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

A recursive enumerator for a function $h$ is an algorithm $f$ which

enumerates for an input $x$ finitely many elements including $h(x)$.

$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$

is among the first $k(n)$ elements enumerated by $f$.

If there is a $k(n)$-enumerator for ...
more >>>

Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is `Equality'. In this work, we show that even allowing access to an `Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... more >>>

Felix Brandt, Felix Fischer, Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

Shachar Lovett

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with ... more >>>

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an $NP$ oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... more >>>

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

Nikhil Gupta, Chandan Saha, Bhargav Thankey

We study the polynomial equivalence problem for orbits of read-once arithmetic formulas (ROFs). Read-once formulas have received considerable attention in both algebraic and Boolean complexity and have served as a testbed for developing effective tools and techniques for analyzing circuits. Two $n$-variate polynomials $f, g \in \mathbb{F}[\mathbf{x}]$ are equivalent, denoted ... more >>>

Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

Ofer Grossman, Justin Holmgren

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

Ronen Shaltiel, Jad Silbak

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.

Guruswami and ...
more >>>

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and ... more >>>

Jin-Yi Cai

We generalize the construction of Gabber and Galil

to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that

every parabolic

or hyperbolic fractional linear transformation explicitly

defines an expander of bounded degree

and constant expansion. Thus all but a vanishingly small fraction

of unimodular matrices define expanders.

Hamed Hatami, Shachar Lovett

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>

Gregory Valiant, Paul Valiant

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... more >>>

Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

Irit Dinur, Pasin Manurangsi

We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G = (V, E)$, an alphabet set $\Sigma$ and, for each edge $\{u, v\} \in E$, a constraint $C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment $\sigma: V ... more >>>

Nutan Limaye, Meena Mahajan, Jayalal Sarma

We re-examine the complexity of evaluating monotone planar circuits

MPCVP, with special attention to circuits with cylindrical

embeddings. MPCVP is known to be in NC^3, and for the special

case of upward stratified circuits, it is known to be in

LogDCFL. We characterize cylindricality, which ...
more >>>

Samir Datta, Chetan Gupta

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

Atri Rudra, Mary Wootters

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that ``most" Reed-Solomon codes are list decodable ... more >>>

Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for ... more >>>

Itai Benjamini, Oded Schramm, Asaf Shapira

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

Irit Dinur, Oded Goldreich, Tom Gur

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

Leslie G. Valiant

Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

Marcos Kiwi, Frederic Magniez, Miklos Santha

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered

the theory of self-testing as an alternative way of dealing with

the problem of software reliability.

Over the last decade this theory played a crucial role in

the construction of probabilistically checkable proofs and

the ...
more >>>

Ludwig Staiger

In this paper we derive several results which generalise the constructive

dimension of (sets of) infinite strings to the case of exact dimension. We

start with proving a martingale characterisation of exact Hausdorff

dimension. Then using semi-computable super-martingales we introduce the

notion of exact constructive dimension ...
more >>>

Ludwig Staiger

The present paper generalises results by Lutz and Ryabko. We prove a

martingale characterisation of exact Hausdorff dimension. On this base we

introduce the notion of exact constructive dimension of (sets of) infinite

strings.

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the

...
more >>>

Beate Bollig, Niko Range, Ingo Wegener

Ordered binary decision diagrams (OBDDs) are nowadays the most common

dynamic data structure or representation type for Boolean functions.

Among the many areas of application are verification, model checking,

computer aided design, relational algebra, and symbolic graph algorithms.

Although many even exponential lower bounds on the OBDD size of Boolean ...
more >>>

Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... more >>>

Xue Chen, David Zuckerman

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>>

Peter Bürgisser, Felipe Cucker

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [Annals of Mathematics, 2002], and show that this analysis can be formalized in the bounded-arithmetic system $VNC^1$ (corresponding to the ``$NC^1$ reasoning''). As a corollary, we prove the ... more >>>

Gil Cohen, Noam Peri, Amnon Ta-Shma

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... more >>>

Stasys Jukna

The \emph{replication number} of a branching program is the minimum

number R such that along every accepting computation at most R

variables are tested more than once. Hence 0\leq R\leq n for every

branching program in n variables. The best results so far were

exponential ...
more >>>

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.

Our construction is based on the high-dimensional expanders devised by Lubotzky, ...
more >>>

Gil Cohen, Bernhard Haeupler, Leonard Schulman

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz

Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and $(\log n)^{e}$ colors for some constant $e > 1$ that depends on the distance, where $n$ is ... more >>>

Venkatesan Guruswami, Atri Rudra

For every $0 < R < 1$ and $\eps > 0$, we present an explicit

construction of error-correcting codes of rate $R$ that can be list

decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.

These codes achieve the ``capacity'' for decoding from {\em ...
more >>>

Zohar Karnin, Yuval Rabani, Amir Shpilka

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of

any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at

least a fraction of $1 - o(1)$ of the transformations in the set.

Albeit the tradeoff between ...
more >>>

Xin Li, Yan Zhong

Affine extractors give some of the best-known lower bounds for various computational models, such as AC$^0$ circuits, parity decision trees, and general Boolean circuits. However, they are not known to give strong lower bounds for read-once branching programs (ROBPs). In a recent work, Gryaznov, Pudl\'{a}k, and Talebanfard (CCC' 22) introduced ... more >>>

Benjamin Diamond, Amir Yehudayoff

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>Eshan Chattopadhyay, Jesse Goodman

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

Ronen Shaltiel, Jad Silbak

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

Shachar Lovett, Yoav Tzur

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

Max Hopkins, Ting-Chun Lin

We construct an explicit family of 3-XOR instances hard for $\Omega(n)$-levels of the Sum-of-Squares (SoS) semi-definite programming hierarchy. Not only is this the first explicit construction to beat brute force search (beyond low-order improvements (Tulsiani 2021, Pratt 2021)), combined with standard gap amplification techniques it also matches the (optimal) hardness ... more >>>

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>>

Michael Forbes, Amir Shpilka

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... more >>>

Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value.

In the information theoretic setting, although existence of such codes for various ... more >>>

Eshan Chattopadhyay, Xin Li

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).

For the first ... more >>>

Anindya De, Elchanan Mossel

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... more >>>

Venkatesan Guruswami, Carol Wang

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>

Loïck Magnin, Jérémie Roland

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

Raghu Meka

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... more >>>

Zander Kelley, Shachar Lovett, Raghu Meka

We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function $f:[N]^3 \to \{0,1\}$, such that: (i) there exist a randomized NOF protocol computing it that sends a constant number of bits; but (ii) any deterministic or nondeterministic NOF protocol computing ... more >>>

Michael Viderman

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

Venkatesan Guruswami, Swastik Kopparty

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

Eshan Chattopadhyay, David Zuckerman

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ... more >>>

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

We explicitly construct extractors for two independent $n$-bit sources of $(\log n)^{1+o(1)}$ min-entropy. Previous constructions required either $\mathrm{polylog}(n)$ min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}.

Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>>

Ronen Shaltiel, Jad Silbak

We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... more >>>

Amnon Ta-Shma

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\epsilon}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>>

Iordanis Kerenidis, Ronald de Wolf

We prove exponential lower bounds on the length of 2-query

locally decodable codes. Goldreich et al. recently proved such bounds

for the special case of linear locally decodable codes.

Our proof shows that a 2-query locally decodable code can be decoded

with only 1 quantum query, and then ...
more >>>

Nathan Segerlind

The matrix cuts of Lov{\'{a}}sz and Schrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems with strong guarantees, and to solve certain instances of Boolean satisfiability.

... more >>>Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

Luke Friedman, Yixin Xu

A propositional proof system based on ordered binary decision diagrams (OBDDs) was introduced by Atserias et al. Krajicek proved exponential lower bounds for a strong variant of this system using feasible interpolation, and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived ... more >>>

Stasys Jukna

In a semantic resolution proof we operate with clauses only

but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

__________________

C

Consistency is the only requirement. We prove a very simple

exponential lower bound for the size ...
more >>>

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

Xiaoming Sun, Marcos Villagra

There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>>

Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov

We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense ... more >>>

Kamil Khadiev, Aliya Khadiev, Alexander Knop

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

Makrand Sinha, Ronald de Wolf

Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total

Boolean function, the sink function, that has polynomial approximate rank and

polynomial randomized communication complexity. This gives an exponential

separation between randomized communication complexity and logarithm of the

approximate rank, refuting the log-approximate-rank conjecture. We show that ...
more >>>

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

Anat Ganor, Gillat Kol, Ran Raz

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

Dmytro Gavinsky, Pavel Pudlak

We give the first exponential separation between quantum and

classical multi-party

communication complexity in the (non-interactive) one-way and

simultaneous message

passing settings.

For every k, we demonstrate a relational communication problem

between k parties

that can be solved exactly by a quantum simultaneous message passing

protocol of

cost ...
more >>>

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

Dmytro Gavinsky, Julia Kempe, Ronald de Wolf

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

We prove an exponential lower bound for tree-like Cutting Planes

refutations of a set of clauses which has polynomial size resolution

refutations. This implies an exponential separation between tree-like

and dag-like proofs for both Cutting Planes and resolution; in both

cases only superpolynomial separations were known before.

In order to ...
more >>>

Jan Johannsen

Resolution trees with lemmas ($\mathrm{RTL}$) are a resolution-based propositional proof system that is related to the DPLL algorithm with clause learning. Its fragments $\mathrm{RTL}(k)$ are related to clause learning algorithms where the width of learned clauses is bounded by $k$.

For every $k$ up to $O(\log n)$, an exponential separation ... more >>>

Holger Dell, Thore Husfeldt, Martin Wahlén

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

Piotr Faliszewski

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>Dana Ron, Rocco Servedio

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form

$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ...
more >>>

Irit Dinur, Inbal Livni Navon

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ...
more >>>

Benny Applebaum

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>

Eric Allender, Luke Friedman, William Gasarch

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

Jan Krajicek

For a finite set $\cal F$ of polynomials over a fixed finite prime field of size $p$ containing all polynomials $x^2 - x$, a Nullstellensatz proof of the unsolvability of the system

$$

f = 0\ ,\ \mbox{ all } f \in {\cal F}

$$

is a linear combination ...
more >>>

Sravanthi Chede, Anil Shukla

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores ... more >>>

Nicola Galesi, Massimo Lauria

We introduce an algebraic proof system Pcrk, which combines together {\em Polynomial Calculus} (Pc) and {\em $k$-DNF Resolution} (Resk).

This is a natural generalization to Resk of the well-known {\em Polynomial Calculus with Resolution} (Pcr) system which combines together Pc and Resolution.

We study the complexity of proofs in such ... more >>>

Mika Göös, Rahul Jain, Thomas Watson

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

Olaf Beyersdorff, Leroy Chew, Mikolas Janota

We investigate two QBF resolution systems that use extension variables: weak extended Q-resolution, where the extension variables are quantified at the innermost level, and extended Q-resolution, where the extension variables can be placed inside the quantifier prefix. These systems have been considered previously by Jussila et al. '07 who ... more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ...
more >>>

Ran Raz, Omer Reingold, Salil Vadhan

We give explicit constructions of extractors which work for a source of

any min-entropy on strings of length n. These extractors can extract any

constant fraction of the min-entropy using O(log^2 n) additional random

bits, and can extract all the min-entropy using O(log^3 n) additional

random bits. Both of these ...
more >>>

Salil Vadhan

In this paper, we give explicit constructions of extractors which work for

a source of any min-entropy on strings of length $n$. The first

construction extracts any constant fraction of the min-entropy using

O(log^2 n) additional random bits. The second extracts all the

min-entropy using O(log^3 n) additional random ...
more >>>

Lance Fortnow, John Hitchcock, A. Pavan, N. V. Vinodchandran, Fengming Wang

We apply recent results on extracting randomness from independent

sources to ``extract'' Kolmogorov complexity. For any $\alpha,

\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show

how to use a constant number of advice bits to efficiently

compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >

(1-\epsilon)|y|$. ...
more >>>

Swastik Kopparty, Vishvajeet N

We study the problem of extracting randomness from somewhere random sources, and related combinatorial phenomena: partition analogues of Shearer's lemma on projections.

A somewhere-random source is a tuple $(X_1, \ldots, X_t)$ of (possibly correlated) $\{0,1\}^n$-valued random variables $X_i$ where for some unknown $i \in [t]$, $X_i$ is guaranteed to be ... more >>>

Omer Reingold, Ronen Shaltiel, Avi Wigderson

On an input probability distribution with some (min-)entropy

an {\em extractor} outputs a distribution with a (near) maximum

entropy rate (namely the uniform distribution).

A natural weakening of this concept is a condenser, whose

output distribution has a higher entropy rate than the

input distribution (without losing

much of ...
more >>>

Maurice Jansen

For two polynomials $f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y]$ and $p \in \mathbb{F}[x_1, x_2, \ldots, x_n]$, we say that $p$ is a root of $f$, if $f(x_1, x_2, \ldots, x_n, p) \equiv 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits ... more >>>

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>

Sumegha Garg, Ran Raz, Avishay Tal

A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

Venkatesan Guruswami, Chris Umans, Salil Vadhan

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

Anindya De, Thomas Watson

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

We give the first construction of a pseudo-random generator with

optimal seed length that uses (essentially) arbitrary hardness.

It builds on the novel recursive use of the NW-generator in

a previous paper by the same authors, which produced many optimal

generators one of which was pseudo-random. This is achieved ...
more >>>

Zeev Dvir, Ariel Gabizon, Avi Wigderson

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

Xin Li

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

Anup Rao

We consider the problem of bit extraction from independent sources. We

construct an extractor that can extract from a constant number of

independent sources of length $n$, each of which have min-entropy

$n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our

constructions are different from recent extractor constructions

more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... more >>>

Xin Li

We give the first explicit construction of deterministic extractors for affine sources over $F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>

Emanuele Viola

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>

Anup Rao

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... more >>>

Gil Cohen, Leonard Schulman

The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any $\delta > 0$ we construct an extractor for $O(1/\delta)$ $n$-bit sources with min-entropy $(\log{n})^{1+\delta}$. This is most interesting when $\delta$ is set to a small constant, though the result also yields an ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>

Eli Ben-Sasson, Ariel Gabizon

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... more >>>

Pavel Pudlak, Vojtech Rodl

A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical ... more >>>

Eshan Chattopadhyay, Jyun-Jie Liao

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits ... more >>>

Eshan Chattopadhyay, Xin Li

We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give ... more >>>

Emanuele Viola

We obtain the first deterministic randomness extractors

for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$

generated (or sampled) by single-tape Turing machines

running in time $n^{2-16 \alpha}$, for all sufficiently

small $\alpha > 0$. We also show that such machines

cannot sample a uniform $n$-bit input to the Inner

Product function ...
more >>>

Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

Ran Raz

We show how to extract random bits from two or more independent

weak random sources, in cases where only one source is of linear

min-entropy and all other sources are of logarithmic min-entropy.

We also give improved constructions of mergers and condensers.

In all that comes below, $\delta$ is an ...
more >>>

Eldon Chung, Maciej Obremski, Divesh Aggarwal

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.

(2) Constructions where one source is uniform, and the other ...
more >>>

Noah Fleming, Toniann Pitassi, Robert Robere

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

Lijie Chen, Jiatu Li, Tianqi Yang

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by ... more >>>