The trouble-with-paper tag has no wiki summary.
3
votes
1answer
93 views
How to find the first $k$ points of high enough level using a priority search tree?
In reading Chan's paper,
Closest Point Problems Simplified on a RAM,
the following came up as a sub-problem:
Given a set $P$ of points in the plane, and a query point $q$, find the first $k$ points ...
0
votes
0answers
48 views
Questions on “Improved Sketching of Hamming Distance with Error Correcting” by Porat and Lipsky
What is the proof of lemma 4.3 in this paper?
http://u.cs.biu.ac.il/~porately/papers/submission_24.pdf
That is, how does it follow from 4.1 and 4.2?
Also, why is the constant 8 necessary? How is it ...
2
votes
0answers
82 views
Initial paper of the Moore Neighborhood algorithm
I don't exactly know if this is the place to ask it, but I'm looking for the original paper of the Moore Neighborhood algorithm. I need to make a reference to it (or whoever came up with it). I can't ...
8
votes
1answer
154 views
question about concurrent ZK paper by Prabhakaran & Sahai
Concurrent Zero Knowledge Proofs with Logarithmic
Round-Complexity
Page numbers are from the paper itself, and not the pdf.
From page 3,
"An interactive proof system is said to be black-box ...
0
votes
0answers
154 views
Is there a typo in this paper? [closed]
I'm studying Andrew W. Moore's tutorial on Kd-Trees. On page 6-7 there is a formular (6.6) and I wonder if there is an error in it. Shouldn't there be hri^max in the bottom case?
5
votes
0answers
194 views
Can we reduce dimensions before applying high dimensional approximate nearest neighbor algorithms?
Andoni and Indyk presented a paper in FOCS 2006: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In this paper they present an algorithm for the $c$-approximate ...
5
votes
1answer
486 views
The Stalin compiler brutally optimizes, but how?
This question was first asked on Stackoverflow, but the question was closed and suggested that it should be moved to cstheory. Since compiler questions are quite rare here, I was not entirely sure. If ...
14
votes
2answers
277 views
Separation of a preprocessed polyhedron and a plane
I have serious trouble understanding one step in the paper of Dobkin and Kirkpatrick about the separation of polyhedra. I am trying to understand this version: ...
