#### Research Publications/Reports

Listing All publications. View/Hide Filter**Lower Bounds for Multilinear Order-restricted ABPs**Ramya C., Raghavendra Rao B V, To Appear in

*44th International Symposium on Mathematical Foundations of Computer Science*, MFCS 2019, Sep 2019.**On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models**Purnata Ghosal, Raghavendra Rao B V, To Appear in

*25th International Computing and Combinatorics Conference*, COCOON 2019, Aug 2019.**Fully Dynamic Data Structures for Interval Coloring**Girish Raguvir, Manas Jyothi Kashyap, Narayanaswamy N S, To Appear in

*25th International Computing and Combinatorics Conference (COCOON 2019)*, Aug 2019.**Attribute Based Encryption (and more) for Nondeterministic Finite Automata from Learning With Errors**Shweta Agrawal, Monosij Maitra, Shota Yamada, To Appear in

*38th Annual International Cryptology Conference (CRYPTO 2019)*, Aug 2019.**Sensitivity, Affine Transforms and Quantum Communication Complexity**Krishnamoorthy Dinesh, Jayalal Sarma, To Appear in

*25th International Computing and Combinatorics Conference (COCOON 2019)*, Vol 2018, No.152, Aug 2019.**Linear projections of the Vandermonde polynomial**Ramya C., Raghavendra Rao B V, Appeared in

*TCS*, Theoretical Computer Science, Jul 2019.**Space Complexity of Labelled Graph Reachability Problem**Vidhya Ramaswamy, Jayalal Sarma, K.S. Sunil, Appeared in

*Journal of Computer and System Sciences*, Jun 2019. A preliminary version appeared in 11th International Conference on Language and Automata Theory and Applications (LATA 2017), Mar 2017.**Lower bounds for Sum and Sum of Products of Read-once Formulas**Ramya C., Raghavendra Rao B V, Appeared in

*ToCT*, ACM Transactions on Computation Theory, Vol 11, No.2, pp.10:1-10:27, May 2019. A preliminary version under the title "Sum of products of Read-Once Polynomials" appeared in 36th International Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2016.**Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness**Meghana Nasre, Prajakta Nimbhorkar, Nada Abdul Majeed Pulath, Appeared in

*45th International Workshop on Graph-Theoretic Concepts in Computer Science*, May 2019.**Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and Instantiation.**Shweta Agrawal, Appeared in

*38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2019)*, May 2019.**Characterization and Lower Bounds for Branching Program Size using Projective Dimension**Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory*, Vol 11, No.8, Mar 2019. A preliminary version appeared in 36th International Conference on Foundations of Software Technology and Theoretical Computer Science, Dec 2016.**Alternation, Sparsity and Sensitivity : Combinatorial Bounds and Exponential Gaps**Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in

*Theoretical Computer Science*, Mar 2019. A preliminary version appeared in 4th Annual Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2018), Feb 2018.**Functional Encryption and Indistinguishability Obfuscation for Turing Machines from minimal assumptions.**Shweta Agrawal, Monosij Maitra, Appeared in

*The 16th Theory of Cryptography Conference (TCC 2018)*, Dec 2018.**A Two-Sided Error Distributed Property Tester For Conductance**Yadu Vasudev, Hendrik Fichtenberger, Appeared in

*43rd International Symposium on Mathematical Foundations of Computer Science (MFCS)*, Aug 2018.**Comparator Circuits over Finite Bounded Posets**Balagopal Komarath, Jayalal Sarma, Sunil K.S., Appeared in

*Information & Computation*, (Special Issue for Selected Papers from ICALP 2015), Vol 261, No.2, pp.160-174, Aug 2018. A preliminary version appeared in Proceedings of International Conference on Automata, Languages and Programming (ICALP), Jul 2015.**Sublinear Message Bounds for Randomized Agreement**John Augustine, Anisur Rahaman Molla, Gopal Pandurangan, Appeared in

*Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC 2018)*, Jul 2018.**Minimum Membership Hitting Sets of Axis Parallel Segments**Narayanaswamy N S, Dhannya S.M., Ramya C., Appeared in

*The 24th International Computing and Combinatorics Conference (COCOON 2018)*, LNCS, Jul 2018.**A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error**Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, Maximilian Woetzel, Appeared in

*ICALP*, he 45th International Colloquium on Automata, Languages, and Programming (ICALP), Jul 2018.**Lower Bounds for Special Classes of Syntactic Multilinear ABPs**Ramya C., Raghavendra Rao B V, Appeared in

*The 24th International Computing and Combinatorics Conference (COCOON 2018)*, Jul 2018.**New Bounds for Energy Complexity of Boolean Functions**Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma, Appeared in

*The 24th International Computing and Combinatorics Conference (COCOON 2018)*, Jul 2018.**Wiretap Polar Codes in Encryption Schemes Based on Learning with Errors Problem**Aswin Rajagopalan, Andrew Thangaraj, Shweta Agrawal, Appeared in

*Proceedings of IEEE International Symposium of Information Theory (ISIT), 2018.*, Jun 2018.**How good are popular matchings?**Krishnapriya A M, Meghana Nasre, Prajakta Nimbhorkar, Amit Rawat, Appeared in

*17th International Symposium on Experimental Algorithms (SEA 2018)*, Jun 2018.**Facility location on planar graphs with unreliable links**Narayanaswamy N S, Meghana Nasre, Vijayaraghunathan Ramamoorthi, Appeared in

