Research Publications/Reports
Listing All publications. View/Hide Filter- Energy and Output Patterns in Boolean Circuits
Jayalal Sarma, Kei Uchizawa, To Appear in 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), May 2024.
- On Rotation Distance of Rank Bounded Trees
Anoop S K M, Jayalal Sarma, Appeared in Fundamentae Informatica, Mar 2024. A preliminary version under the title "On Rotation Distance, Transpositions and Rank Bounded Trees" appeared in 28th International Computing and Combinatorics Conference (COCOON 2022), Oct 2022.
- A faster algorithm for Vertex Cover parameterized by solution size
David Harris, Narayanaswamy N S, Appeared in 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), Mar 2024.
- Approximately interpolating between uniformly and non-uniformly polynomial kernels
Akanksha Agrawal, Ramanujan M S, Appeared in 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2023.
- Recognizing Well-Dominated Graphs is NP-complete
Akanksha Agrawal, Henning Fernau, Mann Kevin, Philipp Kindermann, Uéverton S. Souza, Appeared in Information Processing Letters, Oct 2023.
- Testing properties of distributions in the streaming model
Sampriti Roy, Yadu Vasudev, Appeared in 34th International Symposium on Algorithms and Computation (ISAAC 2023), Sep 2023.
- Matchings under One-Sided Preferences with Soft Quotas
Santhini K A, Meghana Nasre, Raghu Raman Ravi, Appeared in International Joint Conference on Artificial Intelligence (IJCAI), Aug 2023.
- On Separating Words Problem over Groups
Neha Kuntewar, Anoop S K M, Jayalal Sarma, Appeared in 25th International Conference on Descriptional Complexity of Formal Systems (DCFS 2023), Jul 2023.
- Optimal Cost based allocation under Two sided preferences
Girija Limaye, Meghana Nasre, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), pp.259--270, Jun 2023.
- Critical Relaxed Stable Matchings with Two-Sided Ties
Keshav Ranjan, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023.
- Polynomial Kernel for Interval Vertex Deletion
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in ACM Transactions on Algorithms, Vol 19, No.2, pp.11:1-11:68, Apr 2023.
- Erdős-Pósa property of obstructions to interval graphs
Akanksha Agrawal, Daniel Lkoshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi, Appeared in Journal of Graph Theory, Vol 102, No.4, pp.702-727, Apr 2023.
- Clustering What Matters: Optimal Approximation for Clustering with Outliers
Akanksha Agrawal, Tanmay Inamdar, Saket Saurabh, Jie Xue, Appeared in The 37th AAAI Conference On Artificial Intelligence, Feb 2023.
- Envy-freeness and relaxed stability: hardness and approximation algorithms
Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar, Appeared in Journal of Combinatorial Optimization, Vol 45, No.1, pp.41, Jan 2023.
- Trade-Offs in Dynamic Coloring for Bipartite and General Graphs
Manas Jyothi Kashyap, Narayanaswamy N S, Meghana Nasre, Sai Mohith Potluri, Appeared in Algorithmica, Vol 85, No.4, pp.854--878, Jan 2023.
- Computing Square Colorings on Bounded-Treewidth and Planar Graphs
Akanksha Agrawal, Daniel Marx, Daniel Neuen, Jasper Slusallek, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), Jan 2023.
- On finding short reconfiguration sequences between independent sets
Akanksha Agrawal, Soumita Hait, Amer E. Mouawad, Appeared in The 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Dec 2022.
- Parameterized Complexity of Perfectly Matched Sets
Akanksha Agrawal, Sutanay Bhattacharjee, Abhishek Sahu, Satyabrata Jana, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- A Finite Algorithm for the Realizability of a Delaunay Triangulation
Akanksha Agrawal, Saket Saurabh, Meirav Zehavi, Appeared in The 17th International Symposium on Parameterized and Exact Computation (IPEC), Sep 2022.
- Distance From Triviality 2.0: Hybrid Parameterizations
Akanksha Agrawal, M.S. Ramanujan, Appeared in International Workshop on Combinatorial Algorithms (IWOCA), Jun 2022.
- Succinct Data Structure for Path Graphs
Girish Balakrishnan, Sankardeep Chakraborty, Narayanaswamy N S, Kunihiko Sadakane, Appeared in Data Compression Conference (DCC 2022), Mar 2022.
- Fine-grained complexity of rainbow coloring and its variants
Akanksha Agrawal, Appeared in Journal of Computer and System Sciences, Vol 124, Mar 2022.
- Parameterized Complexity of Minimum Membership Dominating Set
Akanksha Agrawal, Pratibha Choudhary, Narayanaswamy N S, Nisha K K, Vijayaraghunathan Ramamoorthi, Appeared in WALCOM, Mar 2022.
- Isomorphism Testing of Read-once Functions and Polynomials
Raghavendra Rao B V, Jayalal Sarma, Appeared in Information and Computation, Feb 2022. A preliminary version 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.
- Optimal Matchings with One-sided Preferences : Fixed and Cost Based Quotas
Santhini K A, Govind S. Sankar, Meghana Nasre, Appeared in Proc. of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2022),, To Appear, Jan 2022.
- Deleting, Eliminating and Decomposing to Hereditary Graph Classes Are All FPT Equivalent
Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Meirav Zehavi, Appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), Jan 2022.
- Popular Matchings in the Hospital-Residents Problem with Two-sided Lower Quotas
Meghana Nasre, Prajakta Nimbhorkar, Keshav Ranjan, Ankita Sarkar, Appeared in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Dec 2021.
- Refuting FPT Algorithms for Some Parameterized Problems Under Gap-ETH
Akanksha Agrawal, Allumalla Ravi Kiran, Dhanekula Varun Teja, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Sep 2021.
- A Polynomial Kernel for Deletion to Ptolemaic Graphs
Akanksha Agrawal, Aditya Anand, Saket Saurabh, Appeared in 16th International Symposium on Parameterized and Exact Computation (IPEC 2021), Aug 2021.
- Budgeted Dominating Sets in Uncertain Graphs
Narayanaswamy N S, David Peleg, Vijayaraghunathan Ramamoorthi, Keerti Choudhary, Avi Cohen, Appeared in 46th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aug 2021.
- Matchings with Group Fairness Constraints: Online and Offline Algorithms
Govind S. Sankar, Anand Louis, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), Aug 2021.
- On Alternation, VC-dimension and k-fold Union of Sets
Amit Kumar Roy, Jayalal Sarma, Appeared in European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB 2021), Jul 2021.
- Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
Dániel Marx, Govind S. Sankar, Philipp Schepper, Appeared in nternational Colloquium on Automata, Languages and Programming (ICALP 2021), Jun 2021.
- Dynamic Complexity of Expansion
Samir Dutta, Anuj Tawari, Yadu Vasudev, Appeared in The 16th International Computer Science Symposium in Russia (CSR 2021), Jun 2021.
- Limitations of Sums of Bounded Read Formulas and ABPs
Purnata Ghosal, Raghavendra Rao B V, Appeared in The 16th International Computer Science Symposium in Russia (CSR 2021), Jun 2021.
- Paths to Trees and Cacti
Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, Prafullkumar Tale, Appeared in Theoretical Computer Science, Vol 860, Mar 2021.
- An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, Appeared in Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- Parameterised Counting in Logspace
Anselm Haak, Arne Meier, Om Prakash, Raghavendra Rao B V, Appeared in The 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Mar 2021.
- On the Computational Power of Programs over BA_2 Monoid
Manasi Kulkarni, Jayalal Sarma, Janani Sundaresan, Appeared in 14th-15th International Conference on Language and Automata Theory and Applications (LATA 2021), Mar 2021.
- The Connected Domination Number of Grids
Narayanaswamy N S, Adarsh Srinivasan, Appeared in 7th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM 2021), Feb 2021.
- Envy-Freeness and Relaxed Stability: Hardness and Approximation Algorithms
Prem Krishnaa, Girija Limaye, Meghana Nasre, Prajakta Nimbhorkar, Appeared in 13th International Symposium Algorithmic Game Theory (SAGT 2020), Sep 2020.
- New Bounds for Energy Complexity of Boolean Functions
Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma, Appeared in Theoretical Computer Science, Sep 2020. A preliminary version appeared in The 24th International Computing and Combinatorics Conference (COCOON 2018), Jul 2018.
- On Measures of Space Over Real and Complex numbers
Om Prakash, Raghavendra Rao B V, Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- Power of Decision Trees with Monotone Queries
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma, Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- On the Mystery of Negations in Circuits : Structure vs Power
Prashanth Amireddy, Sai Jayasurya, Jayalal Sarma, Appeared in The 26th International Conference on Computing and Combinatorics (COCOON 2020), Aug 2020.
- Latency, Capacity, and Distributed Minimum Spanning Tree
John Augustine, Seth Gilbert, Fabian Kuhn, Peter Robinson, Suman Sourav, Appeared in 40th IEEE International Conference on Distributed Computing Systems, Jul 2020.
- Sensitivity, Affine Transforms and Quantum Communication Complexity
Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in Theoretical Computer Science (Invited Special Issue), Jun 2020. A preliminary version appeared in 25th International Computing and Combinatorics Conference (COCOON 2019), Vol 2018, No.152, Aug 2019.
- Guarding a Polygon Without Losing Touch
Barath Ashok, John Augustine, Aditya Mehekare, Sridhar Ragupathi, Srikkanth Ramachandran, Suman Sourav, Appeared in 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2020), Jun 2020.
- On the Parameterized Complexity of the Expected Coverage Problem
Fedor Fomin, Vijayaraghunathan Ramamoorthi, Appeared in 15th International Computer Science Symposium in Russia (CSR 2020), (Best Paper Award in CSR 2020), Jun 2020.
- Distributed Graph Realizations
John Augustine, Keerti Choudhary, Avi Cohen, David Peleg, Sumathi S., Suman Sourav, Singapore, Appeared in International Parallel and Distributed Processing Symposium (IPDPS 2020), May 2020.
- Optimal Broadcast Encryption from Pairings and LWE
Shweta Agrawal, Shota Yamada, Appeared in 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt 2020), (Best Paper Award in Eurocrypt 2020), May 2020.
- Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
Shweta Agrawal, Alice Pellet-Mary, Appeared in 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EuroCrypt 2020), May 2020.
- On Pure Space vs Catalytic Space
Sagar Bisoyi, Krishnamoorthy Dinesh, Jayalal Sarma, Appeared in The 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020), Apr 2020.
- Adaptive Simulation Security for Inner Product Functional Encryption
Shweta Agrawal, Benoît Libert, Monosij Maitra, Radu Titiu, Appeared in IACR International Conference on Practice and Theory of Public-Key Cryptography (PKC), Apr 2020.
- Perfect resolution for Conflict-Free Colouring of Interval Hypergraphs
Dhannya S.M., Narayanaswamy N S, Appeared in The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Mar 2020.
- Shortest Paths in a Hybrid Network Model
John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider, Appeared in 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Jan 2020.
- Ad hoc Multi-Input Functional Encryption.
Shweta Agrawal, Michael Clear, Ophir Frieder, Sajnam Garg, Adam ONeill, Amherst, Justin Thaler, Appeared in 11th Innovations in Theoretical Computer Science (ITCS), Jan 2020.
- Attribute Based Encryption for Deterministic Finite Automata from DLIN
Shweta Agrawal, Monosij Maitra, Shota Yamada, Appeared in Theory of Cryptography Conference (TCC 2019), Oct 2019.
- Minmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities
Guru Prakash Arumugam, John Augustine, Mordecai J. Golin, Prashanth Srikanthan, Appeared in Algorithmica, Vol 81, No.9, pp.3535-3584, Sep 2019.
- Lower Bounds for Multilinear Order-restricted ABPs
Ramya C., Raghavendra Rao B V, Appeared 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, Appeared 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, Appeared 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, Appeared in 38th Annual International Cryptology Conference (CRYPTO 2019), Aug 2019.
- Linear projections of the Vandermonde polynomial
Ramya C., Raghavendra Rao B V, Appeared in TCS, Theoretical Computer Science, Jul 2019.
- Shortest Paths in a Hybrid Network Model
John Augustine, Mohsen Ghaffari, Robert Gmyr, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Jason Li, Appeared in The 31st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA 2019), Jun 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.
- 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.
- Depth Lower Bounds against Circuits with Sparse Orientation
Sajin Koroth, Jayalal Sarma, Appeared in Fundamenta Informaticae, Vol 152, No.2, pp.123-144, Apr 2017. A preliminary version under the title "Depth Lower bounds against Circuits with Sparse Orientation" 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.
- 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 efficient 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.
- 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.
- 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.