All reports by Author Manindra Agrawal:

__
TR17-035
| 23rd February 2017
__

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena#### Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

__
TR14-085
| 29th June 2014
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for ROABP and Sum of Set-Multilinear circuits

__
TR14-057
| 17th April 2014
__

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar#### Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness

Revisions: 3

__
TR13-174
| 6th December 2013
__

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena#### Hitting-sets for low-distance multilinear depth-$3$

__
TR12-113
| 7th September 2012
__

Manindra Agrawal, Chandan Saha, Nitin Saxena#### Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas

__
TR12-087
| 4th July 2012
__

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn#### The Deterministic and Randomized Query Complexity of a Simple Guessing Game

Revisions: 1

__
TR11-143
| 2nd November 2011
__

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

__
TR08-062
| 11th June 2008
__

Manindra Agrawal, V Vinay#### Arithmetic Circuits: A Chasm at Depth Four

__
TR06-129
| 6th October 2006
__

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf#### The polynomially bounded perfect matching problem is in NC^2

__
TR99-018
| 8th June 1999
__

Manindra Agrawal, Somenath Biswas#### Reducing Randomness via Chinese Remaindering

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR97-060
| 2nd December 1997
__

Manindra Agrawal, Thomas Thierauf#### The Satisfiability Problem for Probabilistic Ordered Branching Programs

__
TR97-016
| 29th April 1997
__

Manindra Agrawal, Eric Allender, Samir Datta#### On TC^0, AC^0, and Arithmetic Circuits

__
TR96-032
| 12th March 1996
__

Manindra Agrawal, Thomas Thierauf#### The Boolean Isomorphism Problem

__
TR96-002
| 10th January 1996
__

Manindra Agrawal, Eric Allender#### An Isomorphism Theorem for Circuit Complexity

__
TR96-001
| 10th January 1996
__

Manindra Agrawal, Richard Beigel, Thomas Thierauf#### Modulo Information from Nonadaptive Queries to NP

Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar

In this paper, we propose a quantification of distributions on a set

of strings, in terms of how close to pseudorandom the distribution

is. The quantification is an adaptation of the theory of dimension of

sets of infinite sequences first introduced by Lutz

\cite{Lutz:DISS}.

We show that this definition ...
more >>>

Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

The depth-$3$ model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known exponential lower bounds but no nontrivial blackbox identity tests. In this paper we take a step towards designing such hitting-sets. We define a notion of ... more >>>

Manindra Agrawal, Chandan Saha, Nitin Saxena

We call a depth-$4$ formula $C$ $\textit{ set-depth-4}$ if there exists a (unknown) partition $X_1\sqcup\cdots\sqcup X_d$ of the variable indices $[n]$ that the top product layer respects, i.e. $C(\mathbf{x})=\sum_{i=1}^k {\prod_{j=1}^{d} {f_{i,j}(\mathbf{x}_{X_j})}}$ $ ,$ where $f_{i,j}$ is a $\textit{sparse}$ polynomial in $\mathbb{F}[\mathbf{x}_{X_j}]$. Extending this definition to any depth - we call ... more >>>

Peyman Afshani, Manindra Agrawal, Doerr Benjamin, Winzen Carola, Kasper Green Larsen, Kurt Mehlhorn

We study the $\leadingones$ game, a Mastermind-type guessing game first

regarded as a test case in the complexity theory of randomized search

heuristics. The first player, Carole, secretly chooses a string $z \in \{0,1\}^n$ and a

permutation $\pi$ of $[n]$.

The goal of the second player, Paul, is to ...
more >>>

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tools and techniques. In particular, we show that polynomial time hitting-set generators for identity testing of the two seemingly different and well studied ... more >>>

Manindra Agrawal, V Vinay

We show that proving exponential lower bounds on depth four arithmetic

circuits imply exponential lower bounds for unrestricted depth arithmetic

circuits. In other words, for exponential sized circuits additional depth

beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>

Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The perfect matching problem is known to

be in P, in randomized NC, and it is hard for NL.

Whether the perfect matching problem is in NC is one of

the most prominent open questions in complexity

theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem

more >>>

Manindra Agrawal, Somenath Biswas

We give new randomized algorithms for testing multivariate polynomial

identities over finite fields and rationals. The algorithms use

\lceil \sum_{i=1}^n \log(d_i+1)\rceil (plus \lceil\log\log C\rceil

in case of rationals where C is the largest coefficient)

random bits to test if a

polynomial P(x_1, ..., x_n) is zero where d_i is ...
more >>>

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Motivated by the question of how to define an analog of interactive

proofs in the setting of logarithmic time- and space-bounded

computation, we study complexity classes defined in terms of

operators quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Manindra Agrawal, Thomas Thierauf

We show that the satisfiability problem for

bounded error probabilistic ordered branching programs is NP-complete.

If the error is very small however

(more precisely,

if the error is bounded by the reciprocal of the width of the branching program),

then we have a polynomial-time algorithm for the satisfiability problem.

more >>>

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the

function classes #P, #SAC^1, #L, and #NC^1, we study the

class of functions #AC^0. One way to define #AC^0 is as the

class of functions computed by constant-depth polynomial-size

arithmetic circuits of unbounded fan-in addition ...
more >>>

Manindra Agrawal, Thomas Thierauf

We investigate the computational complexity of the Boolean Isomorphism problem (BI):

on input of two Boolean formulas F and G decide whether there exists a permutation of

the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

Manindra Agrawal, Eric Allender

We show that all sets complete for NC$^1$ under AC$^0$

reductions are isomorphic under AC$^0$-computable isomorphisms.

Although our proof does not generalize directly to other

complexity classes, we do show that, for all complexity classes C

closed under NC$^1$-computable many-one reductions, the sets ...
more >>>

Manindra Agrawal, Richard Beigel, Thomas Thierauf

The classes of languages accepted by nondeterministic polynomial-time

Turing machines (NP machines, in short) that have restricted access to

an NP oracle --- the machines can ask k queries to the NP oracle and

the answer they receive is the number of queries ...
more >>>