*The 13th International Computer Science Symposium in Russia*, Jun 2018.**Spartan: A Framework For Sparse Robust Addressable Networks**John Augustine, Sumathi S., Appeared in

*IEEE International Parallel & Distributed Processing Symposium (IPDPS 2018)*, May 2018.**Pebbling Meets Coloring: Reversible Pebble Game On Trees**Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani, Appeared in

*Journal of Computer and System Sciences*, Vol 91, pp.33-41, Feb 2018. A preliminary version under the title "Reversible Pebble Game on Trees" appeared in 21st International Computing and Combinatorics Conference (COCOON 2015), Aug 2015.**Popular Matchings with Lower Quotas**Meghana Nasre, Prajakta Nimbhorkar, Appeared in

*37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)*, Dec 2017.**Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs**John Augustine, William Kumar Moses Jr., Appeared in

*International Conference on Distributed Computing and Networking (ICDCN 2018)*, Nov 2017.**Deterministic Dispersion of Mobile Robots in Dynamic Rings.**Ankush Agarwalla, John Augustine, William Kumar Moses Jr., Madhav Shankar K., Arvind Krishna Sridhar, Appeared in

*International Conference on Distributed Computing and Networking (ICDCN 2018)*, Nov 2017.**Functional Encryption for Bounded Collusions, Revisited**Shweta Agrawal, Alon Rosen, Appeared in

*Fifteenth IACR Theory of Cryptography Conference - TCC 2017*, Nov 2017.**Efficient Public Trace-and-Revoke from Standard Assumptions**Shweta Agrawal, Sanjay Bhattacherjee, Duong Hieu Phan, Damien Stehlé, Shota Yamada, Appeared in

*ACM Conference on Computer and Communications Security (CCS)*, Oct 2017.**On Weak-Space Complexity over Complex Numbers**Pushkar Joglekar, Siddhartha Sivakumar, Raghavendra Rao B V, Appeared in

*21st International Symposium on Fundamentals of Computation Theory (FCT 2017)*, Sep 2017.**On depth five Sum-Power-Sum-Power-Sum Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree**Christian Engels, Raghavendra Rao B V, Karteek Sreenivasaiah, Appeared in

*21st International Symposium on Fundamentals of Computation Theory (FCT 2017)*, Sep 2017.**Testing Equivalence of Polynomials under Scaling**Markus Blaser, Raghavendra Rao B V, Jayalal Sarma, Appeared in

*21st International Symposium on Fundamentals of Computation Theory (FCT)*, Sep 2017.**Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph**Venkat Guruswami, Ameya Veligker, Santhoshini V, Appeared in

*20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2017)*, Sep 2017.**On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction**Purnata Ghosal, Om Prakash, Raghavendra Rao B V, Appeared in

*23rd Annual International Computing and Combinatorics Conference (COCOON 2017)*, Aug 2017.**Interpolating Predicate and Functional Encryption from Learning With Errors**Shweta Agrawal, Appeared in

*37th International Cryptology Conference (CRYPTO 2017)*, Aug 2017.**The Price of Selection in Differential Privacy**Mitali Bafna, Jonathan Ullman, Appeared in

*30th Annual Conference on Learning Theory (COLT 2017)*, Jul 2017.**Reusable Garbled Deterministic Finite Automata from Learning With Errors**Shweta Agrawal, Ishaan Preet Singh, Appeared in

*The 44th International Colloquium on Automata, Languages, and Programming (ICALP)*, Jul 2017.**Popularity in the generalized Hospital Residents setting**Meghana Nasre, Amit Rawat, Appeared in

*The 12th International Computer Science Symposium in Russia (CSR 2017)*, Jun 2017.**Min/Max-Poly Weighting Schemes and the NL vs UL Problem**Anant Dhayal, Jayalal Sarma, Saurabh Sawlani, Appeared in

*ACM Transactions on Computation Theory*, Vol 9, No.10, May 2017. A preliminary version under the title "Polynomial Min/Max-weighted Reachability is in Unambiguous Logspace" appeared in Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2014), Dec 2014.**Information Spreading in Dynamic Networks under Oblivious Adversaries**John Augustine, Chen Avin, Mehraneh Liaee, Gopal Pandurangan, Rajmohan Rajaraman, Appeared in

*International Symposium on Distributed Computing (DISC 2016)*, Sep 2016.**Hitting Set for hypergraphs of low VC-dimension**Karl Bringmann, Laszlo Kozma, Shay Moran, Narayanaswamy N S, Appeared in

*ESA*, European Symposium on Algorithms, Sep 2016.**A Refined Analysis of Online Path Coloring in Trees**Astha Chauhan, Narayanaswamy N S, Appeared in

*Workshop on Approximation and Online Algorithms*, Aug 2016.**On the Sensitivity Conjecture for Read-k Formulas**Mitali Bafna, Satyanarayana Lokam, Sebastian Tavenas, Ameya Velingker, Appeared in

*41st International Symposium on Mathematical Foundations of Computer Science (MFCS)*, Aug 2016.**On the Complexity Landscape of Connected f-factor Problems**Robert Ganian, Narayanaswamy N S, Sebastian Ordyniak, Rahul C.S., M S Ramanujan, Appeared in

*41st International Symposium on Mathematical Foundations of Computer Science (MFCS)*, Aug 2016.**On Hard Instances of Non-Commutative Permanent**Raghavendra Rao B V, Christian Engels, Appeared in

