-
Article
Open AccessHigher emotional granularity relates to greater inferior frontal cortex cortical thickness in healthy, older adults
Individuals with high emotional granularity make fine-grained distinctions between their emotional experiences. To have greater emotional granularity, one must acquire rich conceptual knowledge of emotions and...
-
Article
Depth-first search in directed planar graphs, revisited
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class ...
-
Chapter and Conference Paper
Dynamic Complexity of Expansion
Dynamic Complexity was introduced by Immerman and Patnaik [25] (see also [14]). It has seen a resurgence of interest in the recent past, see [2, 4, 8–12, 24, 26, 30, 31] for some representative examples. Use of l...
-
Chapter and Conference Paper
Randomized and Symmetric Catalytic Computation
A catalytic Turing machine is a model of computation that is created by equip** a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write...
-
Article
Factors that predict diagnostic stability in neurodegenerative dementia
To determine the frequency and characteristics of clinical diagnostic change in frontotemporal dementia (FTD)-spectrum syndromes and Alzheimer’s disease (AD)-type dementia.
-
Chapter and Conference Paper
Reachability is in DynFO
We consider the dynamic complexity of some central graph problems such as Reachability and Matching and linear algebraic problems such as Rank and Inverse. As elementary change operations we allow insertion and d...
-
Chapter and Conference Paper
Bounded Treewidth and Space-Efficient Linear Algebra
Motivated by a recent result of Elberfeld, Jakoby and Tantau [EJT10] showing that \(\mathsf {MSO}\) properties are Lo...
-
Chapter and Conference Paper
Dynamic Complexity of Directed Reachability and Other Problems
We report progress on dynamic complexity of well-known graph problems such as reachability and matching. In this model, edges are dynamically added and deleted and we measure the complexity of each update/quer...
-
Chapter and Conference Paper
Space Complexity of Optimization Problems in Planar Graphs
We initiate the study of space complexity of certain optimization problems restricted to planar graphs. We provide upper bounds and hardness results in space complexity for some of these well-studied problems ...
-
Chapter and Conference Paper
Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
We present improved uniform TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (as studied by Maciel and Thérien). As a coroll...
-
Chapter and Conference Paper
Collapsing Exact Arithmetic Hierarchies
We provide a uniform framework for proving the collapse of the hierarchy \({\sf NC}^1(\mathcal{C})\) for an exact arith...
-
Article
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 (Jakoby and Tantau in Proceedings of FSTTCS’07: The 27th Annual Conference on Found...
-
Chapter and Conference Paper
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.
-
Chapter and Conference Paper
Some Tractable Win-Lose Games
Finding a Nash equilibrium in a bimatrix game is PPAD-hard (Chen and Deng, 2006 [3], Chen, Deng and Teng, 2009 [6]). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane a...
-
Chapter and Conference Paper
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 determi...
-
Chapter and Conference Paper
Verifying Proofs in Constant Depth
In this paper we initiate the study of proof systems where verification of proofs proceeds by \(\protect{\ensuremath{\mathsf{NC}}}^{0}\)
-
Article
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
We present a deterministic Logspace procedure, which, given a bipartite planar graph on n vertices, assigns O(log n) bits long weights to its edges so that the minimum weight perfect matching in the graph becomes...
-
Chapter and Conference Paper
Counting Classes and the Fine Structure between NC 1 and L
The class NC 1of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we...
-
Article
Planar and Grid Graph Reachability Problems
We study the complexity of restricted versions of s-t-connectivity, which is the standard complete problem for \(\mathsf{NL}\) ...
-
Chapter and Conference Paper
Planarity, Determinants, Permanents, and (Unique) Matchings
We explore the restrictiveness of planarity on the complexity of computing the determinant and the permanent, and show that both problems remain as hard as in the general case, i.e. GapL and #P complete. On the o...
