Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR23-120 | 18th August 2023
Mitali Bafna, Dor Minzer

Characterizing Direct Product Testing via Coboundary Expansion

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 >>>

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

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 >>>

TR16-132 | 23rd August 2016
Mitali Bafna, Satyanarayana V. Lokam, S├ębastien Tavenas, Ameya Velingker

On the Sensitivity Conjecture for Read-k Formulas

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 >>>

ISSN 1433-8092 | Imprint