Vikraman Arvind

Electron. Colloquium Comput. Complex., 2023

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time.

[BibT_eX]

[DOI]

Abhranil Chatterjee

Electron. Colloquium Comput. Complex., 2023

On Lifting Lower Bounds for Noncommutative Circuits using Automata.

[BibT_eX]

[DOI]

Abhranil Chatterjee

Electron. Colloquium Comput. Complex., 2023

On a Hierarchy of Spectral Isomorphism Invariants.

[BibT_eX]

[DOI]

CoRR, 2023

The Parallel Dynamic Complexity of the Abelian Cayley Group Membership Problem.

[BibT_eX]

[DOI]

Shankar Ram Vasudevan

CoRR, 2023

On Identity Testing and Noncommutative Rank Computation over the Free Skew Field.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2022

Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2022

On the Weisfeiler-Leman dimension of fractional packing.

[BibT_eX]

[DOI]

Inf. Comput., 2022

Matrix Polynomial Factorization via Higman Linearization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

On Efficient Noncommutative Polynomial Factorization via Higman Linearization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time.

[BibT_eX]

[DOI]

Abhranil Chatterjee

Electron. Colloquium Comput. Complex., 2022

Recognizing the Commuting Graph of a Finite Group.

[BibT_eX]

[DOI]

Peter J. Cameron

CoRR, 2022

Isomorphism testing of k-spanning tournaments is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

Ilia Ponomarenko

Grigory Ryabov

CoRR, 2022

Theory research in India: 2019-2022.

[BibT_eX]

[DOI]

C. Aiswarya

Saket Saurabh

Commun. ACM, 2022

CNF Satisfiability in a Subspace and Related Problems.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Algorithmica, 2022

Fast Exact Algorithms Using Hadamard Product of Polynomials.

[BibT_eX]

[DOI]

