Noam Solomon
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Noam Solomon has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Micha Sharir
School of Computer Science, Tel Aviv University, Tel Aviv, Israel
10 shared publications - Mrinal Kumar
Tata Institute of Fundamental Research, Mumbai, India
3 shared publications - Chi-Ning Chou
School of Engineering and Applied Sciences Harvard University Cambridge Massachusetts USA
2 shared publications - Guy Moshkovitz
Institute for Advanced Study and DIMACS ( Rutgers University)
2 shared publications - Noga Alon
Department of Mathematics, Princeton University, Princeton, USA
2 shared publications - Ruixiang Zhang
Princeton Univ, Dept Math, Princeton, NJ 08540 USA
2 shared publications
Latest Publications
- 1 December 2025
- Published by Institute of Mathematical Statistics in The Annals of Applied Statistics
- Vol. 19 (4) , 2664-2682
Improving accuracy in cell-perturbation experiments by leveraging auxiliary information
Modern cell-perturbation experiments expose cells to panels of hundreds of treatments, such as cytokines or CRISPR guides. These experiments are designed to investigate whether a particular gene is up- or downregulated by exposure to each treatment. Typical estimators of whether a gene is up- or down-regulated make many errors due to high levels of experimental noise and complex donor and batch effects. In this article we explore whether estimator error rates can be reduced by pooling measurements according to auxiliary information, such as prior knowledge of treatments that are likely to have similar effects. Because auxiliary information can be misleading and because it is generally infeasible to model its quality, we take a model-free approach to identifying a subset of estimates in which error is reliably controlled. We validate this overall approach in simulation, comparing it to an alternative based on the Benjamini–Hochberg procedure. We then use the proposed approach to reanalyze a high-throughput CRISPRa screening and a small-molecule drug screening, which leads to new discoveries about the effects of gene augmentation on immune cells and the effects of cytokines on cancer cells.
- 1 December 2025
- Published by Institute of Mathematical Statistics in The Annals of Applied Statistics
- Vol. 19 (4) , 2664-2682
Improving accuracy in cell-perturbation experiments by leveraging auxiliary information
Modern cell-perturbation experiments expose cells to panels of hundreds of treatments, such as cytokines or CRISPR guides. These experiments are designed to investigate whether a particular gene is up- or downregulated by exposure to each treatment. Typical estimators of whether a gene is up- or down-regulated make many errors due to high levels of experimental noise and complex donor and batch effects. In this article we explore whether estimator error rates can be reduced by pooling measurements according to auxiliary information, such as prior knowledge of treatments that are likely to have similar effects. Because auxiliary information can be misleading and because it is generally infeasible to model its quality, we take a model-free approach to identifying a subset of estimates in which error is reliably controlled. We validate this overall approach in simulation, comparing it to an alternative based on the Benjamini–Hochberg procedure. We then use the proposed approach to reanalyze a high-throughput CRISPRa screening and a small-molecule drug screening, which leads to new discoveries about the effects of gene augmentation on immune cells and the effects of cytokines on cancer cells.
- Open Access
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\"ucker 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+\epsilon}/r^2)$, for $r \ge 3$ and for any $\epsilon>0$, and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+\epsilon})$ $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 $\epsilon$-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.Open AccessOn 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\"ucker 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+\epsilon}/r^2)$, for $r \ge 3$ and for any $\epsilon>0$, and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+\epsilon})$ $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 $\epsilon$-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. - Open Access
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 $\delta > 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^\delta$. 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 $\delta > 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^\delta$ 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 $\tau$-Conjecture of Shub and Smale is true.Open AccessDerandomization 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 $\delta > 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^\delta$. 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 $\delta > 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^\delta$ 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 $\tau$-Conjecture of Shub and Smale is true. - Open Access
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 $\Delta \ge 1$: here we are allowed to make $\Delta$ 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 $\Delta$ is sufficiently large, and naturally we would like to minimize $\Delta$. We first devise an optimal transformation procedure for unweighted matching with $\Delta = 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 [...]Open AccessA 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 $\Delta \ge 1$: here we are allowed to make $\Delta$ 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 $\Delta$ is sufficiently large, and naturally we would like to minimize $\Delta$. We first devise an optimal transformation procedure for unweighted matching with $\Delta = 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 [...] - 11 November 2019
- Published by Springer Nature in Geometric and Functional Analysis
- Vol. 29 (6) , 1844-1863
Incidence Estimates for Well Spaced Tubes
- 11 November 2019
- Published by Springer Nature in Geometric and Functional Analysis
- Vol. 29 (6) , 1844-1863
Incidence Estimates for Well Spaced Tubes
- Open Access
From DNF compression to sunflower theorems via regularity
The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds for the sunflower conjecture, which is the reverse direction of [Computational Complexity 2013]. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.
Open AccessFrom DNF compression to sunflower theorems via regularity
The sunflower conjecture is one of the most well-known open problems in combinatorics. It has several applications in theoretical computer science, one of which is DNF compression, due to Gopalan, Meka and Reingold [Computational Complexity 2013]. In this paper, we show that improved bounds for DNF compression imply improved bounds for the sunflower conjecture, which is the reverse direction of [Computational Complexity 2013]. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.
- 12 May 2019
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 100 (2) , 498-517
Traces of hypergraphs
- 12 May 2019
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 100 (2) , 498-517
Traces of hypergraphs
- Open Access
Closure of VP under taking factors: a short and simple proof
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an $n$ variate degree $d$ polynomial $f$ can be computed by an arithmetic circuit of size $s$, then each of its factors can be computed by an arithmetic circuit of size at most $\textsf{poly}\left(s, n, d\right)$. However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of $f$.Open AccessClosure of VP under taking factors: a short and simple proof
In this note, we give a short, simple and almost completely self contained proof of a classical result of Kaltofen [Kal86, Kal87, Kal89] which shows that if an $n$ variate degree $d$ polynomial $f$ can be computed by an arithmetic circuit of size $s$, then each of its factors can be computed by an arithmetic circuit of size at most $\textsf{poly}\left(s, n, d\right)$. However, unlike Kaltofen's argument, our proof does not directly give an efficient algorithm for computing the circuits for the factors of $f$. - Open Access
- 21 November 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (4) , 698-734
Subquadratic Algorithms for Algebraic 3SUM
- 21 November 2018
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 61 (4) , 698-734
Open AccessSubquadratic Algorithms for Algebraic 3SUM
- Open Access
Traces of Hypergraphs
Let $\text{Tr}(n,m,k)$ denote the largest number of distinct projections onto $k$ coordinates guaranteed in any family of $m$ binary vectors of length $n$. The classical Sauer-Perles-Shelah Lemma implies that $\text{Tr}(n, n^r, k) = 2^k$ for $k \le r$. While determining $\text{Tr}(n,n^r,k)$ precisely for general $k$ seems hopeless even for constant $r$, estimating it, and more generally estimating the function $\text{Tr}(n,m,k)$ for all range of the parameters, remains a widely open problem with connections to important questions in computer science and combinatorics. Here we essentially resolve this problem when $k$ is linear and $m=n^r$ where $r$ is constant, proving that, for any constant $\alpha>0$, $\text{Tr}(n,n^r,\alpha n) = \tilde\Theta(n^C)$ with $C=C(r,\alpha)=\frac{r+1-\log(1+\alpha)}{2-\log(1+\alpha)}$. For the proof we establish a "sparse" version of another classical result, the Kruskal-Katona Theorem, which gives a stronger guarantee when the hypergraph does not induce dense sub-hypergraphs. Furthermore, we prove that the parameters in our sparse Kruskal-Katona theorem are essentially best possible. Finally, we mention two simple applications which may be of independent interest.Open AccessTraces of Hypergraphs
Let $\text{Tr}(n,m,k)$ denote the largest number of distinct projections onto $k$ coordinates guaranteed in any family of $m$ binary vectors of length $n$. The classical Sauer-Perles-Shelah Lemma implies that $\text{Tr}(n, n^r, k) = 2^k$ for $k \le r$. While determining $\text{Tr}(n,n^r,k)$ precisely for general $k$ seems hopeless even for constant $r$, estimating it, and more generally estimating the function $\text{Tr}(n,m,k)$ for all range of the parameters, remains a widely open problem with connections to important questions in computer science and combinatorics. Here we essentially resolve this problem when $k$ is linear and $m=n^r$ where $r$ is constant, proving that, for any constant $\alpha>0$, $\text{Tr}(n,n^r,\alpha n) = \tilde\Theta(n^C)$ with $C=C(r,\alpha)=\frac{r+1-\log(1+\alpha)}{2-\log(1+\alpha)}$. For the proof we establish a "sparse" version of another classical result, the Kruskal-Katona Theorem, which gives a stronger guarantee when the hypergraph does not induce dense sub-hypergraphs. Furthermore, we prove that the parameters in our sparse Kruskal-Katona theorem are essentially best possible. Finally, we mention two simple applications which may be of independent interest.