User contributions
- 17:02, 8 November 2019 (diff | hist) . . (+1) . . m Open Problems:25 (current)
- 17:02, 8 November 2019 (diff | hist) . . (+262) . . Open Problems:25 (→Update: adding KN19)
- 16:59, 8 November 2019 (diff | hist) . . (+197) . . m Bibliography
- 16:51, 13 December 2012 (diff | hist) . . (+140) . . Bibliography
- 16:50, 13 December 2012 (diff | hist) . . (+105) . . Open Problems:48
- 02:28, 12 December 2012 (diff | hist) . . (0) . . Open Problems:51
- 02:26, 12 December 2012 (diff | hist) . . (+263) . . Bibliography
- 02:24, 12 December 2012 (diff | hist) . . (+552) . . Bibliography
- 02:19, 12 December 2012 (diff | hist) . . (+922) . . N Open Problems:60 (Created page with "{{Header |title=Single-Pass Unweighted Matchings |source=dortmund12 |who=Andrew McGregor }} Suppose you have $O(n \hbox{polylog} n)$ memory and a single pass over a stream of ...")
- 02:15, 12 December 2012 (diff | hist) . . (-4) . . Bibliography
- 02:15, 12 December 2012 (diff | hist) . . (+301) . . Bibliography
- 02:12, 12 December 2012 (diff | hist) . . (+1,324) . . N Open Problems:59 (Created page with "{{Header |title=Low Expansion Encoding of Edit Distance |source=dortmund12 |who=Hossein Jowhari }} Let $T = \bigcup_{i=1}^{n} \{0,1\}^i$. For pair of strings $(x,y) \in T \tim...")
- 02:10, 12 December 2012 (diff | hist) . . (+784) . . N Open Problems:58 (Created page with "{{Header |title=Signatures for set equality |source=dortmund12 |who=Rasmus Pagh }} Given $S\subseteq\{1,..n\}$, we would like to construct a fingerprint so that later, given f...")
- 02:06, 12 December 2012 (diff | hist) . . (+684) . . Bibliography
- 02:02, 12 December 2012 (diff | hist) . . (+2,934) . . N Open Problems:57 (Created page with "{{Header |title=Coding theory in the streaming model |source=dortmund12 |who=Atri Rudra }} Consider the problem of "codeword testing" in the data stream model. In particular, ...")
- 01:51, 12 December 2012 (diff | hist) . . (+1,029) . . N Open Problems:56 (Created page with "{{Header |title=Efficient measures of ''surprisingness'' of sequences |source=dortmund12 |who=Rina Panigrahy }} Consider a sequence of iid random bits $S\in\{0,1\}^n$. '''Que...")
- 01:49, 12 December 2012 (diff | hist) . . (+4) . . Bibliography
- 01:48, 12 December 2012 (diff | hist) . . (+387) . . Bibliography
- 01:48, 12 December 2012 (diff | hist) . . (0) . . Open Problems:55
- 01:42, 12 December 2012 (diff | hist) . . (+243) . . Bibliography
- 01:40, 12 December 2012 (diff | hist) . . (+1,721) . . N Open Problems:55 (Created page with "{{Header |title=Applications of Clifford Algebras in Graph Streams |source=dortmund12 |who=He Sun }} Some of the recent results in graph streaming algorithms {{cite|KaneMSS-12...")
- 01:34, 12 December 2012 (diff | hist) . . (+1,098) . . N Open Problems:54 (Created page with "{{Header |title=Faster JL Dimensionality Reduction |source=dortmund12 |who=Jelani Nelson }} The standard Johnson-Lindenstrauss lemma states the following: for any $0<\epsilon<...")
- 01:32, 12 December 2012 (diff | hist) . . (+855) . . N Open Problems:53 (Created page with "{{Header |title=Homomorphic hash functions |source=dortmund12 |who=Ely Porat }} '''Question''': to construct a hash function $ h:\F_p^n \to \F_p^m $, where $m<n$, satisfying ...")
- 01:30, 12 December 2012 (diff | hist) . . (+733) . . N Open Problems:52 (Created page with "{{Header |title=TSP in the streaming model |source=dortmund12 |who=Christian Sohler }} We have $n$ points living in $\{1,\ldots,\Delta\}^2$ space. '''Question''': Can we appr...")
- 01:25, 12 December 2012 (diff | hist) . . (-2) . . Open Problems:51
- 01:24, 12 December 2012 (diff | hist) . . (-2) . . Open Problems:51
- 01:22, 12 December 2012 (diff | hist) . . (+1,945) . . N Open Problems:51 (Created page with "{{Header |title=``For all'' guarantee for computationally bounded adversaries |source=dortmund12 |who=Martin Strauss }} There are two types of compressed sensing guarantees,...")
