We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2
when there are a few errors in the input string.
Counting Paths in VPA is Complete for #NC1.
with Andreas Krebs, Meena Mahajan
To appear in proceedings of the
16th International Computing and Combinatorics Conference, COCOON, July 19-21, 2010.
[PDF]
[Abstract +]
We prove a #NC1 upper bound for the problem of counting accepting paths in any fixed visibly pushdown automaton. Our algorithm involves a non-trivial adaptation of the arithmetic formula evaluation algorithm of Buss, Cook, Gupta, Ramachandran. We also show that the problem is #NC1 hard. Our results show that the difference between #BWBP and #NC1 is captured exactly by the addition of a visible stack to a nondeterministic finite-state automata.
Streaming Algorithms for Some Problems in Log-space.
with Ajesh Babu and Girish Varma
To appear in proceedings of the
7th Annual Conference on Theory and Applications of Models of Computation, (TAMC)
Prague, Czech Republic, June 7-11, 2010
[PDF]
[Abstract +]
In this paper, we give streaming algorithms for some problems
which are known to be in deterministic log-space, when the number of
passes made on the input is unbounded. If the input data is massive,
the conventional deterministic log-space algorithms may not run efficiently.
We study the complexity of the problems when the number of passes is bounded.
The first problem we consider is the membership testing problem for
deterministic linear languages, DLIN. Extending the recent work of
Magniez et al (to appear in STOC 2010), we study the use of fingerprinting
technique for this problem.
We give the following streaming algorithms for the membership testing of DLINs:
a randomized one pass algorithm
that uses O(log n) space (one-sided error, inverse polynomial error probability),
and also a p-pass
O(n/p)-space deterministic algorithm. We also prove that there exists a
language in DLIN, for which any p-pass deterministic algorithm for
membership testing, requires Omega(n/p) space. We also study the application
of fingerprinting technique to visibly pushdown languages, VPLs.
The other problem we consider is, given a degree sequence and a graph,
checking whether the graph has the given degree sequence, DEGSEQ.
We prove that, any p-pass deterministic algorithm that takes as its
input a degree sequence, followed by an adjacency
list of a graph, requires Omega(n/p) space to decide DEGSEQ.
However, using randomness, for a more general input format:
degree sequence, followed by a list of edges in any arbitrary order, DEGSEQ
can be decided in O(\log n) space. We also give
a p-pass, O(n/p)-space deterministic algorithm for DEGSEQ.
Planar Graph Isomorphism is in Log-space.
with Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner
Appeared in proceedings of the 2009 24th Annual IEEE
Conference on Computational Complexity CCC, July 15--18, 2009, Paris,
France. pp. 203--214.
[PDF]
[Abstract +]
Graph Isomorphism is the prime example of a computational problem with
a wide difference between the best known lower and upper bounds on its
complexity. There is a significant gap between extant lower and upper
bounds for planar graphs as well. We bridge the gap for this natural
and important special case by presenting an upper bound that matches
the known log-space hardness [JKMT03]. In fact, we show the formally
stronger result that planar graph canonization is in log-space. This
improves the previously known upper bound of AC1 [MR91]. Our algorithm
first constructs the biconnected component tree of a connected planar
graph and then refines each biconnected component into a triconnected
component tree. The next step is to log-space reduce the biconnected
planar graph isomorphism and canonization problems to those for
3-connected planar graphs, which are known to be in log-space by
[DLN08]. This is achieved by using the above decomposition, and by
making significant modifications to Lindell’s algorithm for tree
canonization, along with changes in the space complexity analysis. The
reduction from the connected case to the biconnected case requires
further new ideas, including a non-trivial case analysis and a group
theoretic lemma to bound the number of automorphisms of a colored
3-connected planar graph. This lemma is crucial for the reduction to
work in log-space.
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata.
with Meena Mahajan
in Proceedings of 3rd International Conference on Language and Automata
Theory and Applications LATA, April 2009, Tarragona, Spain.
Springer-Verlag Lecture Notes in Computer Science series Volume 5457
pp. 493--504.
[PDF]
[Abstract +]
We show that fixed membership testing for many interesting
subclasses of multi-pushdown machines is no harder than for pushdowns
with single stack. The models we consider are MVPA, OVPA and MPDA,
which have all been defined and studied in the past.
Multi-stack pushdown automata, MPDA, have ordered stacks with pop
access restricted to the stack-top of the first non-empty stack. The mem-
bership for MPDAs is known to be in NSPACE(n) and in P. We show
that the P-time algorithm can be implemented in the complexity class
LogCFL; thus membership for MPDAs is LogCFL-complete.
It follows that membership testing for ordered visibly pushdown au-
tomata OVPA is also in LogCFL.
The membership problem for multi-stack visibly pushdown automata,
MVPA, is known to be NP-complete. However, many applications focus
on MVPA with O(1) phases. We show that for MVPA with O(1) phases,
membership reduces to that in MPDAs, and so is in LogCFL.
Longest Paths in Planar DAGs in Unambiguous Logspace.
with Meena Mahajan and Prajakta Nimbhorkar.
To appear in Chicago Journal of Theoretical Computer Science, special
issue for CATS 2009.
A preliminary version appeared in Proceedings of Computing: The
Australasian Theory Symposium, CATS, January 2009, New Zealand.
CRPIT Series Volume 94, pp. 99--105.
[PDF]
[Abstract +]
We present a transformation from longest paths to shortest paths in sub-classes of directed
acyclic graphs (DAGs). The transformation needs log-space and oracle access to reachability in
the same class of graphs. As a corollary, we obtain our main result: Longest Paths in planar
DAGs is in UL. The result also extends to toroidal DAGs. Further, we show that
Longest Paths in max-unique DAGs where the target node is the unique sink is in UL.
We show that for planar DAGs with the promise that the number of distinct paths is bounded
by a polynomial, counting paths can be done by an unambiguous pushdown automaton equipped
with an auxiliary log-space worktape and running in polynomial time. This bound also holds
if we want to compute the number of longest paths, or shortest paths, and this number is
bounded by a polynomial (irrespective of the total number of paths). Along the way, we show
that counting paths in general DAGs can be done by a deterministic pushdown automaton with
an auxiliary log-space worktape and running in polynomial time, and hence is in the complexity
class LogDCFL, provided the number of paths is bounded by a polynomial and the target node
is the only sink.
3-connected Planar Graph Isomorphism in Logspace.
with Samir Datta and Prajakta Nimbhorkar.
Appeared in Proceedings of Foundations of Software Technology and Theoretical Computer Science, FSTTCS,
December 9-11, 2008, Bangalore, India.
[PDF]
[Abstract +]
We consider the isomorphism and canonization problem for 3-connected planar graphs.
The problem was known to be L -hard and in UL coUL [TW08]. In this
paper, we give a deterministic log-space algorithm for 3-connected
planar graph isomorphism and canonization. This gives an
L -completeness result, thereby settling its complexity.
The algorithm uses the notion of universal exploration sequences from
[Kou02] and [Rei05]. To our knowledge, this is a completely new
approach to graph canonization.
On the Complexity of Membership and Counting in Height-deterministic Pushdown Automata.
with Meena Mahajan and Antoine Meyer.
A preliminary version appeared
in Proceedings of 3rd International Computer Science Symposium in Russia CSR, June 7--12, 2008, Moscow.
Springer-Verlag Lecture Notes in Computer Science series Volume 5010
pp. 240--251.
Submitted to Chicago Journal of Theoretical Computer Science.
[PDF]
[Abstract +]
While visibly pushdown languages properly generalise regular languages
and are properly contained in deterministic context-free languages,
the complexity of their membership problem is equivalent to that of
regular languages. However, the corresponding counting problem could
be harder than counting paths in a non-deterministic finite automaton:
it is only known to be in LogDCFL. We investigate the membership and
counting problems for generalisations of visibly pushdown automata,
defined using the notion of height-determinism. We show that, when the
stack-height of a given PDA can be computed using a finite transducer,
both problems have the same complexity as for visibly pushdown
languages. We also show that when allowing pushdown transducers
instead of finite-state ones, both problems become LogDCFL-complete;
this uses the fact that pushdown transducers are sufficient to compute
the stack heights of all real-time height-deterministic pushdown
automata, and yields a candidate arithmetization of LogDCFL that is no
harder than LogDCFL(our main result).
Planarity, Determinants, Permanents, and (Unique) Perfect Matchings.
with Samir Datta, Raghav Kulkarni, and Meena Mahajan.
To appear in the journal Transactions on Computation Theory.
A preliminary version appeared in Proceedings of 2nd International
Computer Science Symposium in Russia CSR, Sep 3--7, 2007,
Ekaterinburg.
Springer-Verlag Lecture Notes in Computer Science series Volume 4649
pp. 115--126.
[PDF]
[Abstract +]
Viewing the computation of the determinant and the permanent
of integer matrices as combinatorial problems on associated graphs, we
explore the restrictiveness of planarity on their complexities and
show that both problems remain as hard as in the general case, i.e.
GapL and #P complete. On the other hand, both bipartite planarity and
bimodal planarity bring the complexity of permanents down (but no
further) to that of determinants. The permanent or the determinant
modulo 2 is complete for L, and we show that parity of paths in a
layered grid graph (which is bimodal planar) is also complete for this
class. We also relate the complexity of grid graph reachability to
that of testing existence/uniqueness of a perfect matching in a planar
bipartite graph.
Arithmetizing Classes around NC1 and L.
with Meena Mahajan and B. V. Raghavendra Rao.
To appear in Theory of Computing systems , special
issue for STACS 2007.
A preliminary version appeared in Proceedings of 24th International
Symposium on Theoretical Aspects of Computer Science STACS, 22-24 Feb
2007, Aachen (Germany). Springer-Verlag Lecture Notes in Computer
Science series Volume 4393 pp. 477--488.
[PDF]
[Abstract +]
The parallel complexity class NC1 has many equivalent models such as
polynomial size formulae and bounded width branching programs.
Caussinus et al. [CMTV98] considered arithmetizations of two of these
classes, #NC1 and #BWBP. We further this study to include
arithmetization of other classes. In particular, we show that counting
paths in branching programs over visibly pushdown automata is in
FLogDCFL, while counting proof-trees in logarithmic width formulae has
the same power as #NC1 . We also consider polynomial-degree
restrictions of SCi , denoted sSCi , and show that the Boolean class
sSC1 is sandwiched between NC1 and L, whereas sSC0 equals NC1 . On the
other hand, the arithmetic class #sSC0 contains #BWBP and is contained
in FL, and #sSC1 contains #NC1 and is in SC2 . We also investigate
some closure properties of the newly defined arithmetic classes.
Upper Bounds for Monotone Planar Circuit Value and Variants.
with Meena Mahajan and Jayalal Sarma M. N.
Appeared in the journal Computational Complexity, Volume 18,
2009, pp. 377--412.
A preliminary version titled "Evaluating Monotone Circuits on Cylinders, Planes and Tori"
appeared in the Proceedings of 23rd Symposium on Theoretical Aspects of Computer Science STACS, 23-25 Feb 2006.
Springer-Verlag Lecture Notes in Computer Science series Volume 3884 pp 660-671.
The full version is a technical report of the ECCC.
[PDF]
[Abstract +]
The P-complete Circuit Value Problem CVP, when restricted to monotone
planar circuits MPCVP, is known to be in NC3,
and for the special case of upward stratified circuits, it is known to be in
LogDCFL. In this paper we re-examine the complexity of MPCVP, with
special attention to circuits with cylindrical embeddings. We
characterize cylindricality, which is stronger than planarity but
strictly generalizes
upward planarity, and make the characterization partially constructive.
We use this construction, and four key reduction lemmas, to obtain
several improvements. We show that stratified cylindrical monotone
circuits can be evaluated in LogDCFL, and arbitrary cylindrical mono-
tone circuits can be evaluated in AC1 (LogDCFL), while monotone circuits
with one-input-face planar embeddings can be evaluated in LogCFL. For
monotone circuits with focused embeddings, we show an upper bound of
AC1 (LogDCFL). We re-examine the NC3 algorithm for general MPCVP,
and note that it is in AC1 (LogCFL) = SAC2 . Finally, we consider exten-
sions beyond MPCVP. We show that monotone circuits with toroidal
embeddings can, given such an embedding, be evaluated in NC. Also,
special kinds of arbitrary genus circuits can also be evaluated in NC.
We also show that planar non-monotone circuits with polylogarithmic
negation-height can be evaluated in NC.
Return to top
Small-depth Multilinear Formula Lower bounds for Iterated Matrix Mulitplication, with applications.
Algebraic Methods, Simons Institute, Dec 2018.
STCS Seminar Series, Tata Institute of Fundamental Research, Nov 2017.
[Video]
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates.
CAALM 2019, Chennai Mathematical Institute, Jan 2019.
Theory Seminar, Simons Institute, Nov 2018.
[Slides]
A Near-Optimal Depth-Hierarchy Theorem for
Small-Depth Multilinear Circuits.
Dagstuhl Seminar on Algebraic Methods in Computational Complexity, Dagstuhl, Germany, Sept 2018.
TOC Seminar, Harvard University, Oct 2018.
[Slides]
Sum of Powers of Linear Forms.
Algebraic Complexity Reading group, Simons Institute, Nov 2018.
Workshop on Arithmetic Complexity, The Institute of Mathematical Sciences, Chennai, Feb 2017.
[Video]
Depth 4 lower bounds for elementary symmetric polynomials.
TuFTLeR, Frontiers of Theory, Lectures and Research, Black Forest, Germany, Jun 2017.
Low-Depth Complexity Workshop, St. Petersburg, Russia, May 2016.
[Slides]
Isolation Lemma for Directed Reachability and NL vs. L.
Dagstuhl Seminar on Algebraic Methods in Computational Complexity, Dagstuhl, Germany, Oct 2016.
[Slides]
The shifted partial derivative complexity of elementary symmetric polynomials
Indo-UK workshop on Computational Complexity Theory, The Institute of Mathematical Sciences, Chennai, Jan 2015.
[Video]
Return to top