Streaming algorithms for recognizing nearly well-parenthesized expressions
To appear in proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science MFCS, August 22-24, 2011.
[PDF] [Abstract +]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.
To appear in proceedings of the 16th International Computing and Combinatorics Conference COCOON, 19-21 July, 2010, Vietnam.
[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.
Steaming algorithms for some problems in log-space.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.