Recent Publications.

    Following papers contain most of my research contibutions. Since the copyrights of papers appeared in
    conference proceedings or journals usually belong to the publishers, the papers may be downloaded for
    research purposes only.

    kmerEstimate: A Streaming Algorithm for Estimating k-mer Counts with Optimal Space Usage.
    Sairam Behera, Sutanu Gayen, Jitender S Deogun and N. V. Vinodchandran
    ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB 2018)
    (to appear).

    On Pseudodeterministic Approximation Algorithms.
    P. Dixon, A. Pavan, N. V. Vinodchandran
    Mathematical Foundations of Computer Science (MFCS 2018)
    (to appear).

    New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory.
    Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, Lin F. Yang
    Algorithmica 80(2) (2018): 652-667.

    New Algorithms for Distributed Sliding Windows.
    Sutanu Gayen, N. V. Vinodchandran
    Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) (2018): 22:1-22:15

    Fractal features for automatic detection of dysarthria.
    Taylor Spangler, N. V. Vinodchandran, Ashok Samal, Jordan R. Green
    IEEE Conference on Biomedical and Health Informatics (IEEE BHI 2017) (2017), pages 437-440.

    Computing Triangle and Open-Wedge Heavy-Hitters in Large Networks.
    A. Pavan, P. Quint, S. Scott, N. V. Vinodchandran, and J. Smith
    2016 IEEE International Conference on Big Data (IEEE BigData 2016) (2016), pages 1998-1005.

    Budgeted Testing Through an Algorithmic Lens.
    Myra Cohen, A. Pavan and N. V. Vinodchandran
    Foundations of Software Engineering (FSE) (Visions and Reflections Track) (2016), pages 948-951.

    A Note on the Advice Complexity of Multipass Randomized Logspace.
    Peter Dixon, Debasis Mandal, A. Pavan and N. V. Vinodchandran
    Mathematical Foundations of Computer Science (2016), 31:1-31:7

    Algorithms for k-median clustering over distributed streams.
    Sutanu Gayen and N. V. Vinodchandran.
    International Computing and Combinatorics Conference (COCOON) (2016), 535-546.

    Constrained Group Testing to Predict Binding Response of Candidate Compounds.
    Paul Quint, Stephen Scott, N. V. Vinodchandran, and Brad Worley.
    SIAM International Conference on Data Mining (SDM) (2016), 756-764.

    On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape.
    Debasis Mandal, A. Pavan, and N. V. Vinodchandran.
    Mathematical Foundations of Computer Science (2). (2015), pages 459-471.

    New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory.
    Vladimir Braverman, Zaoxing Liu, Tejasvam Singh, N. V. Vinodchandran, and Lin F. Yang.
    Mathematical Foundations of Computer Science (2) (2015), pages 151-162.

    On Optimal Language Compression for Sets in PSPACE/poly.
    N. V. Vinodchandran and M. Zimand.
    Theory of Computing Systems 56(3): 581-590 (2015).

    New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs.
    Diptarka Chakraborty, A. Pavan, Raghunath Tewari, N. V. Vinodchandran, and Lin Yang.
    Foundations of Software Technology and Theoretical Computer Science (2014), pages 585-595.

    Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs.
    N. V. Vinodchandran.
    Perspective in Computational Complexity -The Somenath Biswas Anniversary Volume, (2014), pages 37-49.
    Progress in Computer Science and Applied Logic (Volume 26).

    ReachFewL = ReachUL.
    B. Garvin, D. Stolee, Raghunath Tewari and N. V. Vinodchandran.
    Computational Complexity, 23: (2014), pages 85 - 98.

    An O({n^{{1\over 2}+\epsilon}}) -Space and Polynomial-Time Algorithm for Directed Planar Reachability.
    T. Imai and K. Nakagawa and A. Pavan and N. V. Vinodchandran and O. Watanabe
    IEEE Conference on Computational Complexity (2013), pages 277-286.

    Space-Efficient Algorithms for Reachability in Surface-Embedded Graphs.
    Derrick Stolee and N. V. Vinodchandran.
    IEEE Conference on Computational Complexity (2013), pages 326-333.

    On the Power of Unambiguity in Logspace.
    A. Pavan, Raghunath Tewari and N. V. Vinodchandran.
    Computational Complexity 21 (4): 643-670 (2012).

    Green's Theorem and Isolation in Planar Graphs.
    Raghunath Tewari and N. V. Vinodchandran.
    Information and Computation 215: 1-7 (2012).

    Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs.
    Samir Datta, Raghav Kulkarni, Raghunath Tewari and N. V. Vinodchandran.
    Journal of Computer and System Sciences 78 (3): 765-779 (2012).

    Kolmogorov Complexity in Randomness Extraction.
    J. Hitchcock, A. Pavan, N. V. Vinodchandran
    ACM Transactions on Computation Theory 3(1): 1 (2011).

    Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws.
    L. Fortnow, J. Hitchcock, A. Pavan, N. V. Vinodchandran, and F. Wang.
    Information and Computation. 209(4), (2011), pages 627-636.

    A Log-space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources.
    Derrick Stolee, Chris Bourke, and N. V. Vinodchandran.
    IEEE Conference on Computational Complexity 2010 pages 131-138.

    Directed Planar Reachability is in Unambiguous Logspace.
    Chris Bourke, Raghunath Tewari, and N. V. Vinodchandran.
    ACM Transactions on Computation Theory 1(1), (2009), pages 1-17.

    2-Local Random Reductions to 3-Valued Functions.
    A. Pavan and N. V. Vinodchandran.
    Computational Complexity 17(4), (2008), pages 501--514.

    Kernels for Generalized Multiple-Instance Learning.
    Qingping Tao, Stephen Scott, N. V. Vinodchandran, Thomas Takeo Osugi, and Brandon Mueller.
    IEEE Transactions on Pattern Analysis and Machine Intelligence 30(12), (2008), pages 2084-2097.

    On Reoptimizing Multi-Class Classifiers.
    Kun Deng, Chris Bourke, Robert Schapire, Stephen Scott, and N. V. Vinodchandran.
    Machine Learning 71(2-3), (2008), pages 219-242.

    Relations between Average-case and Worst-case Complexity.
    A. Pavan and N. V. Vinodchandran.
    Theory of Computing Systems 42(4), (2008), pages 596-607.

    Partial Bi-immunity, Scaled Dimension, and NP-Completeness.
    J. Hitchcock, A. Pavan, and N. V. Vinodchandran.
    Theory of Computing Systems 42(2), (2008), pages 131-142.

    Polylogarithmic-round Interactive Proofs for coNP Collapse the Exponential Hierarchy.
    A. Pavan, A. Selman, S. Sengupta, and N. V. Vinodchandran.
    Theoretical Computer Science 385 (2007) pages 167-178.

    Some Results on Average-Case Hardness within the Polynomial Hierarchy.
    A. Pavan, R. Santhanam, and N. V. Vinodchandran
    Foundations of Software Technology and Theoretical Computer Science (FSTTCS 06).
    LNCS Vol: 4337, pages 188-199.

    Computational Depth: Concept and Applications.
    Luis Antunes, Lance Fortnow, Dieter van Melkebeek, and N. V. Vinodchandran.
    Theoretical Computer Science 354(3), (2006), Pages 391-404
    Special issue devoted to the fourth International Symposium on Fundamentals of Computation Theory.

    Dimension, Entropy Rates, and Compression.
    J. Hitchcock and N. V. Vinodchandran.
    Journal of Computer and System Sciences, 72(4) (2006) pages 760-782.

    A Note on the Circuit Complexity of PP.
    N. V. Vinodchandran.
    Theoretical Computer Science, 347, (2005), pages 415-418.

    Entropy Rates and Finite-State Dimension.
    Chris Bourke, John M. Hitchcock , and N. V. Vinodchandran.
    Theoretical Computer Science, 349 (2005), pages 392-406.

    Nondeterministic Circuit Minimization Problem and Derandomizing Arthur-Merlin Games.
    N. V. Vinodchandran.
    International Journal on Foundations of Computer Science 16(6) (2005), pages 1297-1308.

    Derandomizing Arthur-Merlin games using Hitting Sets.
    Peter Bro Miltersen and N. V. Vinodchandran.
    Computational Complexity, 14 (2005), pages 256-279.

    Learning DNFs and Circuits using Teaching Assistants.
    N. V. Vinodchandran.
    Computing and Combinatorics Conference, 2004 (COCOON 04).
    LNCS Vol: 3106, pages 188-197.

    Counting Complexity of Solvable Black-box Group Problems.
    N. V. Vinodchandran.
    SIAM Journal on Computing, 33(4): 2004 pages 852-869.

    AMexp not Contained in (NP\cap CoNP)/Poly.
    N. V. Vinodchandran.
    Information Processing Letters. 89: 2004, pages 43-47.

    Query Complexity of Program Checking by Constant-Depth Circuits.
    V. Arvind, K. V. Subrahmanyam, and N. V. Vinodchandran.
    Chicago Journal of Theoretical Computer Science, (2002) Article 2.

    Exact Learning via Teaching Assistants.
    V. Arvind and N. V. Vinodchandran.
    Theoretical Computer Science, 241 (2000), pages 51--81.
    Special issue devoted to the Seventh International Workshop on Algorithmic Learning Theory.

    The Complexity of Group-definable NP Languages.
    V. Arvind and N. V. Vinodchandran.
    Theoretical Computer Science, 242 (2000), pages 199--218.

    Superpolynomial versus Subexponential Circuit Size in the Exponential Hierarchy.
    Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe.
    Computing and Combinatorics Conference 1999 (COCOON 99) ,
    LNCS Vol: 1627, pages 210--220.

    Counting Complexity and Computational Group theory.
    N. V. Vinodchandran.
    PhD. Thesis, Institute of Mathematical Sciences, Chennai, India. 1999.

    Solvable Black-Box Group Problems are Low for PP.
    V. Arvind and N. V. Vinodchandran.
    Theoretical Computer Science, 180 (1997), pages 17-47