*22nd International Computing and Combinatorics Conference (COCOON 2016)*, Aug 2016.**Sub-families of Baxter Permutations Based on Pattern Avoidance**Shankar Balachandran, Sajin Koroth, Appeared in

*The 11th International Computer Science Symposium in Russia (CSR 2016)*, Jun 2016.**Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices**Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory (To Appear)*, Apr 2016. A preliminary version under the title "Arithmetic Circuit Lower Bounds via MaxRank" appeared in 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), Lecture Notes in Computer Science, Vol 7965, pp.661-672, Jul 2013.**Distributed Algorithmic Foundations of Dynamic Networks**John Augustine, Gopal Pandurangan, Peter Robinson, Appeared in

*SIGACT News*, Vol 47, No.1, pp.69-98, Mar 2016.**On the Complexity of L-reachability**Balagopal Komarath, Jayalal Sarma, K.S. Sunil, Appeared in

*Fundamenta Informaticae*, Mar 2016. A preliminary version appeared in 16th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2014), Lecture Notes in Computer Science, Vol 8614, pp.258-269, Aug 2014.**Balanced Allocation: Patience is not a virtue**John Augustine, William Kumar Moses Jr., Amanda Redlich, Eli Upfal, Appeared in

*27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)*, Jan 2016.**Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks**John Augustine, Gopal Pandurangan, Peter Robinson, Scott Roche, Eli Upfal, Appeared in

*56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)*, Oct 2015.**Minimax regret 1-sink location problem in dynamic path networks**John Augustine, Yuya Higashikawa, Siu-Wing Cheng, Mordecai J. Golin, Naoki Katoh, Guanqun Ni, Bing Su, Yin-Feng Xu, Appeared in

*Theoretical Computer Science*, . Comput. Sci. 588: 24-36 (2015) 2013, Vol 588, No.2013, pp.24-36, Jul 2015.**Approximation and Exact Algorithms for special cases of Connected f-Factors**Narayanaswamy N S, Rahul C.S., Appeared in

*10th International Computer Science Symposium in Russia*, Jul 2015.**Leader Election in Sparse Dynamic Networks with Churn.**John Augustine, Tejas Kulkarni, Sumathi S., Appeared in

*IEEE International Parallel & Distributed Processing Symposium (IPDPS)*, May 2015.**Block Sorting is APX-Hard**Narayanaswamy N S, Swapneel Roy, Appeared in

*The 9th International Conference on Algorithms and Complexity*, May 2015.**Enforcing Efficient Equilibria in Network Design Games via Subsidies**John Augustine, Ioannis Caragiannis, Angelo Fanelli, Christos Kalaitzis, Appeared in

*Algorithmica*, Vol 72, No.1, pp.44--82, May 2015. A preliminary version under the title "Enforcing efﬁcient equilibria in cost sharing games via subsidies" appeared in Proceedings of the Symposium on Parallelism in Algorithms and Architectures (2012), Jun 2012.**Distributed agreement in dynamic peer-to-peer networks**John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal, Appeared in

*Journal of Computer and System Sciences (JCSS)*, Vol 81, No.7, pp.1088-1109, Feb 2015.**Block Sorting is APX-Hard**Narayanaswamy N S, Swapnoneel Roy, Appeared in

*International Conference on Algorithms and Complexity 2015*, Feb 2015.**Approximate Distance Oracle in O(n^2) Time and O(n) Space for Chordal Graphs**Gaurav Singh, Narayanaswamy N S, Ramakrishna G., Appeared in

*Workshop on Algorithms and Computation*, Feb 2015.**Parameterized Analogues of Probabilistic Computation**Ankit Chauhan, Raghavendra Rao B V, Appeared in

*Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015)*, Feb 2015.**Tree Path Labeling of Hypergraphs – A Generalization of the Consecutive Ones Property**Narayanaswamy N S, Anju Srinivasan, Appeared in

*Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2015)*, Feb 2015.**Dynamic Profit Sharing Games**John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry Shiryaev, Appeared in

*Internet Mathematics*, Vol 11, No.1, pp.1-22, Jan 2015.**Rank Maximal Matchings -- Structure and Algorithms.**Pratik Ghoshal, Meghana Nasre, Prajakta Nimbhorkar, Appeared in

*Accepted for publication at the 25th International Symposium on Algorithms and Computation*, Dec 2014.**Decremenal ALL-Pairs ALL Shortest Paths and Betweenness Centrality.**Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran, Appeared in

*Accepted for publication at the 25th International Symposium on Algorithms and Computation*, Dec 2014.**Pebbling, Entropy and Branching Program Size Lower Bounds**Balagopal Komarath, Jayalal Sarma, Appeared in

*ACM Transactions on Computation Theory*, Dec 2014. A preliminary version appeared in 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics, Vol 20, pp.622-633, Feb 2013.**Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems**Karl Bringmann, Christian Engels, Bodo Manthey, Raghavendra Rao B V, Appeared in

*Algorithmica*, (To Appear), Dec 2014. A preliminary version appeared in 38th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2013.**On Minimum Average Stretch Spanning Trees in Polygonal 2-trees**Narayanaswamy N S, Ramakrishna G., Appeared in

*Accepted at Theoretical Computer Scince 2014*, Nov 2014.**Tree t-spanners in Outerplanar Graphs via Supply Demand Partition**Narayanaswamy N S, Ramakrishna G., Appeared in

*Accepted at Discrete Applied Mathematics 2014*, Oct 2014.**LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs**Samuel Fiorini, Krithika Ramaswamy, Narayanaswamy N S, Venkatesh Raman, Appeared in

