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

**B**

__
TR23-155
| 25th October 2023
__

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep#### Baby PIH: Parameterized Inapproximability of Min CSP

__
TR18-055
| 26th March 2018
__

Titus Dose#### Balance Problems for Integer Circuits

Revisions: 5

__
TR09-012
| 4th February 2009
__

Noga Alon, Shai Gutner#### Balanced Hashing, Color Coding and Approximate Counting

__
TR06-088
| 9th July 2006
__

Per Austrin#### Balanced Max 2-Sat might not be the hardest

__
TR11-068
| 27th April 2011
__

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder#### Balls and Bins: Smaller Hash Families and Faster Evaluation

__
TR17-162
| 26th October 2017
__

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson#### Barriers for Rank Methods in Arithmetic Complexity

__
TR20-030
| 9th March 2020
__

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam#### Barriers for Rectangular Matrix Multiplication

__
TR15-180
| 4th November 2015
__

Bo Tang, Jiapeng Zhang#### Barriers to Black-Box Constructions of Traitor Tracing Systems

__
TR07-003
| 5th January 2007
__

Jin-Yi Cai, Pinyan Lu#### Bases Collapse in Holographic Algorithms

__
TR14-127
| 11th October 2014
__

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song#### Batch Codes through Dense Graphs without Short Cycles

__
TR23-077
| 25th May 2023
__

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan#### Batch Proofs are Statistically Hiding

Revisions: 4

__
TR20-157
| 21st October 2020
__

Guy Rothblum, Ron Rothblum#### Batch Verification and Proofs of Proximity with Polylog Overhead

__
TR20-147
| 24th September 2020
__

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon#### Batch Verification for Statistical Zero Knowledge Proofs

Revisions: 1

__
TR01-078
| 6th November 2001
__

Matthias Krause#### BDD-based Cryptanalysis of Keystream Generators

__
TR23-171
| 15th November 2023
__

Shuichi Hirahara, Rahul Ilango, Ryan Williams#### Beating Brute Force for Compression Problems

__
TR18-111
| 4th June 2018
__

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay#### Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits

Comments: 1

__
TR18-096
| 13th May 2018
__

Venkatesan Guruswami, Andrii Riazanov#### Beating Fredman-Komlós for perfect $k$-hashing

__
TR19-108
| 23rd August 2019
__

Chaoping Xing, chen yuan#### Beating the probabilistic lower bound on perfect hashing

Revisions: 2

__
TR15-082
| 13th May 2015
__

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright#### Beating the random assignment on constraint satisfaction problems of bounded degree

__
TR11-027
| 28th February 2011
__

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar#### Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant

__
TR07-109
| 7th October 2007
__

Venkatesan Guruswami, Atri Rudra#### Better Binary List-Decodable Codes via Multilevel Concatenation

__
TR17-072
| 25th April 2017
__

Eric Allender, Andreas Krebs, Pierre McKenzie#### Better Complexity Bounds for Cost Register Machines

Revisions: 1

__
TR03-080
| 12th November 2003
__

Venkatesan Guruswami#### Better Extractors for Better Codes?

__
TR10-164
| 4th November 2010
__

Falk Unger#### Better gates can make fault-tolerant computation impossible

Revisions: 1

__
TR21-048
| 27th March 2021
__

William Hoza#### Better Pseudodistributions and Derandomization for Space-Bounded Computation

Revisions: 1

__
TR12-123
| 28th September 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan#### Better pseudorandom generators from milder pseudorandom restrictions

__
TR20-008
| 26th January 2020
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter#### Better Secret-Sharing via Robust Conditional Disclosure of Secrets

Revisions: 2

__
TR04-090
| 3rd November 2004
__

Kazuyuki Amano, Akira Maruoka#### Better Simulation of Exponential Threshold Weights by Polynomial Weights

__
TR19-168
| 20th November 2019
__

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam#### Beyond Natural Proofs: Hardness Magnification and Locality

__
TR14-125
| 9th October 2014
__

Anindya De#### Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums

__
TR02-005
| 3rd January 2002
__

A. Pavan, Alan L. Selman#### Bi-Immunity Separates Strong NP-Completeness Notions

__
TR13-138
| 5th October 2013
__

Itai Benjamini, Gil Cohen, Igor Shinkar#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

__
TR15-096
| 5th June 2015
__

Abhishek Bhowmick, Shachar Lovett#### Bias vs structure of polynomials in large fields, and applications in effective algebraic geometry and coding theory

__
TR19-029
| 20th February 2019
__

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman#### Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

__
TR16-112
| 18th July 2016
__

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz#### Bicovering: Covering edges with two small subsets of vertices

__
TR22-129
| 15th September 2022
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang#### Binary Codes with Resilience Beyond 1/4 via Interaction

__
TR21-051
| 8th April 2021
__

Klim Efremenko, Gillat Kol, Raghuvansh Saxena#### Binary Interactive Error Resilience Beyond $1/8$ (or why $(1/2)^3 > 1/8$)

__
TR15-177
| 9th November 2015
__

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf#### Bipartite Perfect Matching is in quasi-NC

Revisions: 2

__
TR09-005
| 7th December 2008
__

