Source author record

Grigory Solomatov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT Symbolic Computation Computer Vision math.AG

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Conditions for well-posed color recovery in scattering media

Recovering scene color from images captured in scattering media is a fundamental inverse problem in optical imaging. Yet the problem is intrinsically ill-posed as multiple solutions can explain the same observation, and prediction error cannot be controlled without understanding the space of candidate solutions. Here, we present sufficient conditions under which color recovery in a scattering medium becomes well-posed. Observing that ill-posedness stems from (i) projection of spectral signals onto pixel intensities, and (ii) unknown medium parameters, we demonstrate that sensor improvements alone cannot resolve medium-induced distortions without additional constraints. We identify recovery patterns, cross-pixel relationships that naturally occur in images, and prove, for an ideal hyperspectral camera, that they restrict the solution to a unique candidate. This opens the door to a new class of vision algorithms grounded in first principles, enabling quantitative analysis of images in scattering environments.

preprint2022arXiv

Fast Decoding of AG Codes

We present an efficient list decoding algorithm in the style of Guruswami-Sudan for algebraic geometry codes. Our decoder can decode any such code using $\tilde{\mathcal O}(s\ell^ωμ^{ω-1}(n+g))$ operations in the underlying finite field, where $n$ is the code length, $g$ is the genus of the function field used to construct the code, $s$ is the multiplicity parameter, $\ell$ is the designed list size and $μ$ is the smallest positive element in the Weierstrass semigroup at some chosen place; the "soft-O" notation $\tilde{\mathcal O}(\cdot)$ is similar to the "big-O" notation ${\mathcal O}(\cdot)$ , but ignores logarithmic factors. For the interpolation step, which constitutes the computational bottleneck of our approach, we use known algorithms for univariate polynomial matrices, while the root-finding step is solved using existing algorithms for root-finding over univariate power series.

preprint2020arXiv

Fast Encoding of AG Codes over $C_{ab}$ Curves

We investigate algorithms for encoding of one-point algebraic geometry (AG) codes over certain plane curves called $C_{ab}$ curves, as well as algorithms for inverting the encoding map, which we call "unencoding". Some $C_{ab}$ curves have many points or are even maximal, e.g. the Hermitian curve. Our encoding resp. unencoding algorithms have complexity $\tilde{O}(n^{3/2})$ resp. $\tilde{O}(qn)$ for AG codes over any $C_{ab}$ curve satisfying very mild assumptions, where $n$ is the code length and $q$ the base field size, and $\tilde{O}$ ignores constants and logarithmic factors in the estimate. For codes over curves whose evaluation points lie on a grid-like structure, notably the Hermitian curve and norm-trace curves, we show that our algorithms have quasi-linear time complexity $\tilde{O}(n)$ for both operations. For infinite families of curves whose number of points is a constant factor away from the Hasse--Weil bound, our encoding algorithm has complexity $\tilde{O}(n^{5/4})$ while unencoding has $\tilde{O}(n^{3/2})$ .

preprint2020arXiv

Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation

Suppose $\mathbb{K}$ is a large enough field and $\mathcal{P} \subset \mathbb{K}^2$ is a fixed, generic set of points which is available for precomputation. We introduce a technique called \emph{reshaping} which allows us to design quasi-linear algorithms for both: computing the evaluations of an input polynomial $f \in \mathbb{K}[x,y]$ at all points of $\mathcal{P}$ ; and computing an interpolant $f \in \mathbb{K}[x,y]$ which takes prescribed values on $\mathcal{P}$ and satisfies an input $y$ -degree bound. Our genericity assumption is explicit and we prove that it holds for most point sets over a large enough field. If $\mathcal{P}$ violates the assumption, our algorithms still work and the performance degrades smoothly according to a distance from being generic. To show that the reshaping technique may have an impact on other related problems, we apply it to modular composition: suppose generic polynomials $M \in \mathbb{K}[x]$ and $A \in \mathbb{K}[x]$ are available for precomputation, then given an input $f \in \mathbb{K}[x,y]$ we show how to compute $f(x, A(x)) \operatorname{rem} M(x)$ in quasi-linear time.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Grigory Solomatov

Research overview

Is this your work?

4 publications

Conditions for well-posed color recovery in scattering media

Fast Decoding of AG Codes

Fast Encoding of AG Codes over $C_{ab}$ Curves

Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation

See the researcher in context

Building this map preview

Grigory Solomatov

Research overview

Is this your work?

4 publications

Conditions for well-posed color recovery in scattering media

Fast Decoding of AG Codes

Fast Encoding of AG Codes over CabC_{ab}Cab​ Curves

Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation

See the researcher in context

Building this map preview

Fast Encoding of AG Codes over $C_{ab}$ Curves