Manindra Agrawal

For completeness, sublogarithmic space is no space, Manuscript (2008)

Abstract. We study the problem of expressing permanent of matrices as determinant of (possibly larger) matrices. This problem has close connections with complexity of arithmetic computations:...

Abstract (2008)

Manindra Agrawal, Thomas Thierauf, Abt Theoretische Informatik, Universität Ulm

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...

Running Head: Isomorphism of 1-L-Complete Sets Mailing address: (2008)

It is shown that for any class C closed under linear-time reductions, the complete sets for C under sublogarithmic reductions are also complete under 2DFA reductions, and thus are isomorphic under...

Manindra Agrawal, Somenath Biswas, Manindra Agrawal

Let C be any complexity class closed under log-lin reductions. We show that all sets complete for C under 1-L reductions are polynomialtime isomorphic to each other. We also generalize the result to...

On the Isomorphism Conjecture for Weak Reducibilities (2008)

Arithmetic Circuits: A Chasm at Depth Four (2008)

According to the isomorphism conjecture all NP-complete sets are polynomial-time isomorphic to each other while according to the encrypted complete set conjecture there is a p-one-way function f and...

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...

07411 Executive Summary -- Algebraic Methods in Computational Complexity (2008)

Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas

The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for...

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity (2008)

Agrawal, Manindra, Buhrman, Harry, Fortnow, Lance, Thierauf, Thomas

From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the...

Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings (2008)

Agrawal, Manindra.

Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)

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...

Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)

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...

Analysis of pseudorandom permutations (2007)

Manindra Agrawal, Vidit Jain

The main result of this study is a permutation generator which seems to behave pseudorandomly. We also propose three statistical tests for the pseudorandomness of a permutation generator. The results...

Pinpointing computation with modular queries in the boolean hierarchy (2007)

Manindra Agrawal, Richard Beigel, Thomas Thierauf

A modular query consists of asking how many (modulo m) of k strings belong to a fixed NP language. Modular queries provide a form of restricted access to an NP oracle. For each k and m, we consider...

Characterizing Small Depth and Small Space Classes by Operators of Higher Types (2007)

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...

Towards finding a Polynomial time algorithm for Graph Isomorphism problem. CS499 Report (2007)

Kshitiz Verma, Dr. Manindra Agrawal

under the supervision of

Equivalence of F-algebras and cubic forms (2006)

Manindra Agrawal, Nitin Saxena

Abstract. We study the isomorphism problem of two “natural ” algebraic structures – F-algebras and cubic forms. We prove that the F-algebra isomorphism problem reduces in polynomial time to the...

Equivalence of F-algebras and cubic forms (2006)

Manindra Agrawal, Nitin Saxena

We study the isomorphism problem of two “natural ” algebraic structures – F-algebras and cubic forms. We prove that the F-algebra isomorphism problem reduces in polynomial time to the cubic...

Behavioural approximations for restricted linear differential hybrid automata (2006)

Manindra Agrawal, Frank Stephan, P. S. Thiagarajan, Shaofa Yang

Abstract. We show the regularity of the discrete time behaviour of hybrid automata in which the rates of continuous variables are governed by linear differential operators in a diagonal form and in...

Behavioural approximations for restricted linear differential hybrid automata (2006)

Manindra Agrawal, Frank Stephan, P. S. Thiagarajan, Shaofa Yang

Abstract. We show the regularity of the discrete time behaviour of hybrid automata in which the rates of continuous variables are governed by linear differential operators in a diagonal form and in...

Determinant versus permanent (2006)

Agrawal, Manindra

We study the problem of expressing permanents of matrices as determinants of (possibly larger) matrices. This problem has close connections to the complexity of arithmetic computations: the...

The discrete time behavior of lazy linear hybrid automata (2005)

Manindra Agrawal, P. S. Thiagarajan

We study the class of lazy linear hybrid automata with finite precision. The key features of this class are: – The observation of the continuous state and the rate changes associated with mode...

P.S.: The discrete time behavior of lazy linear hybrid automata (2005)

Manindra Agrawal, P. S. Thiagarajan

Abstract. We study the class of lazy linear hybrid automata with finite precision. The key features of this class are: – The observation of the continuous state and the rate changes associated with...

Automorphisms of Finite Rings and Applications to Complexity of Problems (2005)

Manindra Agrawal, Nitin Saxena

In mathematics, automorphisms of algebraic structures play an important role.

Proving lower bounds via pseudo-random generators (2005)

Behavioural approximations for restricted linear differential hybrid automata (2005)

Abstract. In this paper, we formalize two stepwise approaches, based on pseudo-random generators, for proving P � = NP and its arithmetic analog: Permanent requires superpolynomial sized arithmetic...