Emanuele Viola#### Bit-Probe Lower Bounds for Succinct Data Structures

__
TR07-042
| 7th May 2007
__

Zohar Karnin, Amir Shpilka#### Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in

Revisions: 2
,
Comments: 1

__
TR01-050
| 24th June 2001
__

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen#### Black-Box Concurrent Zero-Knowledge Requires $\tilde\Omega(\log n)$ Rounds

__
TR15-056
| 3rd April 2015
__

Sanjam Garg, Steve Lu, Rafail Ostrovsky#### Black-Box Garbled RAM

__
TR11-046
| 2nd April 2011
__

Shubhangi Saraf, Ilya Volkovich#### Black-Box Identity Testing of Depth-4 Multilinear Circuits

__
TR23-147
| 27th September 2023
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

Revisions: 5
,
Comments: 1

__
TR22-067
| 4th May 2022
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

__
TR24-010
| 19th January 2024
__

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere#### Black-Box PPP is not Turing-Closed

__
TR10-102
| 12th May 2010
__

Per Kristian Lehre, Carsten Witt#### Black-Box Search by Unbiased Variation

Revisions: 1

__
TR07-044
| 23rd April 2007
__

Philipp Hertel#### Black-White Pebbling is PSPACE-Complete

Revisions: 1

__
TR10-167
| 5th November 2010
__

Nitin Saxena, C. Seshadhri#### Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

__
TR09-032
| 16th April 2009
__

Neeraj Kayal, Shubhangi Saraf#### Blackbox Polynomial Identity Testing for Depth 3 Circuits

__
TR20-173
| 18th November 2020
__

Kunal Mittal, Ran Raz#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

__
TR12-160
| 20th November 2012
__

Frederic Green, Daniel Kreymer, Emanuele Viola#### Block-symmetric polynomials correlate with parity better than symmetric

__
TR95-049
| 19th October 1995
__

Anna Gal, Avi Wigderson#### Boolean complexity classes vs. their arithmetic analogs

__
TR18-075
| 23rd April 2018
__

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 4

__
TR13-191
| 26th December 2013
__

Petr Savicky#### Boolean functions with a vertex-transitive group of automorphisms

Revisions: 2
,
Comments: 1

__
TR22-041
| 23rd March 2022
__

Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein#### Boolean functions with small approximate spectral norm

__
TR13-141
| 8th October 2013
__

Leonid Gurvits#### Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications

Revisions: 1

__
TR07-131
| 16th November 2007
__

Satyen Kale#### Boosting and hard-core set constructions: a simplified approach

__
TR18-199
| 24th November 2018
__

Lijie Chen, Roei Tell#### Bootstrapping Results for Threshold Circuits “Just Beyond” Known Lower Bounds

__
TR18-035
| 21st February 2018
__

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena#### Bootstrapping variables in algebraic circuits

__
TR23-075
| 17th May 2023
__

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj#### Border Complexity of Symbolic Determinant under Rank One Restriction

__
TR22-157
| 16th November 2022
__

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov#### Border complexity via elementary symmetric polynomials

Revisions: 1

__
TR13-135
| 27th September 2013
__

Scott Aaronson#### BosonSampling Is Far From Uniform

Revisions: 2

__
TR20-055
| 22nd April 2020
__

Ashutosh Kumar, Raghu Meka, David Zuckerman#### Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

__
TR04-121
| 7th December 2004
__

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan#### Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

__
TR99-012
| 19th April 1999
__

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh#### Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

__
TR16-099
| 13th June 2016
__

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama#### Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression

__
TR09-117
| 18th November 2009
__

Ilias Diakonikolas, Daniel Kane, Jelani Nelson#### Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR16-169
| 3rd November 2016
__

Elad Haramaty, Chin Ho Lee, Emanuele Viola#### Bounded independence plus noise fools products

__
TR16-102
| 4th July 2016
__

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola#### Bounded independence vs. moduli

Revisions: 1

__
TR15-182
| 13th November 2015
__

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson#### Bounded Indistinguishability and the Complexity of Recovering Secrets

Revisions: 1

__
TR21-093
| 1st July 2021
__

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan#### Bounded Indistinguishability for Simple Sources

Revisions: 1

__
TR16-093
| 4th June 2016
__

Cyrus Rashtchian#### Bounded Matrix Rigidity and John's Theorem

__
TR07-051
| 18th April 2007
__

Pilar Albert, Elvira Mayordomo, Philippe Moser#### Bounded Pushdown dimension vs Lempel Ziv information density

__
TR97-035
| 31st July 1997
__

Richard Chang#### Bounded Queries, Approximations and the Boolean Hierarchy

Revisions: 1

__
TR23-070
| 9th May 2023
__

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren#### Bounded Relativization

__
TR10-115
| 17th July 2010
__

Shachar Lovett, Emanuele Viola#### Bounded-depth circuits cannot sample good codes

__
TR19-069
| 6th May 2019
__

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova#### Bounded-depth Frege complexity of Tseitin formulas for all graphs

Revisions: 1

__
TR02-023
| 16th April 2002
__

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal#### Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revisions: 1

__
TR01-037
| 21st February 2001
__

