Research Publications/ReportsListing last 25 publications. (View All) View/Hide Filter
- Lower Bounds for Multilinear Order-restricted ABPs
- On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
- Fully Dynamic Data Structures for Interval Coloring
- Attribute Based Encryption (and more) for Nondeterministic Finite Automata from Learning With Errors
- Sensitivity, Affine Transforms and Quantum Communication Complexity
- Linear projections of the Vandermonde polynomial
- 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
- 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.
- 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.