Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Strong 3SUM-INDEXING Conjecture is False
62
0
0.0
(
0
)
Added by
Tsvi Kopelowitz
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
The Knight Move Conjecture claims that the Khovanov homology of any knot decomposes as direct sums of some knight move pairs and a single pawn move pair. This is true for instance whenever the Lee spectral sequence from Khovanov homology to Q^2 converges on the second page, as it does for all alternating knots and knots with unknotting number at most 2. We present a counterexample to the Knight Move Conjecture. For this knot, the Lee spectral sequence admits a nontrivial differential of bidegree (1,8).
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.
Given a string $S$ of length $n$, the classic string indexing problem is to preprocess $S$ into a compact data structure that supports efficient subsequent pattern queries. In this paper we consider the basic variant where the pattern is given in compressed form and the goal is to achieve query time that is fast in terms of the compressed size of the pattern. This captures the common client-server scenario, where a client submits a query and communicates it in compressed form to a server. Instead of the server decompressing the query before processing it, we consider how to efficiently process the compressed query directly. Our main result is a novel linear space data structure that achieves near-optimal query time for patterns compressed with the classic Lempel-Ziv compression scheme. Along the way we develop several data structural techniques of independent interest, including a novel data structure that compactly encodes all LZ77 compressed suffixes of a string in linear space and a general decomposition of tries that reduces the search time from logarithmic in the size of the trie to logarithmic in the length of the pattern.
The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient pattern matching queries. Typical queries include existential queries (decide if the pattern occurs in S), reporting queries (return all positions where the pattern occurs), and counting queries (return the number of occurrences of the pattern). In this paper we consider a variant of string indexing, where the goal is to compactly represent the string such that given two patterns P1 and P2 and a gap range [alpha,beta] we can quickly find the consecutive occurrences of P1 and P2 with distance in [alpha,beta], i.e., pairs of occurrences immediately following each other and with distance within the range. We present data structures that use ~O(n) space and query time ~O(|P1|+|P2|+n^(2/3)) for existence and counting and ~O(|P1|+|P2|+n^(2/3)*occ^(1/3)) for reporting. We complement this with a conditional lower bound based on the set intersection problem showing that any solution using ~O(n) space must use tilde{Omega}}(|P1|+|P2|+sqrt{n}) query time. To obtain our results we develop new techniques and ideas of independent interest including a new suffix tree decomposition and hardness of a variant of the set intersection problem.
We prove that for any positive integers $k$ and $d$, if a graph $G$ has maximum average degree at most $2k + frac{2d}{d+k+1}$, then $G$ decomposes into $k+1$ pseudoforests $C_{1},ldots,C_{k+1}$ such that there is an $i$ such that for every connected component $C$ of $C_{i}$, we have that $e(C) leq d$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