Rustam Mubarakzjanov#### Bounded-Width Probabilistic OBDDs and Read-Once Branching Programs are Incomparable

__
TR12-096
| 17th July 2012
__

Albert Atserias, Sergi Oliva#### Bounded-width QBF is PSPACE-complete

Revisions: 3

__
TR16-142
| 11th September 2016
__

Jason Li, Ryan O'Donnell#### Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

__
TR10-049
| 24th March 2010
__

Alexey Pospelov#### Bounds for Bilinear Complexity of Noncommutative Group Algebras

Revisions: 1
,
Comments: 1

__
TR17-071
| 14th April 2017
__

Young Kun Ko, Arial Schvartzman#### Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

Revisions: 1

__
TR94-012
| 12th December 1994
__

#### Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

__
TR13-136
| 27th September 2013
__

Paul Goldberg, Aaron Roth#### Bounds for the Query Complexity of Approximate Equilibria

__
TR03-019
| 3rd April 2003
__

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan#### Bounds on 2-Query Codeword Testing.

Revisions: 1

__
TR09-138
| 14th December 2009
__

Gillat Kol, Ran Raz#### Bounds on 2-Query Locally Testable Codes with Affine Tests

__
TR03-033
| 6th May 2003
__

Meir Feder, Dana Ron, Ami Tavory#### Bounds on Linear Codes for Network Multicast

Comments: 1

__
TR09-142
| 17th December 2009
__

Aaron Potechin#### Bounds on Monotone Switching Networks for Directed Connectivity

Revisions: 1

__
TR98-044
| 31st July 1998
__

Jiri Sgall#### Bounds on Pairs of Families with Restricted Intersections

__
TR16-013
| 12th January 2016
__

Ludwig Staiger#### Bounds on the Kolmogorov complexity function for infinite words

Revisions: 2

__
TR03-029
| 1st April 2003
__

Philippe Moser#### BPP has effective dimension at most 1/2 unless BPP=EXP

__
TR11-103
| 31st July 2011
__

Yang Li#### BQP and PPAD

__
TR09-104
| 26th October 2009
__

Scott Aaronson#### BQP and the Polynomial Hierarchy

__
TR01-048
| 3rd June 2001
__

Jui-Lin Lee#### Branching program, commutator, and icosahedron, part I

__
TR21-028
| 27th February 2021
__

Anastasia Sofronova, Dmitry Sokolov#### Branching Programs with Bounded Repetitions and $\mathrm{Flow}$ Formulas

__
TR05-098
| 4th September 2005
__

Oded Goldreich#### Bravely, Moderately: A Common Theme in Four Recent Results

__
TR05-124
| 2nd November 2005
__

Kooshiar Azimian#### Breaking Diffie-Hellman is no Easier than Root Finding

__
TR10-068
| 15th April 2010
__

Shir Ben-Israel, Eli Ben-Sasson, David Karger#### Breaking local symmetries can dramatically reduce the length of propositional refutations

__
TR24-067
| 10th April 2024
__

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang#### Breaking Square-Root Loss Barriers via Min-Entropy

__
TR07-098
| 2nd October 2007
__

Tali Kaufman, Simon Litsyn, Ning Xie#### Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2)

__
TR14-009
| 21st January 2014
__

Alexander A. Sherstov#### Breaking the Minsky-Papert Barrier for Constant-Depth Circuits

__
TR13-160
| 20th November 2013
__

Zeev Dvir, Shubhangi Saraf, Avi Wigderson#### Breaking the quadratic barrier for 3-LCCs over the Reals

__
TR19-054
| 9th April 2019
__

Joshua Brakensiek, Venkatesan Guruswami#### Bridging between 0/1 and Linear Programming via Random Walks

__
TR16-090
| 27th May 2016
__

Bernhard Haeupler, Ameya Velingker#### Bridging the Capacity Gap Between Interactive and One-Way Communication

__
TR19-072
| 17th May 2019
__

Lijie Chen, Ofer Grossman#### Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators

__
TR15-202
| 11th December 2015
__

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah#### Building above read-once polynomials: identity testing and hardness of representation

__
TR10-127
| 9th August 2010
__

Brett Hemenway, Rafail Ostrovsky#### Building Injective Trapdoor Functions From Oblivious Transfer

Revisions: 1

__
TR18-172
| 11th October 2018
__

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan#### Building Strategies into QBF Proofs

__
TR06-068
| 6th April 2006
__

Patrick Briest, Piotr Krysta#### Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing

__
TR10-177
| 16th November 2010
__

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu#### Bypassing UGC from some optimal geometric inapproximability results

Revisions: 1

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep

The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a satisfiable 2CSP instance from one which is only $(1-\varepsilon)$-satisfiable (where the parameter is the number of variables) for some constant $0<\varepsilon<1$.

We ... more >>>

Titus Dose

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the ... more >>>

Noga Alon, Shai Gutner

Color Coding is an algorithmic technique for deciding efficiently

if a given input graph contains a path of a given length (or

another small subgraph of constant tree-width). Applications of the

method in computational biology motivate the study of similar

algorithms for counting the number of copies of a ...
more >>>

