6 Search Results for "de Zeeuw, Frank"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.59
Improved Bound for the k-Variate Elekes-Rónyai Theorem

Authors: Yaara Jahn and Orit E. Raz

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Let f ∈ ℝ[x₁,…,x_k], for k ≥ 2. For any finite sets A₁,…,A_k ⊂ ℝ, consider the set f(A₁,…,A_k): = {f(a₁,…,a_k)∣ (a₁,⋯,a_k) ∈ A₁×⋯× A_k}, that is, the image of A₁×⋯×A_k under f. Extending a theorem of Elekes and Rónyai, which deals with the case k = 2, and the result of Raz, Sharir, and De Zeeuw [Raz et al., 2018], dealing with the case k = 3, it is proved in Raz and Shem Tov [Raz and Shem{-}Tov, 2020], that for every choice of finite A₁,…, A_k ⊂ ℝ, each of size n, one has (1) |f(A₁,…,A_k)| = Ω(n^{3/2}), unless f has some degenerate special form. In this paper, we introduce the notion of a rank of a k-variate polynomial f, denoted as rank(f). Letting r = rank(f), we prove that (2) |f(A₁,…,A_k)| = Ω(n^{(5r-4)/2r-ε}) , for every ε > 0, where the constant of proportionality depends on ε and on deg(f). This improves the lower bound (1), for polynomials f for which rank(f) ≥ 3. We present an application of our main result, to lower bound the number of distinct d-volumes spanned by (d+1)-tuples of points lying on the moment curve in ℝ^d.
Cite as

