8 Search Results for "Solomon, Noam"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.56
On Rich Points and Incidences with Restricted Sets of Lines in 3-Space

Authors: Micha Sharir and Noam Solomon

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Let L be a set of n lines in ℝ³ that is contained, when represented as points in the four-dimensional Plücker space of lines in ℝ³, in an irreducible variety T of constant degree which is non-degenerate with respect to L (see below). We show: (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²), for r ⩾ 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 [J. Pach and F. de Zeeuw, 2017] 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. (2) If T is two-dimensional, the number of incidences between L and a set of m points in ℝ³ is O(m+n). (3) If T is three-dimensional and nonlinear, the number of incidences between L and a set of m points in ℝ³ is O (m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n), 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 ℝ⁴ 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.
Cite as

Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56,
  author =	{Sharir, Micha and Solomon, Noam},
  title =	{{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.56},
  URN =		{urn:nbn:de:0030-drops-138551},
  doi =		{10.4230/LIPIcs.SoCG.2021.56},
  annote =	{Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.57
A Generalized Matching Reconfiguration Problem

Authors: Noam Solomon and Shay Solomon

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
The goal in reconfiguration problems is to compute a gradual transformation between two feasible solutions of a problem such that all intermediate solutions are also feasible. In the 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, which uses the Edmonds-Gallai decomposition. In this paper we introduce a natural generalization of the MRP that depends on an integer parameter Δ ≥ 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 recourse bound) is an important quality measure. Nevertheless, the 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 a β-approximate maximum cardinality matching with update time T, for any β ≥ 1, T and ε > 0, can be transformed into an algorithm for maintaining a (β(1 +ε))-approximate maximum cardinality matching with update time T + O(1/ε) and worst-case recourse bound O(1/ε). This result generalizes for approximate maximum weight matching, where the update time and worst-case recourse bound grow from T + O(1/ε) and O(1/ε) to T + O(ψ/ε) and O(ψ/ε), respectively; ψ is the graph aspect-ratio. We complement this positive result by showing that, for β = 1+ε, the worst-case recourse bound of any algorithm produced by our reduction is optimal. As a corollary, several key dynamic approximate matching algorithms - with poor worst-case recourse bounds - are strengthened to achieve near-optimal worst-case recourse bounds with no loss in update time.
Cite as

Noam Solomon and Shay Solomon. A Generalized Matching Reconfiguration Problem. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 57:1-57:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{solomon_et_al:LIPIcs.ITCS.2021.57,
  author =	{Solomon, Noam and Solomon, Shay},
  title =	{{A Generalized Matching Reconfiguration Problem}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{57:1--57:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.57},
  URN =		{urn:nbn:de:0030-drops-135965},
  doi =		{10.4230/LIPIcs.ITCS.2021.57},
  annote =	{Keywords: Dynamic algorithms, graph matching, reconfiguration problem, recourse bound}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.14
Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't

Authors: Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory [Stanley, 1999], in Schubert calculus [Ledoux and Malham, 2010] as well as in Enumerative combinatorics [Gasharov, 1996; Stanley, 1984; Stanley, 1999]. In recent years, they have also shown up in various incarnations in Computer Science, e.g, Quantum computation [Hallgren et al., 2000; Ryan O'Donnell and John Wright, 2015] and Geometric complexity theory [Ikenmeyer and Panova, 2017]. However, unlike some other families of symmetric polynomials like the Elementary Symmetric polynomials, the Power Symmetric polynomials and the Complete Homogeneous Symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question, and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.
Cite as

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14,
  author =	{Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth},
  title =	{{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{14:1--14:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.14},
  URN =		{urn:nbn:de:0030-drops-125660},
  doi =		{10.4230/LIPIcs.CCC.2020.14},
  annote =	{Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.66
Incidences Between Points and Curves with Almost Two Degrees of Freedom

Authors: Micha Sharir and Oleg Zlydenko

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study incidences between points and (constant-degree algebraic) curves in three dimensions, taken from a family C of curves that have almost two degrees of freedom, meaning that (i) every pair of curves of C intersect in O(1) points, (ii) for any pair of points p, q, there are only O(1) curves of C that pass through both points, and (iii) a pair p, q of points admit a curve of C that passes through both of them if and only if F(p,q)=0 for some polynomial F of constant degree associated with the problem. (As an example, the family of unit circles in ℝ³ that pass through some fixed point is such a family.) We begin by studying two specific instances of this scenario. The first instance deals with the case of unit circles in ℝ³ that pass through some fixed point (so called anchored unit circles). In the second case we consider tangencies between directed points and circles in the plane, where a directed point is a pair (p,u), where p is a point in the plane and u is a direction, and (p,u) is tangent to a circle γ if p ∈ γ and u is the direction of the tangent to γ at p. A lifting transformation due to Ellenberg et al. maps these tangencies to incidences between points and curves ("lifted circles") in three dimensions. In both instances we have a family of curves in ℝ³ with almost two degrees of freedom. We show that the number of incidences between m points and n anchored unit circles in ℝ³, 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) in both cases. We then derive a similar incidence bound, with a few additional terms, for more general families of curves in ℝ³ with almost two degrees of freedom, under a few additional natural assumptions. The proofs follow standard techniques, based on polynomial partitioning, but they face a critical novel issue involving the analysis of surfaces that are infinitely ruled by the respective family of curves, as well as of surfaces in a dual three-dimensional space that are infinitely ruled by the respective family of suitably defined dual curves. We either show that no such surfaces exist, or develop and adapt techniques for handling incidences on such surfaces. 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.
Cite as

Micha Sharir and Oleg Zlydenko. Incidences Between Points and Curves with Almost Two Degrees of Freedom. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SoCG.2020.66,
  author =	{Sharir, Micha and Zlydenko, Oleg},
  title =	{{Incidences Between Points and Curves with Almost Two Degrees of Freedom}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.66},
  URN =		{urn:nbn:de:0030-drops-122244},
  doi =		{10.4230/LIPIcs.SoCG.2020.66},
  annote =	{Keywords: Incidences, Polynomial partition, Degrees of freedom, Infinitely-ruled surfaces, Three dimensions}
}
Document
DOI: 10.4230/LIPIcs.CCC.2019.5
From DNF Compression to Sunflower Theorems via Regularity

Authors: Shachar Lovett, Noam Solomon, and Jiapeng Zhang

Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)

Abstract
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 the DNF compression result. The main approach is based on regularity of set systems and a structure-vs-pseudorandomness approach to the sunflower conjecture.
Cite as

Shachar Lovett, Noam Solomon, and Jiapeng Zhang. From DNF Compression to Sunflower Theorems via Regularity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lovett_et_al:LIPIcs.CCC.2019.5,
  author =	{Lovett, Shachar and Solomon, Noam and Zhang, Jiapeng},
  title =	{{From DNF Compression to Sunflower Theorems via Regularity}},
  booktitle =	{34th Computational Complexity Conference (CCC 2019)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-116-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{137},
  editor =	{Shpilka, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.5},
  URN =		{urn:nbn:de:0030-drops-108277},
  doi =		{10.4230/LIPIcs.CCC.2019.5},
  annote =	{Keywords: DNF sparsification, sunflower conjecture, regular set systems}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.13
Hardness vs Randomness for Bounded Depth Arithmetic Circuits

Authors: Chi-Ning Chou, Mrinal Kumar, and Noam Solomon

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
In this paper, we study the question of hardness-randomness tradeoffs for bounded depth arithmetic circuits. We show that if there is a family of explicit polynomials {f_n}, where f_n is of degree O(log^2n/log^2 log n) in n variables such that f_n cannot be computed by a depth Delta arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta-5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth Delta-5 circuits of bounded individual degree. Thus, we remove the "bounded individual degree" condition in the work of Dvir et al. at the cost of strengthening the hardness assumption to hold for polynomials of low degree. The key technical ingredient of our proof is the following property of roots of polynomials computable by a bounded depth arithmetic circuit : if f(x_1, x_2, ..., x_n) and P(x_1, x_2, ..., x_n, y) are polynomials of degree d and r respectively, such that P can be computed by a circuit of size s and depth Delta and P(x_1, x_2, ..., x_n, f) equiv 0, then, f can be computed by a circuit of size poly(n, s, r, d^{O(sqrt{d})}) and depth Delta + 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth Delta + 3 and size poly(n, s, r, d^{t}), where t is the degree of P in y. Thus, the size upper bound in the work of Dvir et al. is non-trivial when t is small but d could be large, whereas our size upper bound is non-trivial when d is small, but t could be large.
Cite as

Chi-Ning Chou, Mrinal Kumar, and Noam Solomon. Hardness vs Randomness for Bounded Depth Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chou_et_al:LIPIcs.CCC.2018.13,
  author =	{Chou, Chi-Ning and Kumar, Mrinal and Solomon, Noam},
  title =	{{Hardness vs Randomness for Bounded Depth Arithmetic Circuits}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.13},
  URN =		{urn:nbn:de:0030-drops-88765},
  doi =		{10.4230/LIPIcs.CCC.2018.13},
  annote =	{Keywords: Algebraic Complexity, Polynomial Factorization Circuit Lower Bounds, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.13
Subquadratic Algorithms for Algebraic Generalizations of 3SUM

Authors: Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave an O(n^{11/6}) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the cartesian product of three n-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: "Given n points in the plane, do three of them lie on a line?", a key problem in computational geometry. We prove that there exist bounded-degree algebraic decision trees of depth O(n^{12/7+e}) that solve 3POL, and that 3POL can be solved in O(n^2 (log log n)^{3/2} / (log n)^{1/2}) time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on o((log n)^{1/6}/(log log n)^{1/2}) constant-degree polynomial curves. This constitutes the first step towards closing the major open question of whether GPT can be solved in subquadratic time. To obtain these results, we generalize important tools - such as batch range searching and dominance reporting - to a polynomial setting. We expect these new tools to be useful in other applications.
Cite as

Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, and Noam Solomon. Subquadratic Algorithms for Algebraic Generalizations of 3SUM. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barba_et_al:LIPIcs.SoCG.2017.13,
  author =	{Barba, Luis and Cardinal, Jean and Iacono, John and Langerman, Stefan and Ooms, Aur\'{e}lien and Solomon, Noam},
  title =	{{Subquadratic Algorithms for Algebraic Generalizations of 3SUM}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.13},
  URN =		{urn:nbn:de:0030-drops-72214},
  doi =		{10.4230/LIPIcs.SoCG.2017.13},
  annote =	{Keywords: 3SUM, subquadratic algorithms, general position testing, range searching, dominance reporting, polynomial curves}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.553
Incidences between Points and Lines in Three Dimensions

Authors: Micha Sharir and Noam Solomon

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^3, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (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 as a major step in their solution of Erdos'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. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.
Cite as

Micha Sharir and Noam Solomon. Incidences between Points and Lines in Three Dimensions. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 553-568, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{sharir_et_al:LIPIcs.SOCG.2015.553,
  author =	{Sharir, Micha and Solomon, Noam},
  title =	{{Incidences between Points and Lines in Three Dimensions}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{553--568},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.553},
  URN =		{urn:nbn:de:0030-drops-51107},
  doi =		{10.4230/LIPIcs.SOCG.2015.553},
  annote =	{Keywords: Combinatorial Geometry, Algebraic Geometry, Incidences, The Polynomial Method}
}
  • Refine by Author
  • 6 Solomon, Noam
  • 3 Sharir, Micha
  • 2 Kumar, Mrinal
  • 1 Barba, Luis
  • 1 Cardinal, Jean
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Algebraic complexity theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Randomness, geometry and discrete structures

  • Refine by Keyword
  • 3 Incidences
  • 1 3SUM
  • 1 Algebraic Complexity
  • 1 Algebraic Geometry
  • 1 Algebraic independence
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 2 2020
  • 2 2021
  • 1 2015
  • 1 2017
  • 1 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact