All reports in year 2022:

__
TR22-009
| 17th January 2022
__

C. Ramya, Anamay Tengse#### On Finer Separations between Subclasses of Read-once Oblivious ABPs

__
TR22-008
| 14th January 2022
__

Gil Cohen, Dean Doron, Ori Sberlo#### Approximating Large Powers of Stochastic Matrices in Small Space

__
TR22-007
| 14th January 2022
__

Halley Goldberg, Valentine Kabanets#### A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information

__
TR22-006
| 12th January 2022
__

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

__
TR22-005
| 11th January 2022
__

Anup Rao#### Sunflowers: from soil to oil

__
TR22-004
| 3rd January 2022
__

Silas Richelson, Sourya Roy#### Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

__
TR22-003
| 4th January 2022
__

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere#### On Semi-Algebraic Proofs and Algorithms

__
TR22-002
| 11th December 2021
__

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

__
TR22-001
| 28th December 2021
__

Yogesh Dahiya, Meena Mahajan#### On (Simple) Decision Tree Rank

C. Ramya, Anamay Tengse

Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials ... more >>>

Gil Cohen, Dean Doron, Ori Sberlo

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>

Halley Goldberg, Valentine Kabanets

We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in ... more >>>

Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

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$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

Anup Rao

A \emph{sunflower} is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erd\H{o}s and Rado, made by Alweiss, Lovett, Wu and Zhang.

more >>>Silas Richelson, Sourya Roy

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

Noah Fleming, Stefan Grosser, Mika Göös, Robert Robere

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts ... 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 >>>

Yogesh Dahiya, Meena Mahajan

In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure ... more >>>