Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSubquadratic Algorithms for Algebraic Generalizations of 3SUM
70
0
0.0
(
0
)
Added by
Aur\\'elien Ooms
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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 a $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. Gro 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^{frac{12}{7}+varepsilon})$ that solve 3POL, and that 3POL can be solved in $O(n^2 {(log log n)}^frac{3}{2} / {(log n)}^frac{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)}^frac{1}{6}/{(log log n)}^frac{1}{2})$ constant-degree polynomial curves. This constitutes a 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.
rate research
Read More
We present subquadratic algorithms in the algebraic decision-tree model for several textsc{3Sum}-hard geometric problems, all of which can be reduced to the following question: Given two sets $A$, $B$, each consisting of $n$ pairwise disjoint segments in the plane, and a set $C$ of $n$ triangles in the plane, we want to count, for each triangle $Deltain C$, the number of intersection points between the segments of $A$ and those of $B$ that lie in $Delta$. The problems considered in this paper have been studied by Chan~(2020), who gave algorithms that solve them, in the standard real-RAM model, in $O((n^2/log^2n)log^{O(1)}log n)$ time. We present solutions in the algebraic decision-tree model whose cost is $O(n^{60/31+varepsilon})$, for any $varepsilon>0$. Our approach is based on a primal-dual range searching mechanism, which exploits the multi-level polynomial partitioning machinery recently developed by Agarwal, Aronov, Ezra, and Zahl~(2020). A key step in the procedure is a variant of point location in arrangements, say of lines in the plane, which is based solely on the emph{order type} of the lines, a handicap that turns out to be beneficial for speeding up our algorithm.
Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, FOCS 2015] run in $O(n^{2}log nMcdottextrm{EO} +n^{3}log^{O(1)}nM)$ time and $O(n^{3}log^{2}ncdot textrm{EO} +n^{4}log^{O(1)}n$) time respectively, where $M$ is the largest absolute value of the function (assuming the range is integers) and $textrm{EO}$ is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only $Omega(n)$, the current shortest non-deterministic proof certifying the optimum value of a function requires $Theta(n^{2})$ function evaluations. The main contribution of this paper are subquadratic SFM algorithms. For integer-valued submodular functions, we give an SFM algorithm which runs in $O(nM^{3}log ncdottextrm{EO})$ time giving the first nearly linear time algorithm in any known regime. For real-valued submodular functions with range in $[-1,1]$, we give an algorithm which in $tilde{O}(n^{5/3}cdottextrm{EO}/varepsilon^{2})$ time returns an $varepsilon$-additive approximate solution. At the heart of it, our algorithms are projected stochastic subgradient descent methods on the Lovasz extension of submodular functions where we crucially exploit submodularity and data structures to obtain fast, i.e. sublinear time subgradient updates. . The latter is crucial for beating the $n^{2}$ bound as we show that algorithms which access only subgradients of the Lovasz extension, and these include the theoretically best algorithms mentioned above, must make $Omega(n)$ subgradient calls (even for functions whose range is ${-1,0,1}$).
In the 3SUM-Indexing problem the goal is to preprocess two lists of elements from $U$, $A=(a_1,a_2,ldots,a_n)$ and $B=(b_1,b_2,...,b_n)$, such that given an element $cin U$ one can quickly determine whether there exists a pair $(a,b)in A times B$ where $a+b=c$. Goldstein et al.~[WADS2017] conjectured that there is no algorithm for 3SUM-Indexing which uses $n^{2-Omega(1)}$ space and $n^{1-Omega(1)}$ query time. We show that the conjecture is false by reducing the 3SUM-Indexing problem to the problem of inverting functions, and then applying an algorithm of Fiat and Naor [SICOMP1999] for inverting functions.
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation, and in particular, on problems with an algebraic flavor.
Consider the following distance query for an $n$-node graph $G$ undergoing edge insertions and deletions: given two sets of nodes $I$ and $J$, return the distances between every pair of nodes in $Itimes J$. This query is rather general and captures sever
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
