Research Publications/ReportsListing last 25 publications. (View All) View/Hide Filter
- Pebbling Meets Coloring: Reversible Pebble Game On Trees
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani, To Appear in Journal of Computer and System Sciences (Accepted), Nov 2017. A preliminary version under the title "Reversible Pebble Game on Trees" appeared in 21st International Computing and Combinatorics Conference (COCOON 2015), Aug 2015.
- On Weak-Space Complexity over Complex Numbers
- On depth five Sum-Power-Sum-Power-Sum Circuits: The Role of Middle Σ Fan-in, Homogeneity and Bottom Degree
- Testing Equivalence of Polynomials under Scaling
- Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
- On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
- Interpolating Predicate and Functional Encryption from Learning With Errors
Shweta Agrawal, To Appear in 37th International Cryptology Conference (CRYPTO 2017), Aug 2017.
- The Price of Selection in Differential Privacy
- Reusable Garbled Deterministic Finite Automata from Learning With Errors
- Popularity in the generalized Hospital Residents setting
- 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.
- Comparator Circuits over Finite Bounded Posets
Balagopal Komarath, Jayalal Sarma, Sunil K.S., Appeared in Information & Computation, (Accepted), Apr 2017. A preliminary version appeared in Proceedings of International Conference on Automata, Languages and Programming (ICALP), Jul 2015.
- Space Complexity of Labelled Graph Reachability Problem
- Sum of products of Read-Once Polynomials
- Characterization and Lower Bounds for Branching Program Size using Projective Dimension
- Information Spreading in Dynamic Networks under Oblivious Adversaries
- Hitting Set for hypergraphs of low VC-dimension
- A Refined Analysis of Online Path Coloring in Trees
- On the Sensitivity Conjecture for Read-k Formulas
- On the Complexity Landscape of Connected f-factor Problems
- On Hard Instances of Non-Commutative Permanent
- Sub-families of Baxter Permutations Based on Pattern Avoidance
- 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
- 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.