Avishay Tal
Vishnu Iyer's Home Page
Sid Jain
Vinayak M. Kumar
Junta Distance Approximation with Sub-Exponential Queries ( link ) joint work with Vishnu Iyer and Avishay Tal Ever wondered how many (input, output) pairs from your function f you have to look at to estimate how close f is to only depending on a few of its inputs? So did we. This work gives an improved algorithm for answering this question for Boolean functions. If you are really interested in questions like this, you can check out my master's thesis , which starts with a survey of the previous work done o
Before I became interested in theory, I dabbled in projects on islanding in energy grids, battery life maximization, and regression for biological datasets.
Quantum Time-Space Tradeoffs for Matrix Problems ( link ) joint work with Paul Beame and Niels Kornerup . On the Rational Degree of Boolean Functions and Applications ( link ) joint work with Vishnu Iyer , Siddhartha Jain , Matt Kovacs-Deak , Vinayak M. Kumar , Luke Schaeffer , and Daochen Wang We spent some time thinking about old questions concerning how hard it is to represent a Boolean function as the ratio of two polynomials. Searching for Regularity in Bounded Functions ( link ) joint work with Siddha
Avishay Tal
Vishnu Iyer's Home Page
Sid Jain
Vinayak M. Kumar