*22nd European Symposium on Algorithms*, Sep 2014.**Betweenness centrality -- Incremental and faster**Meghana Nasre, Matteo Pontecorvi, Vijaya Ramachandran, Appeared in

*39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)*, Aug 2014.**Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth**Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, Navid Talebanfard, Appeared in

*39th International Symposium on Mathematical Foundations of Computer Science (MFCS 2014)*, Lecture Notes in Computer Science, Vol 8634, pp.336-347, Aug 2014.**Building above read-once polynomials: identity testing and hardness of representation.**Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah, Appeared in

*The 20th Annual International Computing and Combinatorics Conference COCOON, 4-6 Aug 2014, Atlanta, USA.*, Aug 2014.**Depth Lower bounds against Circuits with Sparse Orientation**Sajin Koroth, Jayalal Sarma, Appeared in

*Proceedings of the 20th International Computing and Combinatorics Conference (COCOON 2014)*, Lecture Notes in Computer Science, Vol 8591, pp.596-607, Aug 2014.**Complexity of Testing Reachability in Matroids**Raghavendra Rao B V, Jayalal Sarma, Appeared in

*Chicago Journal of Theoretical Computer Science*, Vol 2014, No.5, Jul 2014.**Connected f-Factors of Large Minimum Degree in Polynomial Time.**Narayanaswamy N S, Rahul C.S., Appeared in

*9th International Colloquium on Graph Theory and Combinatorics (ICGT 2014)*, Jul 2014.**Approximation Algorithms for Hitting Triangle-Free Sets of Line Segments**Narayanaswamy N S, Anup Joshi, Appeared in

*Accepted at 14th Scandinavian Symposium and Workshops on Algorithm Theory(SWAT 2014) - Copenhagen, Denmark*, Jul 2014.**FPT results for obtaining COP by Row Deletion and related problems**Narayanaswamy N S, Subashini R., Appeared in

*Accepted at Algorithmica*, Jun 2014.**Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time**Carola Doerr, Ramakrishna G., Jens M. Schmidt, Appeared in

*Accepted at Journal of Graph Algorithms and Applications (JGAA)*, May 2014.**Asynchronous Byzantine Agreement with Optimal Resilience**Arpita Patra, Ashish Choudhary, C. Pandu Rangan, Appeared in

*Distributed Computing*, Vol 27, No.2, pp.111-146, Apr 2014.**Characterization of Minimum Cycle Basis in Weighted Partial 2-trees.**Narayanaswamy N S, Ramakrishna G., Appeared in

*Accepted at Discrete Applied Mathematics, CoRR abs/1302.5889 (2013)*, Apr 2014. A preliminary version under the title "Characterization of Minimum Cycle Basis in Weighted Partial 2-trees" appeared in Cologne-Twente Workshop (CTW), May 2012.**Balancing Bounded Treewidth Circuits**Maurice Jansen, Jayalal Sarma, Appeared in

*Theory of Computing Systems*, Vol 54, No.2, pp.318-336, Jan 2014. A preliminary version appeared in 5th International Computer Science Symposium in Russia (CSR 2010), Vol 6072, pp.228-239, Jun 2010.**Monomials, multilinearity and identity testing in simple read-restricted circuits**Meena Mahajan, Raghavendra Rao B V, Karteek Sreenivasaiah, Appeared in

*Theoretical Computer Science*, 2014. A preliminary version under the title "Monomials in read once/twice formulas and branching programs" appeared in Mathematical Foundations of Computer Science (MFCS), 2012.**Another Disjoint Compression Algorithm for OCT**Narayanaswamy N S, Krithika Ramaswamy, Appeared in

*Information Processing Letters.*, Vol 113, No.22, pp.849–851, Nov 2013.**Anonymous Identity-Based Identification Scheme in Ad-Hoc Groups without Pairings**Prateek Barapatre, C. Pandu Rangan, Appeared in

*Security, Privacy, and Applied Cryptography Engineering - Third International Conference (SPACE 2013)*, Oct 2013.**Identity-Based Identification Schemes from ID-KEMs**Prateek Barapatre, C. Pandu Rangan, Appeared in

*Security, Privacy, and Applied Cryptography Engineering - Third International Conference (SPACE 2013)*, Oct 2013.**On Minimum Average Stretch Spanning Trees in Polygonal 2-trees**Narayanaswamy N S, Ramakrishna G., Appeared in

*Accepted at Workshop on Algorithms and Computation 2014*, Oct 2013.**Robust Leader Election in Fast Changing World**John Augustine, Tejas Kulkarni, Paresh Ashok Nakhe, Peter Robinson, Appeared in

*9th International Workshop on Foundations of Mobile Computing (FOMC)*, Oct 2013.**Approximability of Connected Factors**Kamiel Cornelissen, Ruben Hoeksma, Bodo Manthey, Narayanaswamy N S, Rahul C.S., Appeared in

*11th Workshop on Approximation and Online Algorithms (WAOA)*, Sep 2013.**FPT algorithms for Consecutive Ones Submatrix problems**Narayanaswamy N S, Subashini R., Appeared in

*8th International Symposium on Parameterized and Exact Computation (IPEC)*, Springer series Lecture Notes in Computer Science, Sep 2013.**Faster Parameterized Algorithms using Linear Programming**Daniel Lokshtanov, Narayanaswamy N S, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh, Appeared in