Manindra Agrawal, Frank Stephan, P. S. Thiagarajan, Shaofa Yang

Abstract. We show the regularity of the discrete time behaviour of hybrid automata in which the rates of continuous variables are governed by linear differential operators in a diagonal form and in...

PRIMES is in P (2004)

Agrawal, Manindra, Kayal, Neeraj, Saxena, Nitin

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

On derandomizing tests for certain polynomial identities (2003)

We extract a paradigm for derandomizing tests for polynomial identities from the recent AKS primality testing algorithm. We then discuss its possible application to other tests. 1

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite. 1

We present a deterministic polynomial-time algorithm that determines whether n input number n is prime or composite. "The problem of distinguishing prime numbers from composite numbers and...

We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite. “The problem of distinguishing prime numbers from composite numbers and of...

We present a deterministic polynomial-time algorithm that determines whether an input number n is prime or composite. \The problem of distinguishing prime numbers from composite numbers and of...

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite. 1

Pseudo-random generators and structure of complete degrees (2002)

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite. 1.

Reducing The Complexity Of Reductions (2001)

It is shown that if there exist sets in E that require-sized circuits then sets that are hard for class P, and above, under 1-1 reductions are also hard under 1-1, sizeincreasing reductions. Under...

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

We build on the recent progress regarding isomorphisms of complete sets that was reported in Agrawal et al. (1998). In that paper, it was shown that all sets that are complete under (non-uniform) AC...

The first-order isomorphism theorem (2001)

New way of cryptanalyzing MD5 (1999)

Abstract. For any class C und closed under NC 1 reductions, it is shown that all sets complete for C under first-order (equivalently, Dlogtimeuniform AC 0) reductions are isomorphic under first-order...

In Partial Ful, Buddhi Madhav, To The, Dr. Manindra Agrawal

In this thesis, we show a new method for obtaining collisions for reduced number of rounds in MD4 and MD5 hash algorithms. We also discuss the possibility of extending the existing attacks to full...

Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)

Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)

We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0-computable isomorphisms. Furthermore, these sets remain NP-complete even under...

Reductions in circuit complexity: An isomorphism theorem and a gap theorem (1998)

We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0-computable isomorphisms. Furthermore, these sets remain NP-complete even under...

Characterizing Small Depth and Small Space Classes by Operators of Higher Types (1998)

We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0-computable isomorphisms. Furthermore, these sets remain NP-complete even under...

Manindra Agrawal Dept, 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...

Reducing the Complexity of Reductions (1997)

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...

Reducing the Complexity of Reductions (1997)

Manindra Agrawal Dept, Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...

On TC^0, AC^0, and Arithmetic Circuits (1997)

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC 1 [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC 1 [CMTV96], we study the class of functions #AC 0...

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem. (1997)

On TC^0, AC^0, and Arithmetic Circuits (1997)

We show that all sets that are complete for NP under non-uniform AC 0 reductions are isomorphic under non-uniform AC 0 -computable isomorphisms. Furthermore, these sets remain NP-complete even under...

Manindra Agrawal, Eric Allender, Samir Datta

Continuing a line of investigation that has studied the function classes #P [Val79b], #SAC 1 [Val79a, Vin91, AJMV], #L [AJ93b, Vin91, AO94], and #NC 1 [CMTV96], we study the class of functions #AC 0...

Reducing the Complexity of Reductions (1997)

Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich

We prove that the Berman-Hartmanis isomorphism conjecture is true under AC 0 reductions. More generally, we show three theorems that hold for any complexity class C closed under (uniform) TC 0...

The Boolean Isomorphism Problem (1996)

Manindra Agrawal, Thomas Thierauf, Abt Theoretische Informatik

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...

Modulo Information from Nonadaptive Queries to NP (1996)

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...

An Isomorphism Theorem for Circuit Complexity (1996)

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...

DSPACE(n) ? = NSPACE(n): A degree theoretic characterization (1995)

International Journal of Foundations of Computer Science c ○ World Scientific Publishing Company ON THE ISOMORPHISM CONJECTURE FOR 2-DFA REDUCTIONS (1995)

It is shown that the following are equivalent. 1. DSPACE(n) = NSPACE(n). 2. There is a non-trivial ≤1−NL m-degree that coincides with a ≤1−L m-degree. 3. For every class C closed under...

Manindra Agrawal, S. Venkatesh, Communicated J. Y. Cai

The degree structure of complete sets under 2DFA reductions is investigated. It is shown that, for any class C that is closed under log-lin reductions: • All complete sets for the class C under...

Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem.