All reports by Author Noam Lifshitz:

__
TR24-020
| 2nd February 2024
__

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

Revisions: 1

__
TR23-148
| 3rd October 2023
__

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz#### One Clean Qubit Suffices for Quantum Communication Advantage

__
TR23-133
| 13th September 2023
__

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer#### Product mixing in compact Lie groups

Revisions: 2

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

Srinivasan Arunachalam, Uma Girish, Noam Lifshitz

We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. We demonstrate a partial function that has a quantum protocol of cost $O(\log N)$ in this model, however, every interactive randomized protocol has cost $\Omega(\sqrt{N})$, settling a ... more >>>

David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer

If $G$ is a group, we say a subset $S$ of $G$ is product-free if the equation $xy=z$ has no solutions with $x,y,z \in S$. For $D \in \mathbb{N}$, a group $G$ is said to be $D$-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of $G$ is ... more >>>