Algorithmica, 2022

Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed-Parameter Tractable (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

2021

Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable.

[BibT_eX]

[DOI]

CoRR, 2021

Parameterized Complexity of Small Weight Automorphisms and Isomorphisms.

[BibT_eX]

[DOI]

Algorithmica, 2021

Equivalence Testing of Weighted Automata over Partially Commutative Monoids.

[BibT_eX]

[DOI]

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

On Weisfeiler-Leman invariance: Subgraph counts and related graph properties.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

Multiplicity Equivalence Testing of Automata over Partially Commutative Monoids.

[BibT_eX]

[DOI]

CoRR, 2020

On Explicit Branching Programs for the Rectangular Determinant and Permanent Polynomials.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2020

A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Randomized Polynomial-Time Identity Testing for Noncommutative Circuits.

[BibT_eX]

[DOI]

Theory Comput., 2019

Efficient Black-Box Identity Testing for Free Group Algebra.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Efficient Black-Box Identity Testing over Free Group Algebra.

[BibT_eX]

[DOI]

CoRR, 2019

Efficient Black-Box Identity Testing for Free Group Algebras.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Expanding Generating Sets for Solvable Permutation Groups.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Beating Brute Force for Polynomial Identity Testing of General Depth-3 Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

A Note on Polynomial Identity Testing for Depth-3 Circuits.

[BibT_eX]

[DOI]

CoRR, 2018

On the hardness of the noncommutative determinant.

[BibT_eX]

[DOI]

Comput. Complex., 2018

2017

Finding fixed point free elements and small bases in permutation groups.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

A Quest for Structure in Complexity.

[BibT_eX]

[DOI]

Meena Mahajan

Bull. EATCS, 2017

Graph Isomorphism, Color Refinement, and Compactness.

[BibT_eX]

[DOI]

Comput. Complex., 2017

Efficient Identity Testing and Polynomial Factorization in Nonassociative Free Rings.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2016

Randomized Polynomial Time Identity Testing for Noncommutative Circuits.

[BibT_eX]

[DOI]

Raja S

Electron. Colloquium Comput. Complex., 2016

Parameterized Complexity of Small Weight Automorphisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Identity Testing for +-Regular Noncommutative Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

The Weisfeiler-Lehman Procedure.

[BibT_eX]

[DOI]

Bull. EATCS, 2016

Some Lower Bound Results for Set-Multilinear Arithmetic Computations.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2016

The Parameterized Complexity of Geometric Graph Isomorphism.

[BibT_eX]

[DOI]

Algorithmica, 2016

Solving Linear Equations Parameterized by Hamming Weight.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

On the isomorphism problem for decision trees and decision lists.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Noncommutative Valiant's Classes: Structure and Complete Problems.

[BibT_eX]

[DOI]

Raja S

Electron. Colloquium Comput. Complex., 2015

On the Complexity of Noncommutative Polynomial Factorization.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Robust Oracle Machines revisited.

[BibT_eX]

[DOI]

Bull. EATCS, 2015

Colored Hypergraph Isomorphism is Fixed Parameter Tractable.

[BibT_eX]

[DOI]

Algorithmica, 2015

On Tinhofer's Linear Programming Approach to Isomorphism Testing.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

On the Power of Color Refinement.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 20th International Symposium, 2015

2014

Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

The Complexity of Geometric Graph Isomorphism.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

The Complexity of Two Register and Skew Arithmetic Computation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

On Lower Bounds for Multiplicative Circuits and Linear Circuits in Noncommutative Domains.

[BibT_eX]

[DOI]

A. V. Sreejith

Proceedings of the Computer Science - Theory and Applications, 2014

The Complexity of Bounded Register and Skew Arithmetic Computation.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 20th International Conference, 2014

2013

Comments on Arithmetic Complexity, Kleene Closure, and Formal Power Series.

[BibT_eX]

[DOI]

Eric Allender

Meena Mahajan

Theory Comput. Syst., 2013

The Alon-Roichman Theorem.

[BibT_eX]

[DOI]

Bull. EATCS, 2013

The Parameterized Complexity of some Permutation Group Problems

[BibT_eX]

[DOI]

CoRR, 2013

The Parallel Complexity of Graph Canonization Under Abelian Group Action.

[BibT_eX]

[DOI]

Algorithmica, 2013

The Parameterized Complexity of Fixpoint Free Elements and Bases in Permutation Groups.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 8th International Symposium, 2013

2012

Testing nilpotence of galois groups in polynomial time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

The isomorphism problem for k-trees is complete for logspace.

[BibT_eX]

[DOI]

Inf. Comput., 2012

Approximate Graph Isomorphism.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

[BibT_eX]

[DOI]

CoRR, 2012

Near-Optimal Expanding Generator Sets for Solvable Permutation Groups.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

2011

Solvable Group Isomorphism Is (Almost) in NP ∩ coNP.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2011

Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits.

[BibT_eX]

[DOI]

Yadu Vasudev

Electron. Colloquium Comput. Complex., 2011

Expanding Generator Sets for Solvable Permutation Groups.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs.

[BibT_eX]

[DOI]

Prajakta Nimbhorkar

Electron. Colloquium Comput. Complex., 2011

Noncommutative Arithmetic Circuits meet Finite Automata.

[BibT_eX]

[DOI]

Bull. EATCS, 2011

Canonizing Hypergraphs under Abelian Group Action.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

Isomorphism and canonization of tournaments and hypertournaments.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

Uniform Derandomization from Pathetic Lower Bounds.

[BibT_eX]

[DOI]

Eric Allender

Fengming Wang

Electron. Colloquium Comput. Complex., 2010

Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes.

[BibT_eX]

[DOI]

Comput. Complex., 2010

New Results on Noncommutative and Commutative Polynomial Identity Testing.

[BibT_eX]

[DOI]

Comput. Complex., 2010

2009

Parameterized learnability of juntas.

[BibT_eX]

[DOI]

Wolfgang Lindner

Theor. Comput. Sci., 2009

Circuit Lower Bounds, Help Functions, and the Remote Point Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

On Lower Bounds for Constant Width Arithmetic Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Arithmetic Circuit Size, Identity Testing, and Finite Automata.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

The Remote Point Problem, Small Bias Space, and Expanding Generator Sets

[BibT_eX]

[DOI]

CoRR, 2009

Arithmetic Circuits, Monomial Algebras and Finite Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Arithmetic Circuits and the Hadamard Product of Polynomials.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach.

[BibT_eX]

[DOI]

Christine T. Cheng

Nikhil R. Devanur

SIAM J. Discret. Math., 2008

SZK Proofs for Black-Box Group Problems.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2008

The Orbit problem is in the GapL Hierarchy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Quantum Query Complexity of Multilinear Identity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Lattice Problems, Gauge Functions and Parameterized Algorithms

[BibT_eX]

[DOI]

CoRR, 2008

Algorithmic Problems for Metrics on Permutation Groups.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, 2008

Some Sieving Algorithms for Lattice Problems.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

A Logspace Algorithm for Partial 2-Tree Canonization.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2008

Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

The Ideal Membership Problem and Polynomial Identity Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

The Monomial Ideal Membership Problem and Polynomial Identity Testing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

The Space Complexity of k -Tree Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Parameterized Learnability of k -Juntas and Related Problems.

[BibT_eX]

[DOI]

Wolfgang Lindner

Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006

On Hypergraph and Graph Isomorphism with Bounded Color Classes.

[BibT_eX]

[DOI]

Proceedings of the STACS 2006, 2006

A Polynomial Time Nilpotence Test for Galois Groups and Related Results.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 17th International Symposium, 2006

The Complexity of Black-Box Ring Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 12th Annual International Conference, 2006

2005

Isomorphism Testing: Perspective and Open Problems.

[BibT_eX]

Bull. EATCS, 2005

The Complexity of Solving Linear Equations over a Finite Ring.

[BibT_eX]

[DOI]

Proceedings of the STACS 2005, 2005

2004

Non-stabilizer quantum codes from Abelian subgroups of the error group.

[BibT_eX]

[DOI]

K. R. Parthasarathy

Quantum Inf. Comput., 2004

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Solvable Group Isomorphism is (almost) in NP\cap coNP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Abelian Permutation Group Problems and Logspace Counting Classes.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

Solvable Group Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

On the Complexity of Computing Units in a Number Field.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Number Theory, 6th International Symposium, 2004

2003

Upper Bounds on the Complexity of some Galois Theory Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems.

[BibT_eX]

[DOI]

Rainer Schuler

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

2002

New Lowness Results for ZPPNP and Other Complexity Classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2002

Graph Isomorphism is in SPP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Approximate Counting small subgraphs of bounded treewidth and related problems

[BibT_eX]

[DOI]

Venkatesh Raman

Electron. Colloquium Comput. Complex., 2002

The Query Complexity of Program Checking by Constant-Depth Circuits.

[BibT_eX]

[DOI]

K. V. Subrahmanyam

Chic. J. Theor. Comput. Sci., 2002

Approximation Algorithms for Some Parameterized Counting Problems.

[BibT_eX]

[DOI]

Venkatesh Raman

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001

A nonadaptive NC checker for permutation group intersection.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

On pseudorandomness and resource-bounded measure.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

2000

The counting complexity of group-definable languages.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

Exact learning via teaching assistants.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

The Complexity of Modular Graph Automorphism.

[BibT_eX]

[DOI]

Richard Beigel

Antoni Lozano

SIAM J. Comput., 2000

Nondeterministic Instance Complexity and Hard-to-Prove Tautologies.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results.

[BibT_eX]

[DOI]

Proceedings of the STACS 2000, 2000

1999

Sparse Sets, Approximable Sets, and Parallel Queries to NP.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Graph Isomorphism is Low for ZPPNP and other Lowness results.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Arithmetic Complexity, Kleene Closure, and Formal Power Series

[BibT_eX]

[DOI]

Eric Allender

Meena Mahajan

Electron. Colloquium Comput. Complex., 1999

1997

Solvable Black-Box Group Problems are Low for PP.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

Constructivizing Membership Proofs in Complexity Classes.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1997

On Resource-Bounded Measure and Pseudorandomness.

[BibT_eX]

[DOI]

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

Exact Learning via Teaching Assistants (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 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

Upper Bounds for the Complexity of Sparse and Tally Descriptions.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1996

Monotonous and Randomized Reductions to Sparse Sets.

[BibT_eX]

[DOI]

RAIRO Theor. Informatics Appl., 1996

A Note on Decision versus Search for Graph Automorphism.

[BibT_eX]

[DOI]

Inf. Comput., 1996

A Note on the Self-Witnessing Property of Computational Problems.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, Second Annual International Conference, 1996

The Complexity of Exactly Learning Algebraic Concepts. (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 7th International Workshop, 1996

1995

If NP has Polynomial-Size Circuits, then MA=AM.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

On Reductions to Sets that Avoid EXPSPACE.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1995

On Helping and Interactive Proof Systems.

[BibT_eX]

[DOI]

Rainer Schuler

Int. J. Found. Comput. Sci., 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

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

1993

Hausdorff Reductions to Sparse Sets and to Sets of High Information Content.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

1992

Lowness and the Complexity of Sparse and Tally Descriptions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, Third International Symposium, 1992

On Bounded Truth-Table, Conjunctive, and Randomized Reductions to Sparse Sets.

[BibT_eX]

[DOI]

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

Reductions to Sets of Low Information Content.

[BibT_eX]

Proceedings of the Complexity Theory: Current Research, 1992

1991

Edge-Deletion Graph Problems with First-Order Expressible Subgraph Properties.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1991

A heuristic search strategy for optimization of trade-off cost measures.

[BibT_eX]

[DOI]

Rakesh Kumar Singh

Shashi Kumar

Proceedings of the Third International Conference on Tools for Artificial Intelligence, 1991

1989

On Some Bandwidth Restricted Versions of the Satisfiability Problem of Propositional CNF Formulas.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1989

1987

An O(n²) Algorithm for the Satisfiability Problem of a Subset of Propositional Sentences in CNF That Includes All Horn Sentences.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1987

Expressibility of First Order Logic with a Nondeterministic Inductive Operator.

[BibT_eX]

[DOI]

Proceedings of the STACS 87, 1987

On Certain Bandwidth Restricted Versions of the Satisfaiability Problem of Propositional CNF Formulas.

[BibT_eX]

[DOI]