Sariel Har-Peled
  • Member for 11 years, 5 months
  • Last seen this week
Are there any counterintuitive results in theoretical computer science?
28 votes

I find the fact that network flow is polynomial time counter intuitive. It is seems much harder on first look than many NP-Hard problems. Or putting it differently, there are many results in CS where ...

View answer
What is the enlightenment I'm supposed to attain after studying finite automata?
27 votes

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely ...

View answer
Geometric problems that are NP-complete in $R^3$ but tractable in $R^2$?
Accepted answer
25 votes

Set cover by half-spaces. Given a set of points in the plane, and a set of halfplanes computing the minimum number of halfplanes covering the point sets can be solved in polynomial time in the plane. ...

View answer
What papers should everyone read?
19 votes

If I may quote Sarah Palin on this issue: "All of them". More seriously, I think most papers should not be read in the original. As time passes people figure out better way of understanding and ...

View answer
If you have a casual conversation with someone and it leads to a paper, what do you owe them?
18 votes

Apology. Never have casual conversations with people. Its rude. Also what Peter Shor said. I would also add that if you ask the question, then usually the right thing is to offer this person to be ...

View answer
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
17 votes

Fixed point theorems are all over the place... But a pretty surprising example of geometry popping from nowhere is the effective comparison result. Here, given a partial order defined over a set of $...

View answer
Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time
Accepted answer
17 votes

Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first: A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the ...

View answer
Hamiltonicity of k-regular graphs
Accepted answer
17 votes

First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number ...

View answer
What Books Should Everyone Read?
16 votes

The books by Matousek & Chazelle on Discrepancy are excellent. Almost all the books by Matousek, in fact, are worth reading to some extent. Douglas West books on Graph Theory ([1] and [2]) are ...

View answer
Algorithms from the Book.
16 votes

Computing the closest pair of points in the plane in linear time (especially because there is Omega(n log n) lower bound in the comparison model). The algorithm is originally due to Rabin, but there ...

View answer
Can we get a sorted list from a sorted matrix in $O(n^2)$
Accepted answer
15 votes

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in ...

View answer
Find a largest cube contained in the union of cuboids
Accepted answer
15 votes

Well, here is an first try silly answer... Take a plane through each face of of the rectangular boxes. This form a grid of size $O(n^3)$. It is not hard to compute for each such grid cell whether its ...

View answer
Are there subexponential algorithms for PLANAR SAT known?
Accepted answer
14 votes

Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try ...

View answer
Parameterized complexity of Hitting Set in finite VC-dimension
14 votes

I think this problem is too hard. We do not know the answer to much easier problems in this family. For example, given a set of n points in the plane, and a set of (say n) unit disks, decide if there ...

View answer
Is there a constant factor approximation algorithm for 2D rectangle coloring problem?
Accepted answer
12 votes

As suggested by the other answer, $\Omega(\log n)$ lower bound is not too hard to see. Let us do the sweeping bottom up with a horizontal line. The idea is to build components that require larger and ...

View answer
Packing rectangles into convex polygons but without rotations
12 votes

The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L_\infty$ metric) at least $1$ from each ...

View answer
Publishing short and simple results
11 votes

There are two natural strategies: Put it on the arxiv, forget about publishing it somewhere else. I have several such writeups - people see them and cite them. Go to lower venue conferences. Don't ...

View answer
Smallest axis-aligned box that contains $k$ points
11 votes

For $n$ points there are $O(n^3)$ empty boxes, see introduction of this paper http://www.cs.uwm.edu/faculty/ad/maximal.pdf. One can compute these boxes in roughly this time (see intro for refs). For ...

View answer
Does Approx Carathéodory's theorem implies dimensionality reduction
Accepted answer
11 votes

The approximate Caratheodory theorem goes back to the 60s, and probably way earlier than that (it follows for example from the mistake bound of the preceptron algorithm analysis). As for the ...

View answer
Finding witness in minkowski sum of integers
Accepted answer
11 votes

Here I am explaining how to get $O(n *\mathrm{polylog} n)$ randomized running time. We need a sequence of observations: A witness of a value $v$ is a pair of numbers $(a,b) \in A \times B$ such that $...

View answer
Covering a simple polygon with circles
Accepted answer
11 votes

Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO. One can get 1+eps approximation algorithm using sliding grids. It is natural to assume the problem is NP-Hard because ...

View answer
Examples where insight from geometry was useful for solving something completely non-geometric
11 votes

I dont think there are any examples of such things. Except for linear programming, semi-definite programming, complex numbers, large fractions of machine learning, etc. The real question is http://...

View answer
Hitting set of pairwise intersecting families
Accepted answer
11 votes

The answer is yes - the problem is still NP-Complete. for every set $S_i$ create a fake elements $e_i', e_i''$ and create a new sets $S_i' = S_i \cup \{ e_i'\}$ and $S_i'' =...

View answer
Natural (well studied) classes of graphs with treewidth $\Theta(n^\alpha)$ with $1/2 < \alpha < 1$
Accepted answer
10 votes

The intersection graph of interior disjoint balls in $\mathbb{R}^d$, should have treewidth $O(n^{1-1/d})$, if there is justice in the universe (let me think about it - yep - there is). The treewidth ...

View answer
Massive online collaboration for solving open problem in theoretical computer science
Accepted answer
10 votes

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/...

View answer
Bisecting a set of points into two optimal subsets
10 votes

If you insist on precise partition, then you need to compute all the balanced partitions of a set of points in the plane by a line (the optimal partition is a Voronoi partition, so the two point sets ...

View answer
Calculating the distance to the kth nearest neighbor for all points in the set
Accepted answer
10 votes

Here is a simple trick that might be useful. Consider a random sample that picks every point with probability 1/k. It is easy to verify that with good probability exactly one of your k nearest ...

View answer
Tool for translating PDAs to CFGs
Accepted answer
10 votes

jflap is pretty nice and can do this. See here: http://www.cs.duke.edu/csed/jflap/.

View answer
Approximation algorithms used in exact algorithms
9 votes

An example of an approximation algorithm that converges to the exact solution would be the Ellipsoid algorithm for solving LPs - if the coefficients are rationals, then one can compute a minimum ...

View answer
Paths in a weighted line arrangement
Accepted answer
9 votes

The answer is no, me think. To see why consider two lines that are a perturb copy of each other that intersect at a point p. By giving one line weight 1, and one line weight -1, we created a tiny ...

View answer