*Accepted at the ACM Transactions on Algorithms*, Sep 2013.**Computing Minimum Cycle Bases in Weighted Partial 2-Trees in Linear Time**Carola Doerr, Ramakrishna G., Jens M. Schmidt, Appeared in

*39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013)*, Aug 2013.**Small space analogues of Valiants classes**Meena Mahajan, Raghavendra Rao B V, Appeared in

*Computational Complexity*, Jul 2013. A preliminary version appeared in Foundations of Computation Theory, FCT, Jul 2009.**Smoothed Analysis of Partitioning Algorithms for Euclidean Functionals**Markus Blaeser, Bodo Manthey, Raghavendra Rao B V, Appeared in

*Algorithmica*, Vol 66, No.2, pp.397-418, Jul 2013. A preliminary version appeared in WADS Symposium, Jul 2011.**Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits**Maurice Jansen, Meena Mahajan, Raghavendra Rao B V, Appeared in

*Computational Complexity*, Jul 2013. A preliminary version under the title "Arithmetic circuits, syntactic multilinearity, and the limitations of skew formulae" appeared in Mathematical Foundations of Computer Science (MFCS), MFCS, Jul 2008.**Solving minones-2-sat as Fast as vertex cover**Narayanaswamy N S, Neeldhara Misra, Venkatesh Raman, Bal Sri Shankar, Appeared in

*Accepted at Theoretical Computer Science*, Jul 2013. A preliminary version appeared in Proceedings of International Conference on Mathematical Foundations of Computer Science (MFCS 2010), Lecture Notes in Computer Science, Vol 6289, pp.549-5555, Aug 2010.**Storage and Search in Dynamic Peer-to-Peer Networks**John Augustine, Anisur Rahaman Molla, Ehab Morsy, Gopal Pandurangan, Peter Robinson, Eli Upfal, Appeared in

*25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013)*, Jul 2013.**Fast Byzantine Agreement in Dynamic Networks**John Augustine, Gopal Pandurangan, Peter Robinson, Appeared in

*ACM Symposium on Principles of Distributed Computing (PODC 2013)*, Jul 2013.**A Dirac-type Characterization of k-chordal Graphs**Krithika Ramaswamy, Rogers Mathew, Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*Accepted at Discrete Mathematics*, Jul 2013.**d-COS-R is FPT via Interval Deletion**Narayanaswamy N S, Subashini R., Appeared in

*Arxiv*, Feb 2013.**On Directed Tree Realizations of Degree Sets**Prasun Kumar, Jayalal Sarma, Saurabh Sawlani, Appeared in

*Accepted to International Workshop on Algorithms and Computations (WALCOM 2013)*, Lecture Notes in Computer Science, Vol 7748, pp.274--285, Feb 2013.**Parameterized Algorithms for (r,l)-Partization**Narayanaswamy N S, Krithika Ramaswamy, Appeared in

*Journal of Graph Algorithms and Applications (JGAA)*, Vol 17, No.2, pp.129--146, Jan 2013. A preliminary version under the title "Generalized Above Guarantee Vertex Cover and r-Partization" appeared in 6th International Workshop on Algorithms and Computation (WALCOM 2012), Lecture Notes in Computer Science, Vol 7157, pp.1727, Feb 2012.**A Unified Framework for Bi(Tri)connectivity and Chordal Augmentation**Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*International Journal of Foundations of Computer Science*, Vol 24, No.1, pp.67–93, Jan 2013.**Control Words of Transition P Systems.**Ajeesh Ramanujan, Kamala Krithivasan, Appeared in

*Seventh International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2012)*, Advances in Intelligent Systems and Computing, Vol 1, pp.145--155, Dec 2012.**Density Functions subject to a Co-Matroid Constraint**Venkatesan Chakaravarthy, Natwar Modani, Sivaramakrishnan N.R., Sambuddha Roy, Yogish Sabarwal, Appeared in

*Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)*, Dec 2012.**On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission**Ashwinkumar B.V., Arpita Patra, Ashish Choudhary, Kannan Srinathan, C. Pandu Rangan, Appeared in

*Journal of the Association of Computing Machinery (JACM)*, Vol 59, No.5, pp.22, Sep 2012.**Localized Geometric Query Problems**John Augustine, Sandip Das, Anil Maheswari, Subhas Nandy, Sasanka Roy, Appeared in

*Computational Geometry - Theory and Application*, Aug 2012.**Cache Me If You Can: Capacitated Selfish Replication Games.**Raghavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram, Appeared in

*10th Latin American Symposium on Theoretical Informatics (LATIN 2012)*, Lecture Notes in Computer Science, Vol 7256, pp.420-432, Aug 2012.**A Code-Based 1-out-of-N Oblivious Transfer Based on McEliece Assumptions**Preetha Mathew K, Sachin Vasant, Sridhar Venkatesan, C. Pandu Rangan, Appeared in

*8th International Conference on Information Security Practice and Experience (ISPEC 2012)*, Lecture Notes in Computer Science, Vol 7232, pp.144-157, Aug 2012.**Probabilistic Analysis of Christofides Algorithm.**Markus Blaeser, Konstantinos Panagiotou, Raghavendra Rao B V, Appeared in

*Scandinavian Symposium on Algorithm Theory (SWAT)*, SWAT, Jul 2012.**Faster Algorithms for Finding and Counting Subgraphs.**Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Raghavendra Rao B V, Saket Saurabh, Appeared in

*Journal of Computer and System Sciences*, Vol 78, pp.698-706, Jul 2012.**Counting classes and the fine structure between NC^1 and L**Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer, Appeared in

