BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Samir Datta

Samir Datta appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityData Structures and Algorithmsmath.COComputer Science and Game TheoryDiscrete MathematicsLogic in Computer Science

Catalog footprint

What is connected

11works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2020arXiv

Dynamic Complexity of Expansion

Dynamic Complexity was introduced by Immerman and Patnaik \cite{PatnaikImmerman97} (see also \cite{DongST95}). It has seen a resurgence of interest in the recent past, see \cite{DattaHK14,ZeumeS15,MunozVZ16,BouyerJ17,Zeume17,DKMSZ18,DMVZ18,BarceloRZ18,DMSVZ19,SchmidtSVZK20,DKMTVZ20} for some representative examples. Use of linear algebra has been a notable feature of some of these papers. We extend this theme to show that the gap version of spectral expansion in bounded degree graphs can be maintained in the class $\DynACz$ (also known as $\dynfo$, for domain independent queries) under batch changes (insertions and deletions) of $O(\frac{\log{n}}{\log{\log{n}}})$ many edges. The spectral graph theoretic material of this work is based on the paper by Kale-Seshadri \cite{KaleS11}. Our primary technical contribution is to maintain up to logarithmic powers of the transition matrix of a bounded degree undirected graph in $\DynACz$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Dynamic complexity of Reachability: How many changes can we handle?

In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size $\frac{\log n}{\log \log n}$, where $n$ is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Counting Euler Tours in Undirected Bounded Treewidth Graphs

We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a $\#SAC^1$ upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynamic programming on bounded \emph{clique-width} graphs can be performed efficiently in parallel. Thus we show that the sequential result of Espelage, Gurski and Wanke for efficiently computing Hamiltonian paths in bounded clique-width graphs can be adapted in the parallel setting to count the number of Hamiltonian paths which in turn is a tool for counting the number of Euler tours in bounded tree-width graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in bounded-clique width graphs. While establishing that counting Euler tours in bounded tree-width graphs can be computed by non-uniform monotone arithmetic circuits of polynomial degree (which characterize $\#SAC^1$) is relatively easy, establishing a uniform $\#SAC^1$ bound needs a careful use of polynomial interpolation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Graph properties in node-query setting: effect of breaking symmetry

