4 papers
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +1
We consider random walks on ``balanced multislices'' of any ``grid'' that respects the ``symmetries'' of the grid, and show that a broad class of such walks are good spectral expan…
A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan +1
The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field are non-zero over any "gr…
Streaming Algorithms via Local Algorithms for Maximum Directed Cut
Raghuvansh R. Saxena, Noah G. Singer, Madhu Sudan +1
We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of Buchbinder et al…
Low Degree Local Correction Over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2
In this work, we show that the class of multivariate degree- polynomials mapping to any Abelian group is locally correctable with $\widetilde{O}_{d}((\log n)^{…