Research Publications/ReportsListing last 25 publications. (View All) View/Hide Filter
- Attribute Based Encryption (and more) for Nondeterministic Finite Automata from Learning With Errors
- Space Complexity of Labelled Graph Reachability Problem
Vidhya Ramaswamy, Jayalal Sarma, K.S. Sunil, To Appear 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.
- Classified Rank-Maximal Matchings and Popular Matchings -- Algorithms and Hardness
- Indistinguishability Obfuscation Without Multilinear Maps: New Methods for Bootstrapping and Instantiation.
Shweta Agrawal, To Appear 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.
- Sensitivity, Affine Transforms and Quantum Communication Complexity
- A Two-Sided Error Distributed Property Tester For Conductance
- 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
- Minimum Membership Hitting Sets of Axis Parallel Segments
- A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
- Lower Bounds for Special Classes of Syntactic Multilinear ABPs
- New Bounds for Energy Complexity of Boolean Functions
- Wiretap Polar Codes in Encryption Schemes Based on Learning with Errors Problem
- How good are popular matchings?
- Facility location on planar graphs with unreliable links
- Spartan: A Framework For Sparse Robust Addressable Networks
- 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
- Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs
- 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
- Efficient Public Trace-and-Revoke from Standard Assumptions