Per Austrin

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate Max 2-Sat within $\alpha_{LLZ}^{-}+\epsilon$, where $0.9401 < \alpha_{LLZ}^{-} < 0.9402$ is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick.

This result is surprising considering the fact that balanced instances of Max 2-Sat, i.e. ... more >>>

L. Elisa Celis, Omer Reingold, Gil Segev, Udi Wieder

A fundamental fact in the analysis of randomized algorithm is that when $n$ balls are hashed into $n$ bins independently and uniformly at random, with high probability each bin contains at most $O(\log n / \log \log n)$ balls. In various applications, however, the assumption that a truly random hash ... more >>>

Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than ... more >>>

Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam

We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular matrix multiplication cannot give optimal algorithms. In fact, we prove a precise numerical barrier for this method. Our barrier improves the previously ... more >>>

Bo Tang, Jiapeng Zhang

Reducibility between different cryptographic primitives is a fundamental problem in modern cryptography. As one of the primitives, traitor tracing systems help content distributors recover the identities of users that collaborated in the pirate construction by tracing pirate decryption boxes. We present the first negative result on designing efficient traitor tracing ... more >>>

Jin-Yi Cai, Pinyan Lu

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This ... more >>>

Alexandros G. Dimakis, Anna Gal, Ankit Singh Rawat, Zhao Song

Consider a large database of $n$ data items that need to be stored using $m$ servers.

We study how to encode information so that a large number $k$ of read requests can be performed \textit{in parallel} while the rate remains constant (and ideally approaches one).

This problem is equivalent ...
more >>>

Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan

Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs ... more >>>

Guy Rothblum, Ron Rothblum

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

Inbar Kaslasi, Prashant Nalini Vasudevan, Guy Rothblum, Ron Rothblum, Adam Sealfon

A statistical zero-knowledge proof (SZK) for a problem $\Pi$ enables a computationally unbounded prover to convince a polynomial-time verifier that $x \in \Pi$ without revealing any additional information about $x$ to the verifier, in a strong information-theoretic sense.

Suppose, however, that the prover wishes to convince the verifier that $k$ ... more >>>

Matthias Krause

Many of the keystream generators which are used in practice are LFSR-based in the sense

that they produce the keystream according to a rule $y=C(L(x))$,

where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel

linear feedback shift registers (LFSRs),

and $C$ denotes ...
more >>>

Shuichi Hirahara, Rahul Ilango, Ryan Williams

A compression problem is defined with respect to an efficient encoding function $f$; given a string $x$, our task is to find the shortest $y$ such that $f(y) = x$. The obvious brute-force algorithm for solving this compression task on $n$-bit strings runs in time $O(2^{\ell} \cdot t(n))$, where $\ell$ ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

Let $C$ be a depth-3 $\Sigma\Pi\Sigma$ arithmetic circuit of size $s$,

computing a polynomial $f \in \mathbb{F}[x_1,\ldots, x_n]$ (where $\mathbb{F}$ = $\mathbb{Q}$ or

$\mathbb{C}$) with fan-in of product gates bounded by $d$. We give a

deterministic time $2^d \text{poly}(n,s)$ polynomial identity testing

algorithm to check whether $f \equiv 0$ or ...
more >>>

Venkatesan Guruswami, Andrii Riazanov

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is ... more >>>

Chaoping Xing, chen yuan

For an interger $q\ge 2$, a perfect $q$-hash code $C$ is a block code over $\ZZ_q:=\ZZ/ q\ZZ$ of length $n$ in which every subset $\{\bc_1,\bc_2,\dots,\bc_q\}$ of $q$ elements is separated, i.e., there exists $i\in[n]$ such that $\{\proj_i(\bc_1),\proj_i(\bc_2),\dots,\proj_i(\bc_q)\}=\ZZ_q$, where $\proj_i(\bc_j)$ denotes the $i$th position of $\bc_j$. Finding the maximum size $M(n,q)$ ... more >>>

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. ... more >>>

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

We prove that, assuming the Unique Games Conjecture (UGC), every problem in the class of ordering constraint satisfaction problems (OCSP) where each constraint has constant arity is approximation

resistant. In other words, we show that if $\rho$ is the expected fraction of constraints satisfied by a random ordering, then obtaining ...
more >>>

Venkatesan Guruswami, Atri Rudra

We give a polynomial time construction of binary codes with the best

currently known trade-off between rate and error-correction

radius. Specifically, we obtain linear codes over fixed alphabets

that can be list decoded in polynomial time up to the so called

Blokh-Zyablov bound. Our work ...
more >>>

Eric Allender, Andreas Krebs, Pierre McKenzie

Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along ... more >>>

Venkatesan Guruswami

We present an explicit construction of codes that can be list decoded

from a fraction $(1-\eps)$ of errors in sub-exponential time and which

have rate $\eps/\log^{O(1)}(1/\eps)$. This comes close to the optimal

rate of $\Omega(\eps)$, and is the first sub-exponential complexity

construction to beat the rate of $O(\eps^2)$ achieved by ...
more >>>

Falk Unger

We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with ... more >>>

