16 citations · 42 across the 21 of their papers we have counts for
3 papers · 1 filter
Resource-bounded Dimension in Computational Learning Theory
Ricard Gavalda, Maria Lopez-Valdes, Elvira Mayordomo +1
This paper focuses on the relation between computational learning theory and resource-bounded dimension. We intend to establish close connections between the learnability/nonlearna…
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs
Samir Datta, Raghav Kulkarni, Raghunath Tewari +1
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 t…
On the Power of Unambiguity in Logspace
Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\Reach…