544 citations · 1.3k across the 26 of their papers we have counts for
5 papers · 1 filter
A note on the partition bound for one-way classical communication complexity
Srinivasan Arunachalam, João F. Doriguello, Joao F. Doriguello +1
We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted , and show that it characterizes the one-way ran…
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
Srinivasan Arunachalam, Joao F. Doriguello
We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful -uniform convexity…
Positive spectrahedra: Invariance principles and Pseudorandom generators
Srinivasan Arunachalam, Penghui Yao
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary -facet polytopes in variables with seed length poly-loga…
Communication memento: Memoryless communication complexity
Srinivasan Arunachalam, Supartha Podder
We study the communication complexity of computing functions in the memoryless communication model. Here, Alice is given $x\in \{0…
Improved bounds on Fourier entropy and Min-entropy
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký +2
Given a Boolean function , the Fourier distribution assigns probability to . The Fourier Entropy-Influence (FEI) conjec…