516 citations · 1.1k across the 20 of their papers we have counts for
4 papers · 1 filter
Tight Chang's-lemma-type bounds for Boolean functions
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal +3
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function that ta…
Efficiently factoring polynomials modulo
Ashish Dwivedi, Rajat Mittal, Nitin Saxena
Polynomial factoring has famous practical algorithms over fields-- finite, rational \& -adic. However, modulo prime powers it gets hard as there is non-unique factorization and…
Irreducibility and r-th root finding over finite fields
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal +1
Constructing -th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree (where is…
Product theorems via semidefinite programming
Troy Lee, Rajat Mittal
The tendency of semidefinite programs to compose perfectly under product has been exploited many times in complexity theory: for example, by Lovasz to determine the Shannon capacit…