More Like this

1. Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2024.38  

   Chang, Hsien-Chih; Gao, Jie; Le, Hung (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   Finding the diameter of a graph in general cannot be done in truly subquadratic assuming the Strong Exponential Time Hypothesis (SETH), even when the underlying graph is unweighted and sparse. When restricting to concrete classes of graphs and assuming SETH, planar graphs and minor-free graphs admit truly subquadratic algorithms, while geometric intersection graphs of unit balls, congruent equilateral triangles, and unit segments do not. Unit-disk graphs is one of the major open cases where the complexity of diameter computation remains unknown. More generally, it is conjectured that a truly subquadratic time algorithm exists for pseudo-disk graphs where each pair of objects has at most two intersections on the boundary. In this paper, we show a truly-subquadratic algorithm of running time O^~(n^{2-1/18}), for finding the diameter in a unit-disk graph, whose output differs from the optimal solution by at most 2. This is the first algorithm that provides an additive guarantee in distortion, independent of the size or the diameter of the graph. Our algorithm requires two important technical elements. First, we show that for the intersection graph of pseudo-disks, the graph VC-dimension - either of k-hop balls or the distance encoding vectors - is 4. This contrasts to the VC dimension of the pseudo-disks themselves as geometric ranges (which is known to be 3). Second, we introduce a clique-based r-clustering for geometric intersection graphs, which is an analog of the r-division construction for planar graphs. We also showcase the new techniques by establishing new results for distance oracles for unit-disk graphs with subquadratic storage and O(1) query time. The results naturally extend to unit L₁ or L_∞-disks and fat pseudo-disks of similar size. Last, if the pseudo-disks additionally have bounded ply, we have a truly subquadratic algorithm to find the exact diameter. 

   more » « less
2. SOME REFINED RESULTS ON THE MIXED LITTLEWOOD CONJECTURE FOR PSEUDO-ABSOLUTE VALUES

   https://doi.org/10.1017/s1446788718000198  

   LIU, WENCAI (August 2019, Journal of the Australian Mathematical Society)

   In this paper, we study the mixed Littlewood conjecture with pseudo-absolute values. For any pseudo-absolute-value sequence $${\mathcal{D}}$$ , we obtain a sharp criterion such that for almost every $$\unicode[STIX]{x1D6FC}$$ the inequality $$\begin{eqnarray}|n|_{{\mathcal{D}}}|n\unicode[STIX]{x1D6FC}-p|\leq \unicode[STIX]{x1D713}(n)\end{eqnarray}$$ has infinitely many coprime solutions $$(n,p)\in \mathbb{N}\times \mathbb{Z}$$ for a certain one-parameter family of $$\unicode[STIX]{x1D713}$$ . Also, under a minor condition on pseudo-absolute-value sequences $${\mathcal{D}}_{1},{\mathcal{D}}_{2},\ldots ,{\mathcal{D}}_{k}$$ , we obtain a sharp criterion on a general sequence $$\unicode[STIX]{x1D713}(n)$$ such that for almost every $$\unicode[STIX]{x1D6FC}$$ the inequality $$\begin{eqnarray}|n|_{{\mathcal{D}}_{1}}|n|_{{\mathcal{D}}_{2}}\cdots |n|_{{\mathcal{D}}_{k}}|n\unicode[STIX]{x1D6FC}-p|\leq \unicode[STIX]{x1D713}(n)\end{eqnarray}$$ has infinitely many coprime solutions $$(n,p)\in \mathbb{N}\times \mathbb{Z}$$ . 

   more » « less
3. Algorithmic Thresholds for Refuting Random Polynomial Systems

   https://doi.org/10.1137/1.9781611977073.49  

   Hsieh, Tim; Kothari, Pravesh K. (January 2022, Proceedings of the annual ACMSIAM symposium on discrete algorithms)

   Consider a system of m polynomial equations {pi(x)=bi}i≤m of degree D≥2 in n-dimensional variable x∈ℝn such that each coefficient of every pi and bis are chosen at random and independently from some continuous distribution. We study the basic question of determining the smallest m -- the algorithmic threshold -- for which efficient algorithms can find refutations (i.e. certificates of unsatisfiability) for such systems. This setting generalizes problems such as refuting random SAT instances, low-rank matrix sensing and certifying pseudo-randomness of Goldreich's candidate generators and generalizations. We show that for every d∈ℕ, the (n+m)O(d)-time canonical sum-of-squares (SoS) relaxation refutes such a system with high probability whenever m≥O(n)⋅(nd)D−1. We prove a lower bound in the restricted low-degree polynomial model of computation which suggests that this trade-off between SoS degree and the number of equations is nearly tight for all d. We also confirm the predictions of this lower bound in a limited setting by showing a lower bound on the canonical degree-4 sum-of-squares relaxation for refuting random quadratic polynomials. Together, our results provide evidence for an algorithmic threshold for the problem at m≳O˜(n)⋅n(1−δ)(D−1) for 2nδ-time algorithms for all δ. 

   more » « less
4. Sparse Bounded Hop-Spanners for Geometric Intersection Graphs

   https://doi.org/10.4230/LIPIcs.SoCG.2025.17  

   Bhore, Sujoy; Chan, Timothy M; Huang, Zhengcheng; Smorodinsky, Shakhar; Tóth, Csaba D (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Aichholzer, Oswin; Wang, Haitao (Ed.)

   We present new results on 2- and 3-hop spanners for geometric intersection graphs. These include improved upper and lower bounds for 2- and 3-hop spanners for many geometric intersection graphs in ℝ^d. For example, we show that the intersection graph of n balls in ℝ^d admits a 2-hop spanner of size O^*(n^{3/2 - 1/(2(2⌊d/2⌋ + 1))}) and the intersection graph of n fat axis-parallel boxes in ℝ^d admits a 2-hop spanner of size O(n log^{d+1}n). Furthermore, we show that the intersection graph of general semi-algebraic objects in ℝ^d admits a 3-hop spanner of size O^*(n^{3/2 - 1/(2(2D-1))}), where D is a parameter associated with the description complexity of the objects. For such families (or more specifically, for tetrahedra in ℝ³), we provide a lower bound of Ω(n^{4/3}). For 3-hop and axis-parallel boxes in ℝ^d, we provide the upper bound O(n log ^{d-1}n) and lower bound Ω(n ({log n}/{log log n})^{d-2}). 

   more » « less
5. Fast Algorithms for Geometric Consensuses

   Har-Peled, Sariel; Jones, Mitchell (June 2020, 36th International Symposium on Computational Geometry, SoCG 2020)

   Cabello, Sergio; Chen, Danny (Ed.)

   Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others. 

   more » « less