Yaara Jahn and Orit E. Raz. Improved Bound for the k-Variate Elekes-Rónyai Theorem. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jahn_et_al:LIPIcs.SoCG.2026.59,
  author =	{Jahn, Yaara and Raz, Orit E.},
  title =	{{Improved Bound for the k-Variate Elekes-R\'{o}nyai Theorem}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.59},
  URN =		{urn:nbn:de:0030-drops-258663},
  doi =		{10.4230/LIPIcs.SoCG.2026.59},
  annote =	{Keywords: Polynomial Expansion, Elekes-R\'{o}nyai theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.83
Erdős’s Unit Distance Problem and Rigidity

Authors: János Pach, Orit E. Raz, and József Solymosi

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
According to a classical result of Spencer, Szemerédi, and Trotter (1984), the maximum number of times the unit distance can occur among n points in the plane is O(n^{4/3}). This is far from Erdős’s lower bound, n^{1+O(1/log log n)}, which is conjectured to be optimal. We prove a structural result for point sets with nearly n^{4/3} unit distances and use it to reduce the problem to a conjecture on rigid frameworks. This conjecture, if true, would yield the first improvement on the bound of Spencer et al. A weaker version of this conjecture has been established by Raz and Solymosi.
Cite as

János Pach, Orit E. Raz, and József Solymosi. Erdős’s Unit Distance Problem and Rigidity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 83:1-83:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pach_et_al:LIPIcs.SoCG.2026.83,
  author =	{Pach, J\'{a}nos and Raz, Orit E. and Solymosi, J\'{o}zsef},
  title =	{{Erd\H{o}s’s Unit Distance Problem and Rigidity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{83:1--83:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.83},
  URN =		{urn:nbn:de:0030-drops-258906},
  doi =		{10.4230/LIPIcs.SoCG.2026.83},
  annote =	{Keywords: Unit distance problem, Erd\H{o}s, graph rigidity, incidences, polynomial partitioning technique}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.84
Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings

Authors: Andrei Romashchenko

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings (a, b, c), there exists a string z such that each conditional Kolmogorov complexity C(a|z), C(b|z), C(c|z) is approximately half of the corresponding unconditional Kolmogorov complexity. We provide a negative answer to this question by constructing a triple (a, b, c) for which no such string z exists. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on recent bounds for point-line incidences over prime fields, obtained using tools from additive combinatorics and algebraic methods, notably results by Bourgain-Katz-Tao and Stevens-De Zeeuw. As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields.
Cite as

Andrei Romashchenko. Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 84:1-84:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{romashchenko:LIPIcs.MFCS.2025.84,
  author =	{Romashchenko, Andrei},
  title =	{{Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{84:1--84:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.84},
  URN =		{urn:nbn:de:0030-drops-241914},
  doi =		{10.4230/LIPIcs.MFCS.2025.84},
  annote =	{Keywords: Kolmogorov complexity, algorithmic information theory, communication complexity, discrete geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.8
Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets

Authors: Boris Aronov, Esther Ezra, and Micha Sharir

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

Abstract
We present subquadratic algorithms, in the algebraic decision-tree model of computation, for detecting whether there exists a triple of points, belonging to three respective sets A, B, and C of points in the plane, that satisfy a certain polynomial equation or two equations. The best known instance of such a problem is testing for the existence of a collinear triple of points in A×B×C, a classical 3SUM-hard problem that has so far defied any attempt to obtain a subquadratic solution, whether in the (uniform) real RAM model, or in the algebraic decision-tree model. While we are still unable to solve this problem, in full generality, in subquadratic time, we obtain such a solution, in the algebraic decision-tree model, that uses only roughly O(n^(28/15)) constant-degree polynomial sign tests, for the special case where two of the sets lie on one-dimensional curves and the third is placed arbitrarily in the plane. Our technique is fairly general, and applies to any other problem where we seek a triple that satisfies a single polynomial equation, e.g., determining whether A× B× C contains a triple spanning a unit-area triangle. This result extends recent work by Barba et al. [Luis Barba et al., 2019] and by Chan [Timothy M. Chan, 2020], where all three sets A, B, and C are assumed to be one-dimensional. While there are common features in the high-level approaches, here and in [Luis Barba et al., 2019], the actual analysis in this work becomes more involved and requires new methods and techniques, involving polynomial partitions and other related tools. As a second application of our technique, we again have three n-point sets A, B, and C in the plane, and we want to determine whether there exists a triple (a,b,c) ∈ A×B×C that simultaneously satisfies two real polynomial equations. For example, this is the setup when testing for the existence of pairs of similar triangles spanned by the input points, in various contexts discussed later in the paper. We show that problems of this kind can be solved with roughly O(n^(24/13)) constant-degree polynomial sign tests. These problems can be extended to higher dimensions in various ways, and we present subquadratic solutions to some of these extensions, in the algebraic decision-tree model.
Cite as

Boris Aronov, Esther Ezra, and Micha Sharir. Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.SoCG.2020.8,
  author =	{Aronov, Boris and Ezra, Esther and Sharir, Micha},
  title =	{{Testing Polynomials for Vanishing on Cartesian Products of Planar Point Sets}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.8},
  URN =		{urn:nbn:de:0030-drops-121666},
  doi =		{10.4230/LIPIcs.SoCG.2020.8},
  annote =	{Keywords: Algebraic decision tree, Polynomial partition, Collinearity testing, 3SUM-hard problems, Polynomials vanishing on Cartesian products}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.522
Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Authors: Orit E. Raz, Micha Sharir, and Frank de Zeeuw

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

Abstract
Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.
Cite as

Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 522-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.522,
  author =	{Raz, Orit E. and Sharir, Micha and de Zeeuw, Frank},
  title =	{{Polynomials Vanishing on Cartesian Products: The Elekes-Szab\'{o} Theorem Revisited}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{522--536},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.522},
  URN =		{urn:nbn:de:0030-drops-51031},
  doi =		{10.4230/LIPIcs.SOCG.2015.522},
  annote =	{Keywords: Combinatorial geometry, incidences, polynomials}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.537
Bisector Energy and Few Distinct Distances

Authors: Ben Lund, Adam Sheffer, and Frank de Zeeuw

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

Abstract
We introduce the bisector energy of an n-point set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^2). We also prove the lower bound M(n)n^2, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^a points of P, or there exist n^{8/5 - 12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{-2/5}n^{8/5}, M(n)^{-1}n^2}). This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.
Cite as

Ben Lund, Adam Sheffer, and Frank de Zeeuw. Bisector Energy and Few Distinct Distances. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 537-552, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{lund_et_al:LIPIcs.SOCG.2015.537,
  author =	{Lund, Ben and Sheffer, Adam and de Zeeuw, Frank},
  title =	{{Bisector Energy and Few Distinct Distances}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{537--552},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.537},
  URN =		{urn:nbn:de:0030-drops-51086},
  doi =		{10.4230/LIPIcs.SOCG.2015.537},
  annote =	{Keywords: Combinatorial geometry, distinct distances, incidence geometry}
}
  • Refine by Type
  • 6 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 1 2025
  • 1 2020
  • 2 2015

  • Refine by Author
  • 3 Raz, Orit E.
  • 2 Sharir, Micha
  • 2 de Zeeuw, Frank
  • 1 Aronov, Boris
  • 1 Ezra, Esther
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Information theory
  • 1 Security and privacy → Information-theoretic techniques
  • 1 Theory of computation
  • 1 Theory of computation → Communication complexity
  • Show More...

  • Refine by Keyword
  • 2 Combinatorial geometry
  • 2 incidences
  • 1 3SUM-hard problems
  • 1 Algebraic decision tree
  • 1 Collinearity testing
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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