Nikhil Balaji

According to our database, Nikhil Balaji authored at least 20 papers between 2013 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

A parametric version of the Hilbert Nullstellensatz.

Rida Ait El Manssour, Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi, James Worrell

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

2024

USSR is in P/poly.

Nikhil Balaji, Samir Datta

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

2023

Multiplicity Problems on Algebraic Series and Context-Free Grammars.

Nikhil Balaji, Lorenzo Clemente, Klara Nosan, Mahsa Shirmohammadi, James Worrell

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

2022

On the Complexity of Algebraic Numbers, and the Bit-Complexity of Straight-Line Programs.

Eric Allender, Nikhil Balaji, Samir Datta, Rameshwar Pratap

Electron. Colloquium Comput. Complex., 2022

Terms of Lucas sequences having a large smooth divisor.

Nikhil Balaji, Florian Luca

CoRR, 2022

Identity Testing for Radical Expressions.

Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi, James Worrell

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

2021

Cyclotomic Identity Testing and Applications.

Nikhil Balaji, Sylvain Perifel, Mahsa Shirmohammadi, James Worrell

Proceedings of the ISSAC '21: International Symposium on Symbolic and Algebraic Computation, 2021

2020

Near-Optimal Complexity Bounds for Fragments of the Skolem Problem.

S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, Nikhil Vyas

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2019

On the Complexity of Value Iteration.

Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, Mahsa Shirmohammadi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

On the Complexity of Iterative Tropical Computation with Applications to Markov Decision Processes.

Nikhil Balaji, Stefan Kiefer, Petr Novotný, Guillermo A. Pérez, Mahsa Shirmohammadi

CoRR, 2018

2017

Complexity of Restricted Variants of Skolem and Related Problems.

S. Akshay, Nikhil Balaji, Nikhil Vyas

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP.

Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

Graph Properties in Node-Query Setting: Effect of Breaking Symmetry.

Nikhil Balaji, Samir Datta, Raghav Kulkarni, Supartha Podder

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2015

Bounded Treewidth and Space-Efficient Linear Algebra.

Nikhil Balaji, Samir Datta

Proceedings of the Theory and Applications of Models of Computation, 2015

Counting Euler Tours in Undirected Bounded Treewidth Graphs.

Nikhil Balaji, Samir Datta, Venkatesh Ganesan

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Skew Circuits of Small Width.

Nikhil Balaji, Andreas Krebs, Nutan Limaye

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

2014

Collapsing Exact Arithmetic Hierarchies.

Nikhil Balaji, Samir Datta

Proceedings of the Algorithms and Computation - 8th International Workshop, 2014

Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs.

Eric Allender, Nikhil Balaji, Samir Datta

Proceedings of the Mathematical Foundations of Computer Science 2014, 2014

Sentence Completion Using Text Prediction Systems.

Kavita Asnani, Douglas Vaz, Tanay PrabhuDesai, Surabhi Borgikar, Megha Bisht, Sharvari Bhosale, Nikhil Balaji

Proceedings of the 3rd International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2014, 2014

2013

Tree-width and Logspace: Determinants and Counting Euler Tours.

Nikhil Balaji, Samir Datta

CoRR, 2013