Data Structures and Algorithms (cs.DS)

  • PDF
    In the communication problem $\mathbf{UR}$ (universal relation) [KRW95], Alice and Bob respectively receive $x$ and $y$ in $\{0,1\}^n$ with the promise that $x\neq y$. The last player to receive a message must output an index $i$ such that $x_i\neq y_i$. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly $\Theta(\min\{n, \log(1/\delta)\log^2(\frac{n}{\log(1/\delta)})\})$ bits for failure probability $\delta$. Our lower bound holds even if promised $\mathop{support}(y)\subset \mathop{support}(x)$. As a corollary, we obtain optimal lower bounds for $\ell_p$-sampling in strict turnstile streams for $0\le p < 2$, as well as for the problem of finding duplicates in a stream. Our lower bounds do not need to use large weights, and hold even if it is promised that $x\in\{0,1\}^n$ at all points in the stream. Our lower bound demonstrates that any algorithm $\mathcal{A}$ solving sampling problems in turnstile streams in low memory can be used to encode subsets of $[n]$ of certain sizes into a number of bits below the information theoretic minimum. Our encoder makes adaptive queries to $\mathcal{A}$ throughout its execution, but done carefully so as to not violate correctness. This is accomplished by injecting random noise into the encoder's interactions with $\mathcal{A}$, which is loosely motivated by techniques in differential privacy. Our correctness analysis involves understanding the ability of $\mathcal{A}$ to correctly answer adaptive queries which have positive but bounded mutual information with $\mathcal{A}$'s internal randomness, and may be of independent interest in the newly emerging area of adaptive data analysis with a theoretical computer science lens.
  • PDF
    This thesis is in the area called computational social choice which is an intersection area of algorithms and social choice theory.
  • PDF
    Let $G$ be an $n$-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of $G$ with minimum weight and (2) a~cycle of $G$ with minimum weight. The best previously known algorithm for the former problem, running in $O(n\log^3 n)$ time, can be obtained from the algorithm of \Lacki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the $O(n\log^3 n)$-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in $O(n\log n\log\log n)$ time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an $O(n\log\log n)$-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.
  • PDF
    We initiate the study of distance-sensitive hashing, a generalization of locality-sensitive hashing that seeks a family of hash functions such that the probability of two points having the same hash value is a given function of the distance between them. More precisely, given a distance space $(X, \text{dist})$ and a "collision probability function" (CPF) $f\colon \mathbb{R}\rightarrow [0,1]$ we seek a distribution over pairs of functions $(h,g)$ such that for every pair of points $x, y \in X$ the collision probability is $\Pr[h(x)=g(y)] = f(\text{dist}(x,y))$. Locality-sensitive hashing is the study of how fast a CPF can decrease as the distance grows. For many spaces $f$ can be made exponentially decreasing even if we restrict attention to the symmetric case where $g=h$. In this paper we study how asymmetry makes it possible to achieve CPFs that are, for example, increasing or unimodal. Our original motivation comes from annulus queries where we are interested in searching for points at distance approximately $r$ from a query point, but we believe that distance-sensitive hashing is of interest beyond this application.

Recent comments

Māris Ozols Feb 21 2017 15:35 UTC

I'm wondering if this result could have any interesting consequences for Hamiltonian complexity. The LCL problem sounds very much like a local Hamiltonian problem, with the run-time of an LCL algorithm corresponding to the range of local interactions in the Hamiltonian.

Maybe one caveat is that thi

...(continued)
Zoltán Zimborás Jan 12 2017 20:38 UTC

Here is a nice description, with additional links, about the importance of this work if it turns out to be flawless (thanks a lot to Martin Schwarz for this link): [dichotomy conjecture][1].

[1]: http://processalgebra.blogspot.com/2017/01/has-feder-vardi-dichotomy-conjecture.html

Māris Ozols Oct 21 2016 21:06 UTC

Very nice! Now we finally know how to fairly cut a cake in a finite number of steps! What is more, the number of steps is expected to go down from the whopping $n^{n^{n^{n^{n^n}}}}$ to just barely $n^{n^n}$. I can't wait to get my slice!

https://www.quantamagazine.org/20161006-new-algorithm-solve

...(continued)
Ashley Apr 21 2015 18:42 UTC

Thanks for the further comments and spotting the new typos. To reply straight away to the other points:

First, the resulting states might as well stay in the same bin (even though, as you rightly note, the bins no longer correspond to the same bit-strings as before). All that matters is that the

...(continued)
Perplexed Platypus Apr 21 2015 14:55 UTC

Thanks for updating the paper so promptly. The updated version addresses all my concerns so far. However I noticed a few extra (minor) things while reading through it.

On page 15, last step of 2(b): if $|\psi_r\rangle$ and $|\psi_t\rangle$ were in the same bin but the combination operation failed

...(continued)
Ashley Apr 20 2015 16:27 UTC

Thank you for these very detailed and helpful comments. I have uploaded a new version of the paper to the arXiv to address them, which should appear tomorrow. I will reply to the comments in more detail (and justify the cases where I didn't modify the paper as suggested) when I receive them through

...(continued)
Perplexed Platypus Apr 13 2015 22:37 UTC

**Summary and recommendation**

This paper considers a $d$-dimensional version of the problem of finding a given pattern within a text, for random patterns and text. The text is assumed to be picked uniformly at random and has size $n^d$ while the pattern has size $m^d$ and is either uniformly ran

...(continued)
Ashley Apr 12 2015 13:01 UTC

Thanks for the clarification. In fact it seems that I do have this option switched on, with the correct author identifier, so I'm not sure why I didn't get an email about these comments.

Perplexed Platypus Apr 10 2015 13:18 UTC

Hi Ashley,

Thanks for your reply, it was very helpful! I thought about e-mailing you but I wanted to preserve my confidentiality as a reviewer. Also, I wanted to see if it is feasible to use SciRate as a platform for interacting with authors during the review process.

I encourage you (and **ot

...(continued)
Ashley Apr 09 2015 20:03 UTC

Hi,

Thank you for your very detailed comments / questions about the technical points in this paper. I did happen to check Scirate today but in general (as I suspect with many other people) I don't check it regularly, so for reliable replies it's better just to email me. To reply to your questions i

...(continued)