Source author record

Noam Solomon

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

ResearcherUnclaimed source record

math.CO Computational Geometry math.AG Computational Complexity Data Structures and Algorithms Machine Learning Quantitative Methods Symbolic Computation

Catalog footprint

Research overview

13works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On rich points and incidences with restricted sets of lines in 3-space

Let $L$ be a set of $n$ lines in $R^3$ that is contained, when represented as points in the four-dimensional Plücker space of lines in $R^3$ , in an irreducible variety $T$ of constant degree which is \emph{non-degenerate} with respect to $L$ (see below). We show: \medskip \noindent{\bf (1)} If $T$ is two-dimensional, the number of $r$ -rich points (points incident to at least $r$ lines of $L$ ) is $O(n^{4/3+ε}/r^2)$ , for $r \ge 3$ and for any $ε>0$ , and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+ε})$ $2$ -rich points. For $r$ larger than some sufficiently large constant, the number of $r$ -rich points is also $O(n/r)$ . As an application, we deduce (with an $ε$ -loss in the exponent) the bound obtained by Pach and de Zeeuw (2107) on the number of distinct distances determined by $n$ points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle. \medskip \noindent{\bf (2)} If $T$ is two-dimensional, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $O(m+n)$ . \medskip \noindent{\bf (3)} If $T$ is three-dimensional and nonlinear, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $O\left(m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n \right)$ , provided that no plane contains more than $s$ of the points. When $s = O(\min\{n^{3/5}/m^{2/5}, m^{1/2}\})$ , the bound becomes $O(m^{3/5}n^{3/5}+m+n)$ . As an application, we prove that the number of incidences between $m$ points and $n$ lines in $R^4$ contained in a quadratic hypersurface (which does not contain a hyperplane) is $O(m^{3/5}n^{3/5} + m + n)$ . The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.

preprint2022arXiv

SystemMatch: optimizing preclinical drug models to human clinical outcomes via generative latent-space matching

Translating the relevance of preclinical models ( $\textit{in vitro}$ , animal models, or organoids) to their relevance in humans presents an important challenge during drug development. The rising abundance of single-cell genomic data from human tumors and tissue offers a new opportunity to optimize model systems by their similarity to targeted human cell types in disease. In this work, we introduce SystemMatch to assess the fit of preclinical model systems to an $\textit{in sapiens}$ target population and to recommend experimental changes to further optimize these systems. We demonstrate this through an application to developing $\textit{in vitro}$ systems to model human tumor-derived suppressive macrophages. We show with held-out $\textit{in vivo}$ controls that our pipeline successfully ranks macrophage subpopulations by their biological similarity to the target population, and apply this analysis to rank a series of 18 $\textit{in vitro}$ macrophage systems perturbed with a variety of cytokine stimulations. We extend this analysis to predict the behavior of 66 $\textit{in silico}$ model systems generated using a perturbational autoencoder and apply a $k$ -medoids approach to recommend a subset of these model systems for further experimental development in order to fully explore the space of possible perturbations. Through this use case, we demonstrate a novel approach to model system development to generate a system more similar to human biology.

preprint2020arXiv

A Generalized Matching Reconfiguration Problem

The goal in {\em reconfiguration problems} is to compute a {\em gradual transformation} between two feasible solutions of a problem such that all intermediate solutions are also feasible. In the {\em Matching Reconfiguration Problem} (MRP), proposed in a pioneering work by Ito et al.\ from 2008, we are given a graph $G$ and two matchings $M$ and $M'$ , and we are asked whether there is a sequence of matchings in $G$ starting with $M$ and ending at $M'$ , each resulting from the previous one by either adding or deleting a single edge in $G$ , without ever going through a matching of size $< \min\{|M|,|M'|\}-1$ . Ito et al.\ gave a polynomial time algorithm for the problem. In this paper we introduce a natural generalization of the MRP that depends on an integer parameter $Δ\ge 1$ : here we are allowed to make $Δ$ changes to the current solution rather than 1 at each step of the {transformation procedure}. There is always a valid sequence of matchings transforming $M$ to $M'$ if $Δ$ is sufficiently large, and naturally we would like to minimize $Δ$ . We first devise an optimal transformation procedure for unweighted matching with $Δ= 3$ , and then extend it to weighted matchings to achieve asymptotically optimal guarantees. The running time of these procedures is linear. We further demonstrate the applicability of this generalized problem to dynamic graph matchings. In this area, the number of changes to the maintained matching per update step (the \emph{recourse bound}) is an important quality measure. Nevertheless, the \emph{worst-case} recourse bounds of almost all known dynamic matching algorithms are prohibitively large, much larger than the corresponding update times. We fill in this gap via a surprisingly simple black-box reduction: Any dynamic algorithm for maintaining [...]

preprint2020arXiv

Derandomization from Algebraic Hardness

A hitting-set generator (HSG) is a polynomial map $G:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$ -variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ G$ is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following over any field of characteristic zero: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose $\{P_d\}_{d\in \mathbb{N}}$ is an explicit family of $k$ -variate polynomials such that $\operatorname{deg} P_d = d$ and $P_d$ requires algebraic circuits of size $d^δ$ . Then, there are explicit hitting sets of polynomial size for $\mathsf{VP}$ . This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. As a direct consequence, we show that even saving a single point from the "trivial" explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits, implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in \mathbb{N}$ and $δ> 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$ -variate polynomials of individual degree $s$ that are computable by size $s^δ$ circuits. Then there is an explicit hitting set of size $\operatorname{poly}(s)$ for the class of $s$ -variate polynomials, of degree $s$ , that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $τ$ -Conjecture of Shub and Smale is true.

preprint2020arXiv

Incidences between points and curves with almost two degrees of freedom

We study incidences between points and algebraic curves in three dimensions, taken from a family $C$ of curves that have almost two degrees of freedom, meaning that every pair of curves intersect in $O(1)$ points, for any pair of points $p$ , $q$ , there are only $O(1)$ curves of $C$ that pass through both points, and a pair $p$ , $q$ of points admit a curve of $C$ that passes through both of them iff $F(p,q)=0$ for some polynomial $F$ . We study two specific instances, one involving unit circles in $R^3$ that pass through some fixed point (so called anchored unit circles), and the other involving tangencies between directed points (points and directions) and circles in the plane; a directed point is tangent to a circle if the point lies on the circle and the direction is the tangent direction. A lifting transformation of Ellenberg et al. maps these tangencies to incidences between points and curves in three dimensions. In both instances the curves in $R^3$ have almost two degrees of freedom. We show that the number of incidences between $m$ points and $n$ anchored unit circles in $R^3$ , as well as the number of tangencies between $m$ directed points and $n$ arbitrary circles in the plane, is $O(m^{3/5}n^{3/5}+m+n)$ . We derive a similar incidence bound, with a few additional terms, for more general families of curves in $R^3$ with almost two degrees of freedom. The proofs follow standard techniques, based on polynomial partitioning, but face a novel issue involving surfaces that are infinitely ruled by the respective family of curves, as well as surfaces in a dual 3D space that are infinitely ruled by the respective family of suitably defined dual curves. The general bound that we obtain is $O(m^{3/5}n^{3/5}+m+n)$ plus additional terms that depend on how many curves or dual curves can lie on an infinitely-ruled surface.

preprint2020arXiv

Incidences with curves in three dimensions

We study incidence problems involving points and curves in $R^3$ . The current (and in fact only viable) approach to such problems, pioneered by Guth and Katz, requires a variety of tools from algebraic geometry, most notably (i) the polynomial partitioning technique, and (ii) the study of algebraic surfaces that are ruled by lines or, in more recent studies, by algebraic curves of some constant degree. By exploiting and refining these tools, we obtain new and improved bounds for point-curve incidence problems in $R^3$ . Incidences of this kind have been considered in several previous studies, starting with Guth and Katz's work on points and lines. Our results, which are based on the work of Guth and Zahl concerning surfaces that are doubly ruled by curves, provide a grand generalization of most of the previous results. We reconstruct the bound for points and lines, and improve, in certain significant ways, recent bounds involving points and circles (in Sharir, Sheffer and Zahl), and points and arbitrary constant-degree algebraic curves (in Sharir, Sheffer and Solomon). While in these latter instances the bounds are not known (and are strongly suspected not) to be tight, our bounds are, in a certain sense, the best that can be obtained with this approach, given the current state of knowledge. As an application of our point-curve incidence bound, we show that the number of triangles spanned by a set of $n$ points in $R^3$ and similar to a given triangle is $O(n^{15/7})$ , which improves the bound of Agarwal et al. Our results are also related to a study by Guth et al.~(work in progress), and have been recently applied in Sharir, Solomon and Zlydenko to related incidence problems in three dimensions.

preprint2016arXiv

Distinct and repeated distances on a surface and incidences between points and spheres

In this paper we show that the number of distinct distances determined by a set of $n$ points on a constant-degree two-dimensional algebraic variety $V$ (i.e., a surface) in $\mathbb R^3$ is at least $Ω\left(n^{7/9}/{\rm polylog} \,n\right)$ . This bound is significantly larger than the conjectured bound $Ω(n^{2/3})$ for general point sets in $\mathbb R^3$ . We also show that the number of unit distances determined by $n$ points on a surface $V$ , as above, is $O(n^{4/3})$ , a bound that matches the best known planar bound, and is worst-case tight in 3-space. This is in sharp contrast with the best known general bound $O(n^{3/2})$ for points in three dimensions. To prove these results, we establish an improved upper bound for the number of incidences between a set $P$ of $m$ points and a set $S$ of $n$ spheres, of arbitrary radii, in $\mathbb R^3$ , provided that the points lie on an algebraic surface $V$ of constant degree, which does not have linear or spherical components. Specifically, the bound is $O\left( m^{2/3}n^{2/3} + m^{1/2}n^{7/8}\log^β(m^4/n) + m + n + \sum_{c} |P_{c}|\cdot |S_{c}| \right) ,$ where the constant of proportionality and the constant exponent $β$ depend on the degree of $V$ , and where the sum ranges over all circles $c$ that are fully contained in $V$ , so that, for each such $c$ , $P_c = P\cap c$ and $S_c$ is the set of the spheres of $S$ that contain $c$ . In addition, $\sum_{c} |P_{c}| = O(m)$ and $\sum_{c} |S_{c}| = O(n)$ . This bound too improves upon earlier known bounds. These have been obtained for arbitrary point sets but only under severe restrictions about the spheres, which are dropped in our result. Another interesting application of our result is an incidence bound for arbitrary points and spheres in 3-space, where we improve and generalize the previous work of Apfelbaum and Sharir[AS].

preprint2016arXiv

Incidences between points and lines on two- and three-dimensional varieties

Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in $\mathbb R^4$ , such that the points of $P$ lie on an algebraic three-dimensional surface of degree $D$ that does not contain hyperplane or quadric components, and no 2-flat contains more than $s$ lines of $L$ . We show that the number of incidences between $P$ and $L$ is $I(P,L) = O\left(m^{1/2}n^{1/2}D + m^{2/3}n^{1/3}s^{1/3} + nD + m\right) ,$ for some absolute constant of proportionality. This significantly improves the bound of the authors, for arbitrary sets of points and lines in $\mathbb R^4$ , when $D$ is not too large. The same bound holds when the three-dimensional surface is embedded in any higher dimensional space. For the proof of this bound, we revisit certain parts of [Sharir-Solomon16], combined with the following new incidence bound. Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in $\mathbb R^d$ , for $d\ge 3$ , which lie in a common two-dimensional algebraic surface of degree $D$ (assumed to be $\ll n^{1/2}$ ) that does not contain any 2-flat, so that no 2-flat contains more than $s$ lines of $L$ (here we require that the lines of $L$ also be contained in the surface). Then the number of incidences between $P$ and $L$ is $I(P,L) = O\left(m^{1/2}n^{1/2}D^{1/2} + m^{2/3}D^{2/3}s^{1/3} + m + n\right).$ When $d=3$ , this improves the bound of Guth and Katz for this special case, when $D \ll n^{1/2}$ . Moreover, the bound does not involve the term $O(nD)$ , that arises in most standard approaches, and its removal is a significant aspect of our result. Finally, we also obtain (slightly weaker) variants of both results over the complex field. For two-dimensional varieties, the bound is as in the real case, with an added term of $O(D^3)$ . For three-dimensional varieties, the bound is as in the real case, with an added term of $O(D^6)$ .

preprint2015arXiv

Generalizations of the Szemerédi-Trotter Theorem

We generalize the Szemerédi-Trotter incidence theorem, to bound the number of complete \emph{flags} in higher dimensions. Specifically, for each $i=0,1,\ldots,d-1$ , we are given a finite set $S_i$ of $i$ -flats in $\R^d$ or in $\C^d$, and a (complete) flag is a tuple $(f_0,f_1,\ldots,f_{d-1})$ , where $f_i\in S_i$ for each $i$ and $f_i\subset f_{i+1}$ for each $i=0,1,\ldots,d-2$ . Our main result is an upper bound on the number of flags which is tight in the worst case. We also study several other kinds of incidence problems, including (i) incidences between points and lines in $\R^3$ such that among the lines incident to a point, at most $O(1)$ of them can be coplanar, (ii) incidences with Legendrian lines in $\R^3$ , a special class of lines that arise when considering flags that are defined in terms of other groups, and (iii) flags in $\R^3$ (involving points, lines, and planes), where no given line can contain too many points or lie on too many planes. The bound that we obtain in (iii) is nearly tight in the worst case. Finally, we explore a group theoretic interpretation of flags, a generalized version of which leads us to new incidence problems.

preprint2015arXiv

Incidences between points and lines in R^4

We show that the number of incidences between $m$ distinct points and $n$ distinct lines in ${\mathbb R}^4$ is $O\left(2^{c\sqrt{\log m}} (m^{2/5}n^{4/5}+m) + m^{1/2}n^{1/2}q^{1/4} + m^{2/3}n^{1/3}s^{1/3} + n\right)$ , for a suitable absolute constant $c$ , provided that no 2-plane contains more than $s$ input lines, and no hyperplane or quadric contains more than $q$ lines. The bound holds without the factor $2^{c\sqrt{\log m}}$ when $m \le n^{6/7}$ or $m \ge n^{5/3}$ . Except for this factor, the bound is tight in the worst case.

preprint2015arXiv

Incidences between points and lines in three dimensions

We give a fairly elementary and simple proof that shows that the number of incidences between $m$ points and $n$ lines in ${\mathbb R}^3$ , so that no plane contains more than $s$ lines, is $O\left(m^{1/2}n^{3/4}+ m^{2/3}n^{1/3}s^{1/3} + m + n\right)$ (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between $m$ and $n$ ). This bound, originally obtained by Guth and Katz~\cite{GK2} as a major step in their solution of Erd{\H o}s's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth~\cite{Gu14}. The present paper presents a different and simpler derivation, with better bounds than those in \cite{Gu14}, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.

preprint2015arXiv

Incidences between points and lines on a two-dimensional variety

We present a direct and fairly simple proof of the following incidence bound: Let $P$ be a set of $m$ points and $L$ a set of $n$ lines in ${\mathbb R}^d$ , for $d\ge 3$ , which lie in a common algebraic two-dimensional surface of degree $D$ that does not contain any 2-flat, so that no 2-flat contains more than $s \le D$ lines of $L$ . Then the number of incidences between $P$ and $L$ is $I(P,L)=O\left(m^{1/2}n^{1/2}D^{1/2} + m^{2/3}\min\{n,D^{2}\}^{1/3}s^{1/3} + m + n\right).$ When $d=3$ , this improves the bound of Guth and Katz~\cite{GK2} for this special case, when $D$ is not too large. A supplementary feature of this work is a review, with detailed proofs, of several basic (and folklore) properties of ruled surfaces in three dimensions.

preprint2015arXiv

Incidences with curves in R^d

We prove that the number of incidences between $m$ points and $n$ bounded-degree curves with $k$ degrees of freedom in ${\mathbb R}^d$ is $I(m,n) =O\left(m^{\frac{k}{dk-d+1}+\varepsilon}n^{\frac{dk-d}{dk-d+1}}+ \sum_{j=2}^{d-1} m^{\frac{k}{jk-j+1}+\varepsilon}n^{\frac{d(j-1)(k-1)}{(d-1)(jk-j+1)}}q_j^{\frac{(d-j)(k-1)}{(d-1)(jk-j+1)}}+m+n\right),$ for any $\varepsilon>0$ , where the constant of proportionality depends on $k, \varepsilon$ and $d$ , provided that no $j$ -dimensional surface of degree $\le c_j(k,d,\varepsilon)$ , a constant parameter depending on $k$ , $d$ , $j$ , and $\varepsilon$ , contains more than $q_j$ input curves, and that the $q_j$ 's satisfy certain mild conditions. This bound generalizes a recent result of Sharir and Solomon concerning point-line incidences in four dimensions (where $d=4$ and $k=2$ ), and partly generalizes a recent result of Guth (as well as the earlier bound of Guth and Katz) in three dimensions (Guth's three-dimensional bound has a better dependency on $q_2$ ). It also improves a recent $d$ -dimensional general incidence bound by Fox, Pach, Sheffer, Suk, and Zahl, in the special case of incidences with algebraic curves. Our results are also related to recent works by Dvir and Gopi and by Hablicsek and Scherr concerning rich lines in high-dimensional spaces.

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.

Noam Solomon

Research overview

Is this your work?

13 publications

On rich points and incidences with restricted sets of lines in 3-space

SystemMatch: optimizing preclinical drug models to human clinical outcomes via generative latent-space matching

A Generalized Matching Reconfiguration Problem

Derandomization from Algebraic Hardness

Incidences between points and curves with almost two degrees of freedom

Incidences with curves in three dimensions

Distinct and repeated distances on a surface and incidences between points and spheres

Incidences between points and lines on two- and three-dimensional varieties

Generalizations of the Szemerédi-Trotter Theorem

Incidences between points and lines in R^4

Incidences between points and lines in three dimensions

Incidences between points and lines on a two-dimensional variety

Incidences with curves in R^d

See the researcher in context

Building this map preview