The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
45 views

Difference between “image patches” and “image components”

In this paper, two terms are used to refer to the same concept, at least they sound one to me. I'd like to know what is the difference between them, if any. A variety of representations used in ...
2
votes
0answers
96 views

How does part 5 of the paper “computational complexity of Minesweeper” work?

Marzio De Biasi mentioned this paper in this answer, and that paper's claim in part 5 would appear to resolve my question. However, there seems to be a significant gap in the proof. Even though one ...
3
votes
1answer
112 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
52 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
106 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
167 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 ...
6
votes
0answers
224 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 ...
9
votes
1answer
579 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
284 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: ...