All reports by Author Mitali Bafna:

__
TR24-020
| 2nd February 2024
__

Mitali Bafna, Noam Lifshitz, Dor Minzer#### Constant Degree Direct Product Testers with Small Soundness

Revisions: 1

__
TR23-120
| 18th August 2023
__

Mitali Bafna, Dor Minzer#### Characterizing Direct Product Testing via Coboundary Expansion

__
TR21-169
| 24th November 2021
__

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett#### Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments

__
TR16-132
| 23rd August 2016
__

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker#### On the Sensitivity Conjecture for Read-k Formulas

Mitali Bafna, Noam Lifshitz, Dor Minzer

Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich ... more >>>

Mitali Bafna, Dor Minzer

A $d$-dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$-faces (where $k\ll d$) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution $\mu$ over pairs of $k$-faces $(A,A')$, and given ... more >>>

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of ... more >>>

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision ... more >>>