*Theoretical Computer Science*, TCS, Vol 417, pp.36-49, Jul 2012. A preliminary version under the title "Counting Classes and the Fine Structure between NC^1 and L" appeared in Mathematical Foundations of Computer Science (MFCS), MFCS, Jul 2010.**An Efficient IND-CCA2 Secure Variant of the Niederreiter Encryption Scheme in the Standard Model**Preetha Mathew K, Sachin Vasant, Sridhar Venkatesan, C. Pandu Rangan, Appeared in

*17th Australasian Conference on Information Security and Privacy (ACISP 2012)*, Lecture Notes in Computer Science, Vol 7372, pp.166-179, Jul 2012.**Using Elimination Theory to Construct Rigid Matrices**Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma, Appeared in

*Computational Complexity (accepted)*, Jul 2012. A preliminary version under the title "Using Elimination Theory to construct Rigid Matrices" appeared in Proceedings of Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), Vol 4, pp.299-310, Dec 2009.**On Isomorphism Testing of Groups with Normal Hall Subgroups**Youming Qiao, Jayalal Sarma, Bangsheng Tang, Appeared in

*Journal of Computer Science and Technology (JCST)*, Special Issue on Theoretical Computer Science (by invitation), Vol 27, No.4, pp.687-701, Jul 2012. A preliminary version appeared in Proceedings of 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Vol 9, pp.567-578, Mar 2011.**Faster Parameterized Algorithms for Deletion to Split Graphs**Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Mishra, Fahad Panolan, Ashuthosh Rai, M. S. Ramanujan, Appeared in

*13th Scandinavian Symposium and Workshops on Algorithm Theory - SWAT 2012*, Lecture Notes in Computer Science, Vol 7357, pp.107--118, Jul 2012.**Optimal Parameters for Efficient Two-Party Computation Protocols**Chaya Ganesh, C. Pandu Rangan, Appeared in

*International Workshop on Information Security Theory and Practice (WISTP 2012)*, Lecture Notes in Computer Science, Vol 7332, pp.128--143, Jun 2012.**LP can be a cure for Parameterized Problems**Narayanaswamy N S, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh, Appeared in

*29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012*, LIPIcs Schloss Dagstuhl, Vol 14, pp.338-349, Feb 2012.**Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks**John Augustine, Gopal Pandurangan, Peter Robinson, Eli Upfal, Appeared in

*Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)*, Jan 2012.**Isomorphism Testing of Read-once Functions and Polynomials**Raghavendra Rao B V, Jayalal Sarma, Appeared in

*Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)*, LIPIcs–Leibniz International Proceedings in Informatics, Vol 13, pp.115-126, Dec 2011.**On the Complexity of Connected (s, t)-Vertex Separator**Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*Arxiv*, Nov 2011.**On the Complexity of Matroid Isomorphism Problem**Raghavendra Rao B V, Jayalal Sarma, Appeared in

*Theory of Computing Systems*, Vol 49, No.2, pp.246-272, Aug 2011. A preliminary version appeared in Proceedings of the 4th Computer Science Symposium in Russia (CSR 2009), Vol 5675, pp.286-298, Aug 2009.**Hardness of subgraph and supergraph problems in c-tournaments**S. Kanthi Kiran, Narayanaswamy N S, Appeared in

*Theoretical Computer Science*, Vol 412, No.35, pp.4629-4635, Aug 2011.**Dominating Set Based Exact Algorithms for 3-coloring**Narayanaswamy N S, C.R. Subramanian, Appeared in

*Information Processing Letters*, Vol 111, No.6, pp.251-255, Jul 2011.**Tree Insertion Systems**Kamala Krithivasan, Sunil K.S., Appeared in

*The 2011 International Conference on Foundations of Computer Science (FCS 2011)*, Jun 2011.**A New Approach to Threshold Attribute Based Signatures**Sharmila Deva Selvi S., Subhashini Venugopalan, C. Pandu Rangan, Appeared in

*Manuscript*, Jun 2011.**A Characterization of all Stable Minimal Separator Graphs**Mrinal Kumar, Gaurav Maheshwari, Sadagopan Narasimhan, Appeared in

*Accepted for Poster Presentation in European Conference on Combinatorics, Graph Theory and Applications (EURO- COMB 2011)*, Jun 2011.**A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs**Esha Ghosh, Narayanaswamy N S, C. Pandu Rangan, Appeared in

*5th International Workshop on Algorithms and Computation (WALCOM 2011)*, Lecture Notes in Computer Science, Vol 6552, pp.191-201, Feb 2011.**A Novel Data Structure for Biconnectivity, Triconnectivity, and k-tree Augmentation.**Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*Perth, Australia*, In Proc. Computing: The Australasian Theory Symposium, ACS, CRPIT, Vol 119, pp.45-54, Jan 2011.**On String Languages Generated by Spiking Neural P Systems with Anti-Spikes**Kamala Krithivasan, Padma Metta, Deepak Garg, Appeared in

*International Journal of Foundations of Computer Science*, Vol 22, No.1, pp.15--27, Jan 2011.**A Unified Framework for Bi(Tri)connectivity and Chordal Augmentation**Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*International Journal of Foundations of Computer Science*, 2011.**Deterministic BlackBox Identity Testing Pi-ordered Algebraic Branching Programs**Maurice Jansen, Youming Qiao, Jayalal Sarma, Appeared in

*Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)*, Vol 8, pp.296-307, Dec 2010.**Limiting Negations in Bounded Treewidth and Upward Planar Circuits**Jing He, Hongyu Liang, Jayalal Sarma, Appeared in

*35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010)*, Lecture Notes in Computer Science, Vol 6281, pp.417-428, Aug 2010.**Arithmetizing Classes around NC1 and L**Meena Mahajan, Nutan Limaye, Raghavendra Rao B V, Appeared in

*Theory of Computing Systems*, Vol 46, No.3, pp.499-522, Jul 2010. A preliminary version appeared in Symposium on Theoretical Aspects of Computer Science, STACS, Mar 2007.**Deterministic Polynomial Identity Testing of Read-once Algebraic Branching Programs**Maurice Jansen, Youming Qiao, Jayalal Sarma, Appeared in

*Manuscript*, Jun 2010.**Size-Efficient Multi-level Threshold Attribute Based Encryption**Subhashini Venugopalan, C. Pandu Rangan, Appeared in

*Manuscript*, Jun 2010.**Non-contractible non-edges in 2-connected graphs**Anita Das, Mathew C. Francis, Rogers Mathew, Sadagopan Narasimhan, Appeared in

*Information Processing Letters*, Vol 110, No.23, pp.1044--1048, Jun 2010.**On the Complexity of Rank and Rigidity**Meena Mahajan, Jayalal Sarma, Appeared in

*Theory of Computing Systems*, Special issue (by invitation), Vol 46, No.1, pp.9--26, Jan 2010. A preliminary version appeared in Proceedings of the 2nd International Computer Science Symposium in Russia (CSR 2007), Vol 4649, pp.269--280, Aug 2007.**TRANS: Schema-Aware Mapping of OWL Ontologies into Relational Databases**Narayanaswamy N S, Saurabh Kejriwal, Appeared in

*Mysore, India*, In the 15th International Conference on Management of Data (COMAD), Dec 2009.**Modeling Spiking Neural P Systems using Timed Petri Nets**Padma Metta, Kamala Krithivasan, Deepak Garg, Appeared in

*World Congress on Nature & Biologically Inspired Computing*, pp.25--30, Dec 2009.**A New Characterization of Matrices with the Consecutive Ones Property**Narayanaswamy N S, Subashini R., Appeared in

*Discrete Applied Mathematics*, Vol 157, No.18, pp.3721-3727, Nov 2009.**Upper Bounds for Monotone Planar Circuit Value and Variants**Nutan Limaye, Meena Mahajan, Jayalal Sarma, Appeared in

*Computational Complexity*, Vol 18, No.3, pp.377--412, Oct 2009. A preliminary version under the title "Evaluating Monotone Circuits on Cylinders, Planes and Tori" appeared in Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, Vol 3884, pp.660-671, Feb 2006.**On the Relative Expressive Power of Contextual Grammars with Maximal and Depth-First Derivations.**Lakshman Kuppusamy, Kamala Krithivasan, Appeared in

*6th International Colloquium on Theoretical Aspects of Computing (ICTAC)*, Lecture Notes in Computer Science, Vol 5684, pp.246-260, Aug 2009.**Simulation of Arithmetical Circuits by Branching Programs Preserving Constant Width and Syntactic Multilinearity**Maurice Jansen, Raghavendra Rao B V, Appeared in

*Symposium on Computer Science in Russia (CSR)*, CSR, Jul 2009.**On the Structure of Contractible Edges in k-connected Partial k-trees**Narayanaswamy N S, Sadagopan Narasimhan, Sunil Chandran L., Appeared in

*Graphs and Combinatorics*, Vol 25, No.4, pp.557--569, Jul 2009.**Tuning Search Heuristics for Classical Planning with Macro Actions**Narayanaswamy N S, I. Murugeswari, Appeared in

*Florida*, In the 22nd International FLAIRS Conferences, May 2009.**On the Structure of Contractible Vertex Pairs in Chordal Graphs**Narayanaswamy N S, Sadagopan Narasimhan, Appeared in

*Electronic notes in Discrete Mathematics*, (Selected papers from International Conference on Graph Theory and its Applications), Vol 33, pp.29--36, Apr 2009.**Analysis of Online Algorithms for the Dynamic Convoy Movement Problem**Narayanaswamy N S, Ram Gopalan, Appeared in

*Journal of the Operational Research Society*, Vol 60, pp.1230-1236, Jan 2009.**Cuts and Connectivity in Chordal Graphs**Narayanaswamy N S, L. Sunil Chandran, Appeared in

*Ars Combinatoria*, Vol 92, 2009.**Complexity Theoretic Aspects of Matrix Rank, Rigidity and Circuit Value**Jayalal Sarma, Appeared in

*PhD Thesis*, Sep 2008.**Rigidity of a Simple Extended Lower Triangular Matrix**Meena Mahajan, Jayalal Sarma, Appeared in

*Information Processing Letters*, Vol 107, No.5, pp.147--153, Aug 2008.**Graph Splicing Systems**L. Jeganathan, Kamala Krithivasan, Raghavan Rama, Appeared in

*International Conference on Theoretical and Mathematical Foundations of Computer Science*, pp.72-79, Jul 2008.**A Note on First-Fit Coloring of Interval Graphs**Narayanaswamy N S, Subhash Babu R., Appeared in

*Order*, Vol 25, pp.49-53, 2008.**Algorithms and heuristics for the single machine completion time variance minimization problem**Narayanaswamy N S, B. Chaitanya, B. Srirangacharyalu, G. Srinivasan, Appeared in

*Indian National Science Academy, New Delhi*, In the 40th Annual Convention of OR Society of India, Dec 2007.**On the Thickness of Branching Programs**Meena Mahajan, Jayalal Sarma, Appeared in

*Workshop on Computational Complexity and Decidability in Algebra*, Aug 2007.**A note on the Hadwiger number of circular arc graphs**Narayanaswamy N S, Naveen Belkale, Sunil Chandran L., Naveen Sivadasan, Appeared in

*Information Processing Letter*, Vol 104, No.1, pp.10--13, Jun 2007.**Sequences Characterizing k-Trees**Zvi Lotkar, Debapriyo Majunmdar, Narayanaswamy N S, Ingmar Weber, Appeared in

*12th Annual International Conference on Computing and Combinatoric*, Lecture Notes in Computer Science, Vol 4112, pp.216 - 225, Aug 2006.**An improved algorithm for online coloring of intervals with bandwidth.**Yossi Azar, Amos Fiat, Miatal Levi, Narayanaswamy N S, Appeared in

*Theoretical Computer Science*, Vol 363, No.1, pp.18--27, Jun 2006.**Graph splicing systems**Rahul Santhanam, Kamala Krithivasan, Appeared in

*Discrete Applied Mathematics*, Vol 154, pp.1264-1278, Feb 2006.**Distributed 2-way Finite State Quantum Automata**A Arun Prakash, Kamala Krithivasan, Appeared in

*Grammar Systems Week 2004*, Proceedings of GSW 2004, pp.15--29, Sep 2004.**Distributed Probabilistic Finite Automata**G. N. Santhana Krishnan, Kamala Krithivasan, Ashish Choudhary, Appeared in

*Grammar Systems Week 2004*, Proceedings of the GSW 2004, pp.281--289, Sep 2004.**Modeling Boolean Circuits using Peptide-Antibody Interactions**Sakthi Balan M., Kamala Krithivasan, Appeared in

*International conference on Mathematical Biology*, Sep 2004.**Dynamic Storage Allocation and On-Line Colouring Interval Graphs**Narayanaswamy N S, Appeared in

*10th Annual International Conference on Computing and Combinatorics*, Lecture Notes in Computer Science, Vol 3109, pp.329--338, Aug 2004.**On the Arrangement of Cliques in Chordal Graphs with Respect to the Cuts**Sunil Chandran L., Narayanaswamy N S, Appeared in

*International Conference on Computing and Combinatorics*, Lecture Notes in Computer Science, Vol 3106, pp.151-160, Aug 2004.**Algorithms for Satisfiability using Independent Sets of Variables**Narayanaswamy N S, Ravi Gummadi, R. Venkatakrishnan, Appeared in

*Vancouver, Canada*, SAT (Selected Papers), pp.133-144, May 2004.**Refining Randomness and Applications to Derandomization(Survey)**Jayalal Sarma, Appeared in

*Masters Thesis*, Mar 2004.**Some Variants in Communication of Parallel Communicating Pushdown Automata**Sakthi Balan M., Kamala Krithivasan, Madhu Mutyam, Appeared in

*Journal of Automata, Languages and Combinatorics*, Vol 8, pp.401--416, Sep 2003.**Distributed consensus in the presence of sectional faults**Amitanand Aiyer S., Sanketh Indrapu, Kannan Srinathan, Vinod Vaikuntanathan, C. Pandu Rangan, Appeared in

*Proceedings of the 22nd ACM Annual Symposium on Principles of Distributed Computing*, pp.202-210, Aug 2003.**Brief announcement: Efficient Perfectly Secure Communication over Synchronous Networks**Kannan Srinathan, Vinod Vaikuntanathan, C. Pandu Rangan, Appeared in

*Proceedings of the 22nd ACM Annual Symposium on Principles of Distributed Computing*, pp.252-252, Aug 2003.**Distributed omega automata**Kamala Krithivasan, Sharda K., Sandeep Varma, Appeared in

*International Journal of Foundations of Computer Science*, Vol 14, pp.681-698, Jul 2003.**On rule number complexity of components of probabilistic cooperating grammar systems**K. Aarthi, Kamala Krithivasan, Erzsebet Csuhaj-Varju, Appeared in

*Journal of Automata, Languages and Combinatorics*, Vol 7, pp.433--446, Sep 2002.**Generalized normal forms for Rewriting P Systems**Kamala Krithivasan, Madhu Mutyam, Appeared in

*Acta Informatica*, Vol 38, pp.721--734, Apr 2002.**On the generative power of Simple H Systems**Lakshminarayanan, Muralidhar Talupur, Kamala Krithivasan, C. Pandu Rangan, Appeared in

*Journal of Automata, Languages and Combinatorics*, Vol 5, pp.457--473, Sep 2000.**Finite Automata and Digital Images**Kamala Krithivasan, Ramasubramanian S.V., Appeared in

*International Journal of Pattern Recognition and Artificial Intelligence*, Vol 14, No.4, pp.501--524, Sep 2000.**Distributed Processing in Automata**Sakthi Balan M., Kamala Krithivasan, Prahladh Harsha, Appeared in

*International Journal of Foundations of Computer Science*, Vol 10, No.4, pp.443--463, Dec 1999.**Growth Functions and Syntatic Inference of Edge Replacement Graph OL Systems**Kamala Krithivasan, Raju Narayanaswamy, Appeared in

*The Third Centenary Celebrations of the Mathematical Society*, Mar 1990.