Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANKIT GARG:
All reports by Author Ankit Garg:

TR20-045 | 15th April 2020
Ankit Garg, Neeraj Kayal, Chandan Saha

Learning sums of powers of low-degree polynomials in the non-degenerate case

We develop algorithms for writing a polynomial as sums of powers of low degree polynomials. Consider an $n$-variate degree-$d$ polynomial $f$ which can be written as
$$f = c_1Q_1^{m} + \ldots + c_s Q_s^{m},$$
where each $c_i\in \mathbb{F}^{\times}$, $Q_i$ is a homogeneous polynomial of degree $t$, and $t m = ... more >>>


TR19-042 | 18th March 2019
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Determinant equivalence test over finite fields and over $\mathbf{Q}$

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>


TR18-151 | 29th August 2018
Ankit Garg, Rafael Oliveira

Recent progress on scaling algorithms and applications

Scaling problems have a rich and diverse history, and thereby have found numerous
applications in several fields of science and engineering. For instance, the matrix scaling problem
has had applications ranging from theoretical computer science to telephone forecasting,
economics, statistics, optimization, among many other fields. Recently, a generalization of matrix
more >>>




ISSN 1433-8092 | Imprint