All reports by Author Abhishek Bhrushundi:

__
TR18-081
| 20th April 2018
__

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar#### On Multilinear Forms: Bias, Correlation, and Tensor Rank

Revisions: 1

__
TR18-076
| 22nd April 2018
__

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao#### Torus polynomials: an algebraic approach to ACC lower bounds

Revisions: 2

__
TR17-013
| 23rd January 2017
__

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan#### On polynomial approximations over $\mathbb{Z}/2^k\mathbb{Z}$

__
TR13-142
| 11th October 2013
__

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni#### Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees

Revisions: 2

__
TR13-089
| 17th June 2013
__

Abhishek Bhrushundi#### On testing bent functions

Revisions: 1

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

In this paper, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over $GF(2)= \{0,1\}$. We show the following results for multilinear forms and tensors.

1. Correlation bounds : We show that a random $d$-linear ... more >>>

Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying the notion of torus polynomials. We show how currently known polynomial-based approximation results for AC0 and ACC0 can be reformulated in this framework, implying that ACC0 can be approximated by low-degree torus polynomials. Furthermore, ... more >>>

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

We study approximation of Boolean functions by low-degree polynomials over the ring $\mathbb{Z}/2^k\mathbb{Z}$. More precisely, given a Boolean function F$:\{0,1\}^n \rightarrow \{0,1\}$, define its $k$-lift to be F$_k:\{0,1\}^n \rightarrow \{0,2^{k-1}\}$ by $F_k(x) = 2^{k-F(x)}$ (mod $2^k$). We consider the fractional agreement (which we refer to as $\gamma_{d,k}(F)$) of $F_k$ with ... more >>>

Abhishek Bhrushundi, Sourav Chakraborty, Raghav Kulkarni

In this paper, we study linear and quadratic Boolean functions in the context of property testing. We do this by observing that the query complexity of testing properties of linear and quadratic functions can be characterized in terms of the complexity in another model of computation called parity decision trees. ... more >>>

Abhishek Bhrushundi

A bent function is a Boolean function all of whose Fourier coefficients are equal in absolute value. These functions have been extensively studied in cryptography and play an important role in cryptanalysis and design of cryptographic systems.

We study bent functions in the framework of property testing. In particular, we ...
more >>>