New answers tagged ds.algorithms
2
I believe I can partially answer your question as to why the bounds of $\{-n^3, ..., n^3\}$ are justified.
This paper by Pătraşcu mentions that for 3SUM over any bounded universe of integers of size $u >> n^3$, the universe size can be hashed down to $O(n^3)$ while maintaining the expected $O(n^2)$ run time for 3SUM. Therefore, to prove that 3SUM can ...
3
The following excellent video:
https://www.youtube.com/watch?v=YRiyqc99kd0&t=2661s
and this one:
https://www.youtube.com/watch?v=x-HskkxUuVI&t=1965s
Deals with this issue and Fine Grained Approach to Complexity in general.
9
I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of ...
5
The smaller this upper bound is, the easier the problem becomes. In particular, if the range is $m$, then the problem can be solved in $O(m \log m)$ time using FFT. It is impressive/interesting that the authors were able to show that the problem is still quadratically nasty for numbers that are "slightly" larger than quadratic.
5
EDIT: Added an answer meeting the unique-sum requirement.
Lemma 1. The problem is NP-hard by reduction from 3-CNF-SAT, even if the maximum is required to be unique.
Proof. Here's the reduction. First we describe the reduction to the problem without the requirement that the maximum is unique.
Fix a 3-CNF-SAT instance $\phi$. Assume WLOG that $\phi$ has more ...
3
Here's a poly-time dynamic-programming algorithm.
Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm.
Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$.
For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows. Consider the problem restricted to the first $t$ time slots. (That is, ...
0
You question is very vague. Let's give it a try.
Let $X_1,\ldots,X_n$ be drawn ii from the uniform distribution on $[-1,1]$. For every $\epsilon \ge e^{-n/(2C)}$. With probability at least $1-\exp(-(n/2-C\log(1/\epsilon))^2/(2n))$ the following holds:
For ever $x \in [-1/2,1/2]$, there exists $S \subseteq \{1,\ldots,n\}$ such that $|\sum_{i \in S}X_i - x|...
Top 50 recent answers are included
