Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Rajat Mittal:

TR23-099 | 8th July 2023
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>

TR22-143 | 7th November 2022
Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny

Certificate games

Revisions: 1

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index $i$ such that $x_i\neq y_i$, in a zero-communication setting.

We give upper and lower ... more >>>

TR19-033 | 20th February 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications

Finding an irreducible factor, of a polynomial $f(x)$ modulo a prime $p$, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that {\em counts} the number of irreducible factors of $f\bmod p$. We can ask the same question modulo prime-powers $p^k$. The irreducible ... more >>>

TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Efficiently factoring polynomials modulo $p^4$

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>>

TR17-016 | 31st January 2017
Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena

Irreducibility and deterministic r-th root finding over finite fields

Constructing $r$-th nonresidue over a finite field is a fundamental computational problem. A related problem is to construct an irreducible polynomial of degree $r^e$ (where $r$ is a prime) over a given finite field $\F_q$ of characteristic $p$ (equivalently, constructing the bigger field $\F_{q^{r^e}}$). Both these problems have famous randomized ... more >>>

ISSN 1433-8092 | Imprint