William Hoza

Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-$n$ length-$n$ read-once branching programs (ROBPs) with error $\varepsilon$ and seed length $O(\log^2 n + \log n \cdot \log(1/\varepsilon))$ (Combinatorica 1992). Nisan's generator remains the best explicit PRG known for this important model of computation. However, a recent ... more >>>

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan

We present an iterative approach to constructing pseudorandom generators, based on the repeated application of mild pseudorandom restrictions. We use this template to construct pseudorandom generators for combinatorial rectangles and read-once CNFs and a hitting set generator for width-3 branching programs, all of which achieve near optimal seed-length even in ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. The collection of authorized sets is called the access structure. For over 30 years, it was ... more >>>

Kazuyuki Amano, Akira Maruoka

We give an explicit construction of depth two threshold circuit with polynomial weights and $\tilde{O}(n^5)$ gates that computes an arbitrary threshold function. We also give the construction of such circuits with $O(n^3/\log n)$ gates computing the COMPARISON and CARRY functions, and that with $O(n^4/\log n)$ gates computing the ADDITION function. ... more >>>

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Hardness magnification reduces major complexity separations (such as $EXP \not\subseteq NC^1$) to proving lower bounds for some natural problem $Q$ against weak circuit models. Several recent works [OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of this form. In the most intriguing cases, the required lower bound is ... more >>>

Anindya De

In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}

and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that

more >>>

A. Pavan, Alan L. Selman

We prove that if for some epsilon > 0 NP contains a set that is

DTIME(2^{n^{epsilon}})-bi-immune, then NP contains a set that 2-Turing

complete for NP but not 1-truth-table complete for NP. Lutz and Mayordomo

(LM96) and Ambos-Spies and Bentzien (AB00) previously obtained the

same consequence using strong ...
more >>>

Itai Benjamini, Gil Cohen, Igor Shinkar

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

Abhishek Bhowmick, Shachar Lovett

Let $f$ be a polynomial of degree $d$ in $n$ variables over a finite field $\mathbb{F}$. The polynomial is said to be unbiased if the distribution of $f(x)$ for a uniform input $x \in \mathbb{F}^n$ is close to the uniform distribution over $\mathbb{F}$, and is called biased otherwise. The polynomial ... more >>>

Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman

The seminal result of Kahn, Kalai and Linial shows that a coalition of $O(\frac{n}{\log n})$ players can bias the outcome of *any* Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely ... more >>>

Mohammad T. Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and that every edge $e$ belongs to either the graph induced by $A$ or to the graph induced by $B$. The ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang

In the reliable transmission problem, a sender, Alice, wishes to transmit a bit-string x to a remote receiver, Bob, over a binary channel with adversarial noise. The solution to this problem is to encode x using an error correcting code. As it is long known that the distance of binary ... more >>>

Klim Efremenko, Gillat Kol, Raghuvansh Saxena

Interactive error correcting codes are codes that encode a two party communication protocol to an error-resilient protocol that succeeds even if a constant fraction of the communicated symbols are adversarially corrupted, at the cost of increasing the communication by a constant factor. What is the largest fraction of corruptions that ... more >>>

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>

Emanuele Viola

We prove lower bounds on the redundancy necessary to

represent a set $S$ of objects using a number of bits

close to the information-theoretic minimum $\log_2 |S|$,

while answering various queries by probing few bits. Our

main results are:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>

Zohar Karnin, Amir Shpilka

In this paper we consider the problem of determining whether an

unknown arithmetic circuit, for which we have oracle access,

computes the identically zero polynomial. Our focus is on depth-3

circuits with a bounded top fan-in. We obtain the following

results.

1. A quasi-polynomial time deterministic black-box identity testing algorithm ... more >>>

Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen

We show that any concurrent zero-knowledge protocol for a non-trivial

language (i.e., for a language outside $\BPP$), whose security is proven

via black-box simulation, must use at least $\tilde\Omega(\log n)$

rounds of interaction. This result achieves a substantial improvement

over previous lower bounds, and is the first bound to rule ...
more >>>

Sanjam Garg, Steve Lu, Rafail Ostrovsky

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations ... more >>>

Shubhangi Saraf, Ilya Volkovich

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic

identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Hrube\v{s} and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem ... more >>>

Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere

The complexity class PPP contains all total search problems many-one reducible to the PIGEON problem, where we are given a succinct encoding of a function mapping n+1 pigeons to n holes, and must output two pigeons that collide in a hole. PPP is one of the “original five” syntactically-defined subclasses ... more >>>

Per Kristian Lehre, Carsten Witt

The complexity theory for black-box algorithms, introduced by

Droste et al. (2006), describes common limits on the efficiency of

a broad class of randomised search heuristics. There is an

obvious trade-off between the generality of the black-box model

and the strength of the bounds that can be proven in such ...
more >>>

Philipp Hertel

The complexity of the Black-White Pebbling Game has remained an open problem for 30 years. It was devised to capture the power of non-deterministic space bounded computation. Since then it has been continuously studied and applied to problems in diverse areas of computer science including VLSI design and more recently ... more >>>

Nitin Saxena, C. Seshadhri

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.

It is a major open problem to design a deterministic polynomial time blackbox algorithm

that tests if C is identically zero.

