All reports by Author Anindya De:

__
TR21-005
| 13th January 2021
__

Anindya De, Elchanan Mossel, Joe Neeman#### Robust testing of low-dimensional functions

__
TR18-100
| 18th May 2018
__

Eshan Chattopadhyay, Anindya De, Rocco Servedio#### Simple and efficient pseudorandom generators from Gaussian processes

Revisions: 1

__
TR16-026
| 20th February 2016
__

Anindya De, Michael Saks, Sijian Tang#### Noisy population recovery in polynomial time

__
TR14-125
| 9th October 2014
__

Anindya De#### Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums

__
TR13-173
| 28th November 2013
__

Anindya De, Rocco Servedio#### Efficient deterministic approximate counting for low degree polynomial threshold functions

__
TR13-172
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

__
TR13-171
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

__
TR12-181
| 20th December 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### The Inverse Shapley Value Problem

__
TR12-152
| 7th November 2012
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Inverse Problems in Approximate Uniform Generation

__
TR12-072
| 5th June 2012
__

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio#### Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

__
TR12-016
| 24th February 2012
__

Anindya De, Elchanan Mossel#### Explicit Optimal hardness via Gaussian stability results

Revisions: 3

__
TR11-037
| 18th March 2011
__

Anindya De, Thomas Watson#### Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

__
TR09-133
| 9th December 2009
__

Anindya De, Thomas Vidick#### Near-optimal extractors against quantum storage

__
TR09-113
| 9th November 2009
__

Anindya De, Luca Trevisan, Madhur Tulsiani#### Non-uniform attacks against one-way functions and PRGs

__
TR08-023
| 10th January 2008
__

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi#### Fast Integer Multiplication using Modular Arithmetic

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. ... more >>>

Eshan Chattopadhyay, Anindya De, Rocco Servedio

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space.

The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of ... more >>>

Anindya De, Michael Saks, Sijian Tang

In the noisy population recovery problem of Dvir et al., the goal is to learn

an unknown distribution $f$ on binary strings of length $n$ from noisy samples. For some parameter $\mu \in [0,1]$,

a noisy sample is generated by flipping each coordinate of a sample from $f$ independently with

more >>>

Anindya De

In this paper, we construct pseudorandom generators for the class of \emph{combinatorial sums}, a class of functions first studied by \cite{GMRZ13}

and defined as follows: A function $f: [m]^n \rightarrow \{0,1\}$ is said to be a combinatorial sum if there exists functions $f_1, \ldots, f_n: [m] \rightarrow \{0,1\}$ such that

more >>>

Anindya De, Rocco Servedio

We give a deterministic algorithm for

approximately counting satisfying assignments of a degree-$d$ polynomial threshold function

(PTF).

Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$

and a parameter $\epsilon > 0$, our algorithm approximates

$

\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]

$

to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates

\[

\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]

\]

to within an additive $\pm \eps$ in ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[

\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]

to within an additive $\pm \eps$. For any constant ...
more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

For $f$ a weighted voting scheme used by $n$ voters to choose between two candidates, the $n$ \emph{Shapley-Shubik Indices} (or {\em Shapley values}) of $f$ provide a measure of how much control each voter can exert over the overall outcome of the vote. Shapley-Shubik indices were introduced by Lloyd Shapley ... more >>>

Anindya De, Ilias Diakonikolas, Rocco Servedio

We initiate the study of \emph{inverse} problems in approximate uniform generation, focusing on uniform generation of satisfying assignments of various types of Boolean functions. In such an inverse problem, the algorithm is given uniform random satisfying assignments of an unknown function $f$ belonging to a class $\C$ of Boolean functions ... more >>>

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco Servedio

The \emph{Chow parameters} of a Boolean function $f: \{-1,1\}^n \to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 \cite{Chow:61, Tannenbaum:61} that the (exact values of the) Chow parameters of any linear threshold function $f$ uniquely specify $f$ within the space of all Boolean ... more >>>

Anindya De, Elchanan Mossel

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... more >>>

Anindya De, Thomas Watson

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

Anindya De, Thomas Vidick

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

Anindya De, Luca Trevisan, Madhur Tulsiani

We study the power of non-uniform attacks against one-way

functions and pseudorandom generators.

Fiat and Naor show that for every function

$f: [N]\to [N]$

there is an algorithm that inverts $f$ everywhere using

(ignoring lower order factors)

time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Anindya De, Piyush Kurur, Chandan Saha, Ramprasad Saptharishi

We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for

multiplying two $N$-bit integers that improves the $O(N\cdot \log

N\cdot \log\log N)$ algorithm by

Sch\"{o}nhage-Strassen. Both these algorithms use modular

arithmetic. Recently, F\"{u}rer gave an $O(N\cdot \log

N\cdot 2^{O(\log^*N)})$ algorithm which however uses arithmetic over

complex numbers as opposed to ...
more >>>