Manindra Agrawal

Madhuri Kanitkar

Mathukumalli Vidyasagar

Proceedings of the 2021 60th IEEE Conference on Decision and Control (CDC), 2021

2020

Impossibility of Derandomizing the Isolation Lemma for all Families.

[BibT_eX]

[DOI]

Rohit Gurjar

Electron. Colloquium Comput. Complex., 2020

2019

The query complexity of a permutation-based variant of Mastermind.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

2018

Bootstrapping variables in algebraic circuits.

[BibT_eX]

[DOI]

Sumanta Ghosh

Electron. Colloquium Comput. Complex., 2018

On the optimality of lattices for the coppersmith technique.

[BibT_eX]

[DOI]

Appl. Algebra Eng. Commun. Comput., 2018

2017

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Dimension, pseudorandomness and extraction of pseudorandomness.

[BibT_eX]

[DOI]

Comput., 2017

2016

Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits.

[BibT_eX]

[DOI]

Ramprasad Saptharishi

SIAM J. Comput., 2016

Integer Factoring Using Small Algebraic Dependencies.

[BibT_eX]

[DOI]

Shubham Sahai Srivastava

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Approximate Verification of the Symbolic Dynamics of Markov Chains.

[BibT_eX]

[DOI]

J. ACM, 2015

2014

Theory and Applications of Models of Computation at the Turing Centenary in China.

[BibT_eX]

[DOI]

George Barmpalias

S. Barry Cooper

Theor. Comput. Sci., 2014

Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

A Roadmap for TAMC.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2014

2013

Hitting-sets for low-distance multilinear depth-3.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Quasi-polynomial hitting-set for set-depth-Δ formulas.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

The Query Complexity of Finding a Hidden Permutation.

[BibT_eX]

[DOI]

Proceedings of the Space-Efficient Data Structures, 2013

2012

Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The Deterministic and Randomized Query Complexity of a Simple Guessing Game.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421).

[BibT_eX]

[DOI]

Christopher Umans

Dagstuhl Reports, 2012

The Discrete Time Behaviour of Restricted Linear Hybrid Automata.

[BibT_eX]

[DOI]

Proceedings of the Modern Applications of Automata Theory., 2012

2011

Theory and applications of models of computation (TAMC 2008).

[BibT_eX]

[DOI]

Angsheng Li

Theor. Comput. Sci., 2011

The isomorphism conjecture for constant depth reductions.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.

[BibT_eX]

[DOI]

Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2011

On the Arithmetic Complexity of Euler Function.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Preface to Special Issue: Theory and Applications of Models of Computation (TAMC 2008-2009).

[BibT_eX]

[DOI]

S. Barry Cooper

Angsheng Li

Math. Struct. Comput. Sci., 2010

2009

One-Way Functions and the Isomorphism Conjecture.

[BibT_eX]

[DOI]

Osamu Watanabe

Electron. Colloquium Comput. Complex., 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

One-Way Functions and the Berman-Hartmanis Conjecture.

[BibT_eX]

[DOI]

Osamu Watanabe

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Arithmetic Circuits: A Chasm at Depth Four.

[BibT_eX]

[DOI]

V. Vinay

Electron. Colloquium Comput. Complex., 2008

2007

The Polynomially Bounded Perfect Matching Problem Is in NC 2.

[BibT_eX]

[DOI]

Thanh Minh Hoang

Proceedings of the STACS 2007, 2007

07411 Abstracts Collection -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

07411 Executive Summary -- Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006

The polynomially bounded perfect matching problem is in NC^2.

[BibT_eX]

[DOI]

Thanh Minh Hoang

Electron. Colloquium Comput. Complex., 2006

Equivalence of F-Algebras and Cubic Forms.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

Primality Tests Based on Fermat's Little Theorem.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing and Networking, 8th International Conference, 2006

Behavioural Approximations for Restricted Linear Differential Hybrid Automata.

[BibT_eX]

[DOI]

Proceedings of the Hybrid Systems: Computation and Control, 9th International Workshop, 2006

2005

Automorphisms of Finite Rings and Applications to Complexity of Problems.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

The Discrete Time Behavior of Lazy Linear Hybrid Automata.

[BibT_eX]

[DOI]

P. S. Thiagarajan

Proceedings of the Hybrid Systems: Computation and Control, 8th International Workshop, 2005

Proving Lower Bounds Via Pseudo-random Generators.

[BibT_eX]

[DOI]

Proceedings of the FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 2005

2004

Lazy Rectangular Hybrid Automata.

[BibT_eX]

[DOI]

P. S. Thiagarajan

Proceedings of the Hybrid Systems: Computation and Control, 7th International Workshop, 2004

2003

Primality and identity testing via Chinese remaindering.

[BibT_eX]

[DOI]

J. ACM, 2003

On Derandomizing Tests for Certain Polynomial Identities.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

For completeness, sublogarithmic space is no space.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2002

Pseudo-Random Generators and Structure of Complete Degrees.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Reducing the complexity of reductions.

[BibT_eX]

[DOI]

Comput. Complex., 2001

The First-Order Isomorphism Theorem.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Hard Sets and Pseudo-random Generators for Constant Depth Circuits.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Towards Uniform AC0 - Isomorphisms.

[BibT_eX]

[DOI]

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

The Formula Isomorphism Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

On TC0, AC0, and Arithmetic Circuits.

[BibT_eX]

[DOI]

Eric Allender

Samir Datta

J. Comput. Syst. Sci., 2000

Characterizing Small Depth and Small Space Classes by Operators of Higher Type.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2000

1999

Reducing Randomness via Chinese Remaindering

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

1998

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

[BibT_eX]

[DOI]

Eric Allender

Steven Rudich

J. Comput. Syst. Sci., 1998

Characterizing Small Depth and Small Space Classes by Operators of Higher Types

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

1997

DSPACE(n) = NSPACE(n): A Degree Theoretic Characterization.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

The Satisfiability Problem for Probabilistic Ordered Branching Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

1996

Quasi-Linear Truth-Table Reductions to p-Selective Sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Geometric Sets of Low Information Content.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

NP-Creative Sets: A New Class of Creative Sets in NP.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1996

Polynomial-Time Isomorphism of 1-L-Complete Sets.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

On the Isomorphism Conjecture for Weak Reducibilities.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1996

On the Isomorphism Conjecture for 2-DFA Reductions.

[BibT_eX]

[DOI]

Srinivasan Venkatesh

Int. J. Found. Comput. Sci., 1996

A Note on Decision versus Search for Graph Automorphism.

[BibT_eX]

[DOI]

Inf. Comput., 1996

The Boolean Isomorphism Problem

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

An Isomorphism Theorem for Circuit Complexity

[BibT_eX]

[DOI]

Eric Allender

Electron. Colloquium Comput. Complex., 1996

Modulo Information from Nonadaptive Queries to NP

[BibT_eX]

[DOI]

Richard Beigel

Electron. Colloquium Comput. Complex., 1996

Pinpointing Computation with Modular Queries in the Boolean Hierarchy.

[BibT_eX]

[DOI]

Richard Beigel

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1996

1995

Reductions of Self-Reducible Sets to Depth-1 Weighted Threshold Circuit Classes, and Sparse Sets.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

DSPACE(n)=?NSPACE(n): A Degree Theoretic Characterization.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Polynomial Time Truth-Table Reductions to P-Selective Sets.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

On the Isomorphism Problem for Weak Reducibilities.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Polynomial Isomorphism of 1-L-Complete Sets.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

Universal Relations.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

NP-hard Sets and Creativeness over Constant Time Languages.

[BibT_eX]

[DOI]