Klivans & Spielman (STOC 2001) observed ...
more >>>

Neeraj Kayal, Shubhangi Saraf

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

Kunal Mittal, Ran Raz

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

Frederic Green, Daniel Kreymer, Emanuele Viola

We show that degree-$d$ block-symmetric polynomials in

$n$ variables modulo any odd $p$ correlate with parity

exponentially better than degree-$d$ symmetric

polynomials, if $n \ge c d^2 \log d$ and $d \in [0.995

\cdot p^t - 1,p^t)$ for some $t \ge 1$. For these

infinitely many degrees, our result ...
more >>>

Anna Gal, Avi Wigderson

This paper provides logspace and small circuit depth analogs

of the result of Valiant-Vazirani, which is a randomized (or

nonuniform) reduction from NP to its arithmetic analog ParityP.

We show a similar randomized reduction between the

Boolean classes NL and semi-unbounded fan-in Boolean circuits and

their arithmetic counterparts. These ...
more >>>

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

Petr Savicky

A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.

Tsun-Ming Cheung, Hamed Hatami, Rosie Zhao, Itai Zilberstein

The sum of the absolute values of the Fourier coefficients of a function $f:\mathbb{F}_2^n \to \mathbb{R}$ is called the spectral norm of $f$. Green and Sanders' quantitative version of Cohen's idempotent theorem states that if the spectral norm of $f:\mathbb{F}_2^n \to \{0,1\}$ is at most $M$, then the support of ... more >>>

Leonid Gurvits

We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications. Our main application is the first poly-time deterministic algorithm which approximates the partition functions associated with

boolean matrices with prescribed row and (uniformly bounded) column sums within simply ...
more >>>

Satyen Kale

We revisit the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio. We present a boosting algorithm with a certain smoothness property that is necessary for hard-core set constructions: the distributions it generates do not put too much weight on any single example. We then use ... more >>>

Lijie Chen, Roei Tell

The best-known lower bounds for the circuit class $\mathcal{TC}^0$ are only slightly super-linear. Similarly, the best-known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative ... more >>>

Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>

Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj

VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem ... more >>>

Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

In (ToCT’20) Kumar surprisingly proved that every polynomial can be approximated as a sum of a constant and a product of linear polynomials. In this work, we prove the converse of Kumar's result which ramifies in a surprising new formulation of Waring rank and border Waring rank. From this conclusion, ... more >>>

Scott Aaronson

BosonSampling, which we proposed three years ago, is a scheme for using linear-optical networks to solve sampling problems that appear to be intractable for a classical computer. In a recent manuscript, Gogolin et al. claimed that even an ideal BosonSampling device's output would be "operationally indistinguishable" from a uniform random ... more >>>

Ashutosh Kumar, Raghu Meka, David Zuckerman

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... more >>>

Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan

In this paper we study the complexity of Bounded Color

Multiplicity Graph Isomorphism (BCGI): the input is a pair of

vertex-colored graphs such that the number of vertices of a given

color in an input graph is bounded by $b$. We show that BCGI is in the

#L hierarchy ...
more >>>

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

Constant-depth arithmetic circuits have been defined and studied

in [AAD97,ABL98]; these circuits yield the function classes #AC^0

and GapAC^0. These function classes in turn provide new

characterizations of the computational power of threshold circuits,

and provide a link between the circuit classes AC^0 ...
more >>>

Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama

A Boolean function $f: \{0,1\}^n \to \{0,1\}$ is weighted symmetric if there exist a function $g: \mathbb{Z} \to \{0,1\}$ and integers $w_0, w_1, \ldots, w_n$ such that $f(x_1,\ldots,x_n) = g(w_0+\sum_{i=1}^n w_i x_i)$ holds.

In this paper, we present algorithms for the circuit satisfiability problem of bounded depth circuits with AND, ... more >>>

Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

Elad Haramaty, Chin Ho Lee, Emanuele Viola

Let $D$ be a $b$-wise independent distribution over

$\{0,1\}^m$. Let $E$ be the ``noise'' distribution over

$\{0,1\}^m$ where the bits are independent and each bit is 1

with probability $\eta/2$. We study which tests $f \colon

\{0,1\}^m \to [-1,1]$ are $\e$-fooled by $D+E$, i.e.,

$|\E[f(D+E)] - \E[f(U)]| \le \e$ where ...
more >>>

Ravi Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola

Let $k=k(n)$ be the largest integer such that there

exists a $k$-wise uniform distribution over $\zo^n$ that

is supported on the set $S_m := \{x \in \zo^n : \sum_i

x_i \equiv 0 \bmod m\}$, where $m$ is any integer. We

show that $\Omega(n/m^2 \log m) \le k \le 2n/m + ...
more >>>

Andrej Bogdanov, Yuval Ishai, Emanuele Viola, Christopher Williamson

We say that a function $f\colon \Sigma^n \to \{0, 1\}$ is $\epsilon$-fooled by $k$-wise indistinguishability if $f$ cannot distinguish with advantage $\epsilon$ between any two distributions $\mu$ and $\nu$ over $\Sigma^n$ whose projections to any $k$ symbols are identical. We study the class of functions $f$ that are fooled by ... more >>>

Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan

A pair of sources $\mathbf{X},\mathbf{Y}$ over $\{0,1\}^n$ are $k$-indistinguishable if their projections to any $k$ coordinates are identically distributed. Can some $\mathit{AC^0}$ function distinguish between two such sources when $k$ is big, say $k=n^{0.1}$? Braverman's theorem (Commun. ACM 2011) implies a negative answer when $\mathbf{X}$ is uniform, whereas Bogdanov et ... more >>>

Cyrus Rashtchian

Using John's Theorem, we prove a lower bound on the bounded rigidity of a sign matrix, defined as the Hamming distance between this matrix and the set of low-rank, real-valued matrices with entries bounded in absolute value. For Hadamard matrices, our asymptotic leading constant is tighter than known results by ... more >>>

Pilar Albert, Elvira Mayordomo, Philippe Moser

In this paper we introduce a variant of pushdown dimension called bounded pushdown (BPD) dimension, that measures the density of information contained in a sequence, relative to a BPD automata, i.e. a finite state machine equipped with an extra infinite memory stack, with the additional requirement that every input symbol ... more >>>

Richard Chang

This paper introduces a new model of computation for describing the

complexity of NP-approximation problems. The results show that the

complexity of NP-approximation problems can be characterized by classes of

multi-valued functions computed by nondeterministic polynomial time Turing

machines with a bounded number of oracle queries to an NP-complete

language. ...
more >>>

Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

Shachar Lovett, Emanuele Viola

We study a variant of the classical circuit-lower-bound problems: proving lower bounds for sampling distributions given random bits. We prove a lower bound of $1-1/n^{\Omega(1)}$ on the statistical distance between (i) the output distribution of any small constant-depth (a.k.a.~$\mathrm{AC}^0$) circuit $f : \{0,1\}^{\mathrm{poly}(n)} \to \{0,1\}^n$, and (ii) the uniform distribution ... more >>>

Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova

We prove that there is a constant $K$ such that \emph{Tseitin} formulas for an undirected graph $G$ requires proofs of

size $2^{\mathrm{tw}(G)^{\Omega(1/d)}}$ in depth-$d$ Frege systems for $d<\frac{K \log n}{\log \log n}$, where $\tw(G)$ is the treewidth of $G$. This extends H{\aa}stad recent lower bound for the grid graph ...
more >>>

Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal

We prove a quasi-polynomial lower bound on the size of bounded-depth

Frege proofs of the pigeonhole principle $PHP^{m}_n$ where

$m= (1+1/{\polylog n})n$.

This lower bound qualitatively matches the known quasi-polynomial-size

bounded-depth Frege proofs for these principles.

Our technique, which uses a switching lemma argument like other lower bounds

for ...
more >>>

Rustam Mubarakzjanov

Restricted branching programs are considered by the investigation

of relationships between complexity classes of Boolean functions.

Read-once ordered branching programs (or OBDDs) form the most restricted class

of this computation model.

Since the problem of proving exponential lower bounds on the complexity

for general probabilistic OBDDs is open so ...
more >>>

Albert Atserias, Sergi Oliva

Tree-width is a well-studied parameter of structures that measures their similarity to a tree. Many important NP-complete problems, such as Boolean satisfiability (SAT), are tractable on bounded tree-width instances. In this paper we focus on the canonical PSPACE-complete problem QBF, the fully-quantified version of SAT. It was shown by Pan ... more >>>

Jason Li, Ryan O'Donnell

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, Håstad, and ... more >>>

Alexey Pospelov

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the ... more >>>

Young Kun Ko, Arial Schvartzman

In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper ... more >>>

It is shown that high order feedforward neural nets of constant depth with piecewise

polynomial activation functions and arbitrary real weights can be simulated for boolean

inputs and outputs by neural nets of a somewhat larger size and depth with heaviside

gates and weights ...
more >>>

Paul Goldberg, Aaron Roth

We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player's behavior must always be approximately optimal, in the ... more >>>

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

We present upper bounds on the size of codes that are locally

testable by querying only two input symbols. For linear codes, we

show that any $2$-locally testable code with minimal distance

$\delta n$ over a finite field $F$ cannot have more than

$|F|^{3/\delta}$ codewords. This result holds even ...
more >>>

Gillat Kol, Ran Raz

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

Meir Feder, Dana Ron, Ami Tavory

Traditionally, communication networks are composed of

routing nodes, which relay and duplicate data. Work in

recent years has shown that for the case of multicast, an

improvement in both rate and code-construction complexity can be

gained by replacing these routing nodes by linear coding

nodes. These nodes transmit linear combinations ...
more >>>

Aaron Potechin

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$

more >>>Jiri Sgall

We study pairs of families ${\cal A},{\cal B}\subseteq

2^{\{1,\ldots,r\}}$ such that $|A\cap B|\in L$ for any

$A\in{\cal A}$, $B\in{\cal B}$. We are interested in the maximal

product $|{\cal A}|\cdot|{\cal B}|$, given $r$ and $L$. We give

asymptotically optimal bounds for $L$ containing only elements

of $s<q$ residue classes modulo ...
more >>>

Ludwig Staiger

The Kolmogorov complexity function of an infinite word $\xi$ maps a natural

number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We

investigate the maximally achievable complexity function if $\xi$ is taken

from a constructively describable set of infinite words. Here we are

interested ...
more >>>

Philippe Moser

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.

Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP

on infinitely many input lengths.

We also prove that BPP has measure zero in the smaller complexity

class ...
more >>>

Yang Li

We initiate the study of the relationship between two complexity classes, BQP

(Bounded-Error Quantum Polynomial-Time) and PPAD (Polynomial Parity Argument,

Directed). We first give a conjecture that PPAD is contained in BQP, and show

a necessary and sufficient condition for the conjecture to hold. Then we prove

that the conjecture ...
more >>>

Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

Jui-Lin Lee

In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of

uniform $NC^1$ based on different recursion principles: one is OR-AND complete

binary tree (in depth $\log n$) and the other is the recursion on notation with value

bounded in $[0,k]$ and $|x|(=n)$ many ...
more >>>

Anastasia Sofronova, Dmitry Sokolov

Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. '95 who showed the equivalence between regular Resolution and read-once branching programs ... more >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>

Kooshiar Azimian

In this paper we compare hardness of two well known problems: the Diffie-Hellman problem and the root finding problem. We prove that in any cyclic group computing Diffie-Hellman is not weaker than root finding if certain circumstances are met. As will be discussed in the paper this theorem can affect ... more >>>

Shir Ben-Israel, Eli Ben-Sasson, David Karger

This paper shows that the use of ``local symmetry breaking'' can dramatically reduce the length of propositional refutations. For each of the three propositional proof systems known as (i) treelike resolution, (ii) resolution, and (iii) k-DNF resolution, we describe families of unsatisfiable formulas in conjunctive normal form (CNF) that are ... more >>>

Mi-Ying Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang

Information complexity is one of the most powerful tools to prove information-theoretical lower bounds, with broad applications in communication complexity and streaming algorithms. A core notion in information complexity analysis is the Shannon entropy. Though it has some convenient properties, such as chain rules, Shannon entropy still has inherent limitations. ... more >>>

Tali Kaufman, Simon Litsyn, Ning Xie

For Boolean functions that are $\epsilon$-far from the set of linear functions, we study the lower bound on the rejection probability (denoted $\textsc{rej}(\epsilon)$) of the linearity test suggested by Blum, Luby and Rubinfeld. The interest in this problem is partly due to its relation to PCP constructions and hardness of ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969

monograph, Minsky and Papert constructed a polynomial-size constant-depth

$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies ...
more >>>

Zeev Dvir, Shubhangi Saraf, Avi Wigderson

We prove that 3-query linear locally correctable codes over the Reals of dimension $d$ require block length $n>d^{2+\lambda}$ for some fixed, positive $\lambda >0$. Geometrically, this means that if $n$ vectors in $R^d$ are such that each vector is spanned by a linear number of disjoint triples of others, then ... more >>>

Joshua Brakensiek, Venkatesan Guruswami

Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial ... more >>>

Bernhard Haeupler, Ameya Velingker

We study the communication rate of coding schemes for interactive communication that transform any two-party interactive protocol into a protocol that is robust to noise.

Recently, Haeupler (FOCS '14) showed that if an $\epsilon > 0$ fraction of transmissions are corrupted, adversarially or randomly, then it is possible to ... more >>>

Lijie Chen, Ofer Grossman

Consider the multiparty communication complexity model where there are n processors, each receiving as input a row of an n by n matrix M with entries in {0, 1}, and in each round each party can broadcast a single bit to all other parties (this is known as the BCAST(1) ... more >>>

Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah

Polynomial Identity Testing (PIT) algorithms have focused on

polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted

formulas. Read-once polynomials (ROPs) are computed by read-once

formulas (ROFs) and are the simplest of read-restricted polynomials.

Building structures above these, we show the following:

\begin{enumerate}

\item A deterministic polynomial-time non-black-box ...
more >>>

Brett Hemenway, Rafail Ostrovsky

Injective one-way trapdoor functions are one of the most fundamental cryptographic primitives. In this work we give a novel construction of injective trapdoor functions based on oblivious transfer for long strings.

Our main result is to show that any 2-message statistically sender-private semi-honest oblivious transfer (OT) for ...
more >>>

Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan

Strategy extraction is of paramount importance for quantified Boolean formulas (QBF), both in solving and proof complexity. It extracts (counter)models for a QBF from a run of the solver resp. the proof of the QBF, thereby allowing to certify the solver's answer resp. establish soundness of the system. So far ... more >>>

Patrick Briest, Piotr Krysta

We investigate non-parametric unit-demand pricing problems, in which the goal is to find revenue maximizing prices for a set of products based on consumer profiles obtained, e.g., from an e-Commerce website. A consumer profile consists of a number of non-zero budgets and a ranking of all the products the consumer ... more >>>

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

The Unique Games conjecture (UGC) has emerged in recent years as the starting point for several optimal inapproximability results. While for none of these results a reverse reduction to Unique Games is known, the assumption of bijective projections in the Label Cover instance seems critical in these proofs. In this ... more >>>