The query complexity of graph properties is well-studied when queries are on edges. We investigate the same when queries are on nodes. In this setting a graph $G = (V, E)$ on $n$ vertices and a property $\mathcal{P}$ are given. A black-box access to an unknown subset $S \subseteq V$ is provided via queries of the form `Does $i \in S$?'. We are interested in the minimum number of queries needed in worst case in order to determine whether $G[S]$, the subgraph of $G$ induced on $S$, satisfies $\mathcal{P}$. Apart from being combinatorially rich, this setting allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on hereditary graph properties. The monotone functions in the node-query setting translate precisely to the hereditary graph properties. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on $G$, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., $n$. We show that in the absence of any symmetry on $G$ it can fall as low as $O(n^{1/(d + 1) })$ where $d$ denotes the minimum possible degree of a minimal forbidden sub-graph for $\mathcal{P}$. In particular, every hereditary property benefits at least quadratically. The main question left open is: can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with {finitely many} forbidden subgraphs by exhibiting a bound of $Ω(n^{1/k})$ for some constant $k$ depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing $Ω(\log n/ \log \log n)$ bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdös and Rado.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Bounded Treewidth and Space-Efficient Linear Algebra

Motivated by a recent result of Elberfeld, Jakoby and Tantau showing that $\mathsf{MSO}$ properties are Logspace computable on graphs of bounded tree-width, we consider the complexity of computing the determinant of the adjacency matrix of a bounded tree-width graph and as our main result prove that it is in Logspace. It is important to notice that the determinant is neither an $\mathsf{MSO}$-property nor counts the number of solutions of an $\mathsf{MSO}$-predicate. This technique yields Logspace algorithms for counting the number of spanning arborescences and directed Euler tours in bounded tree-width digraphs. We demonstrate some linear algebraic applications of the determinant algorithm by describing Logspace procedures for the characteristic polynomial, the powers of a weighted bounded tree-width graph and feasibility of a system of linear equations where the underlying bipartite graph has bounded tree-width. Finally, we complement our upper bounds by proving $\mathsf{L}$-hardness of the problems of computing the determinant, and of powering a bounded tree-width matrix. We also show the $\mathsf{GapL}$-hardness of Iterated Matrix Multiplication where each matrix has bounded tree-width.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Tree-width and Logspace: Determinants and Counting Euler Tours

Motivated by the recent result of [EJT10] showing that MSO properties are Logspace computable on graphs of bounded tree-width, we consider the complexity of computing the determinant of the adjacency matrix of a bounded tree-width graph and prove that it is L-complete. It is important to notice that the determinant is neither an MSO-property nor counts the number of solutions of an MSO-predicate. We extend this technique to count the number of spanning arborescences and directed Euler tours in bounded tree-width digraphs, and further to counting the number of spanning trees and the number of Euler tours in undirected graphs, all in L. Notice that undirected Euler tours are not known to be MSO-expressible and the corresponding counting problem is in fact #P-hard for general graphs. Counting undirected Euler tours in bounded tree-width graphs was not known to be polynomial time computable till very recently Chebolu et al [CCM13] gave a polynomial time algorithm for this problem (concurrently and independently of this work). Finally, we also show some linear algebraic extensions of the determinant algorithm to show how to compute the charcteristic polynomial and trace of the powers of a bounded tree-width graph in L.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Computing Bits of Algebraic Numbers

We initiate the complexity theoretic study of the problem of computing the bits of (real) algebraic numbers. This extends the work of Yap on computing the bits of transcendental numbers like π, in Logspace. Our main result is that computing a bit of a fixed real algebraic number is in C=NC1\subseteq Logspace when the bit position has a verbose (unary) representation and in the counting hierarchy when it has a succinct (binary) representation. Our tools are drawn from elementary analysis and numerical analysis, and include the Newton-Raphson method. The proof of our main result is entirely elementary, preferring to use the elementary Liouville's theorem over the much deeper Roth's theorem for algebraic numbers. We leave the possibility of proving non-trivial lower bounds for the problem of computing the bits of an algebraic number given the bit position in binary, as our main open question. In this direction we show very limited progress by proving a lower bound for rationals.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Planarity Testing Revisited

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem. The bounded space complexity of these problems has been determined to be exactly Logspace by Allender and Mahajan with the aid of Reingold's result. Unfortunately, the algorithm is quite daunting and generalizing it to say, the bounded genus case seems a tall order. In this work, we present a simple planar embedding algorithm running in logspace. We hope this algorithm will be more amenable to generalization. The algorithm is based on the fact that 3-connected planar graphs have a unique embedding, a variant of Tutte's criterion on conflict graphs of cycles and an explicit change of cycle basis.% for planar graphs. We also present a logspace algorithm to find obstacles to planarity, viz. a Kuratowski minor, if the graph is non-planar. To the best of our knowledge this is the first logspace algorithm for this problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Log-space Algorithms for Paths and Matchings in k-trees

Reachability and shortest path problems are NL-complete for general graphs. They are known to be in L for graphs of tree-width 2 [JT07]. However, for graphs of tree-width larger than 2, no bound better than NL is known. In this paper, we improve these bounds for k-trees, where k is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed k-trees, and for computation of shortest and longest paths in directed acyclic k-trees. Besides the path problems mentioned above, we also consider the problem of deciding whether a k-tree has a perfect macthing (decision version), and if so, finding a perfect match- ing (search version), and prove that these two problems are L-complete. These problems are known to be in P and in RNC for general graphs, and in SPL for planar bipartite graphs [DKR08]. Our results settle the complexity of these problems for the class of k-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from [JT07] and [LMR07].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Some Tractable Win-Lose Games

Determining a Nash equilibrium in a $2$-player non-zero sum game is known to be PPAD-hard (Chen and Deng (2006), Chen, Deng and Teng (2009)). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane and Valiant (2005)). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta (2006)) and planar games (Addario-Berry, Olver and Vetta (2007)). We extend the results in the latter work to $K_{3,3}$ minor-free games and a subclass of $K_5$ minor-free games. Both these classes of games strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace, a small complexity class contained well within polynomial time. Apart from these classes of games, our results also extend to a class of games that contain both $K_{3,3}$ and $K_5$ as minors, thereby covering a large and non-trivial class of win-lose bimatrix games. For this class, we prove an upper bound of nondeterministic logspace, again a small complexity class within polynomial time. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the logspace complexity class \SPL. Since \SPL\ is contained in the logspace counting classes $\oplusŁ$ (in fact in \modk\ for all $k\geq 2$), \CeqL, and \PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs is in $\FL^{\SPL}$. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a logspace computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function.

0 citations0 reviewsNo code linkedOpen access