9 citations · 11 across the 8 of their papers we have counts for
12 papers
Approximate Polynomial Satisfiability is in the Counting Hierarchy
Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas +1
The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image…
USSR is in P/poly
Nikhil Balaji, Samir Datta
The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers , and signs , check if $\sum_{…
Multiplicity Problems on Algebraic Series and Context-Free Grammars
Nikhil Balaji, Lorenzo Clemente, Klara Nosan +2
In this paper we obtain complexity bounds for computational problems on algebraic power series over several commuting variables. The power series are specified by systems of polyno…
Terms of Lucas sequences having a large smooth divisor
Nikhil Balaji, Florian Luca
We show that the --smooth part of for an integer is for most positive integers .
Identity Testing for Radical Expressions
Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi +1
We study the Radical Identity Testing problem (RIT): Given an algebraic circuit representing a polynomial and nonnegative integers $a_1, \ldots,…
Cyclotomic Identity Testing and Applications
Nikhil Balaji, Sylvain Perifel, Mahsa Shirmohammadi +1
We consider the cyclotomic identity testing (CIT) problem: given a polynomial , decide whether is zero, where i…