User jbapple

54 votes

2 answers

7k views

What are the outstanding questions in purely functional data structures?

asked Sep 22, 2010 at 18:43

17 votes

0 answers

296 views

Sequences with sublogarithmic concat and approximate split

asked Apr 9, 2011 at 5:01

16 votes

2 answers

977 views

Faster join of treap-like data structures with approximately the same size

asked Jan 6, 2011 at 7:39

15 votes

2 answers

584 views

Reusing 5-independent hash functions for linear probing

asked Sep 8, 2011 at 16:07

15 votes

1 answer

306 views

Maintaining order in a list in $AC^0$ in $O(1)$ time

asked Sep 26, 2011 at 3:41

14 votes

1 answer

343 views

How much independence is required for separate chaining?

asked Mar 28, 2013 at 4:40

13 votes

2 answers

683 views

Simple balanced trees with O(1) concat?

asked Aug 16, 2010 at 22:35

12 votes

1 answer

233 views

Integer priority queue with distribution-sensitive deleteMin

asked Sep 10, 2013 at 5:58

12 votes

1 answer

151 views

Decidable theory of asymptotic growth

asked Jan 26, 2014 at 3:40

11 votes

1 answer

403 views

Strongly weight-balanced deterministic skip lists

asked Oct 2, 2010 at 19:12

9 votes

2 answers

354 views

Almost universal string hashing in $Z_{2^n}$ and sublinear space

asked Apr 9, 2013 at 4:24

8 votes

1 answer

343 views

Storing a bit vector in uninitialized memory and minimal space

asked May 30, 2013 at 16:14

8 votes

3 answers

677 views

Proving skip-lists strongly weight-balanced in expectation

asked Oct 24, 2010 at 3:03

8 votes

1 answer

183 views

Dynamic planar exact k-nearest neighbors for pathological data

asked Nov 16, 2011 at 5:46

7 votes

1 answer

230 views

Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

asked May 27, 2012 at 3:40

7 votes

2 answers

128 views

Shoup-style hashing without one-wayness

asked Dec 16, 2015 at 4:28

6 votes

0 answers

227 views

Purely functional uniquely-represented deques

asked Sep 27, 2014 at 21:35

6 votes

1 answer

303 views

Simple and cache-oblivious tries on fixed-length strings

asked Feb 24, 2011 at 5:39

5 votes

1 answer

199 views

Local updates in weight-balanced search trees

asked Sep 22, 2012 at 19:44

5 votes

0 answers

101 views

Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

asked Nov 24, 2013 at 8:25

5 votes

1 answer

153 views

Single-pass streaming quantile estimation using moments

asked Aug 19, 2015 at 4:26

4 votes

1 answer

144 views

Solving a system of sums-of-powers polynomials

asked Dec 24, 2014 at 6:29

4 votes

1 answer

138 views

Sublinear finite-precision sampling in a stream

asked May 28, 2017 at 6:26

3 votes

1 answer

247 views

Decidability of first-order theory of real closed fields with functions

asked Aug 5, 2014 at 15:41

3 votes

1 answer

981 views

How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

asked Apr 5, 2011 at 4:59

2 votes

2 answers

181 views

Keyed queues with depth queries and delete

asked Jun 17, 2011 at 4:37

Stack Exchange Network

26 Questions

What are the outstanding questions in purely functional data structures?

Sequences with sublogarithmic concat and approximate split

Faster join of treap-like data structures with approximately the same size

Reusing 5-independent hash functions for linear probing

Maintaining order in a list in $AC^0$ in $O(1)$ time

How much independence is required for separate chaining?

Simple balanced trees with O(1) concat?

Integer priority queue with distribution-sensitive deleteMin

Decidable theory of asymptotic growth

Strongly weight-balanced deterministic skip lists

Almost universal string hashing in $Z_{2^n}$ and sublinear space

Storing a bit vector in uninitialized memory and minimal space

Proving skip-lists strongly weight-balanced in expectation

Dynamic planar exact k-nearest neighbors for pathological data

Simple succinct dynamic predecessor with $O(\sqrt{n})$ redundancy in contiguous space

Shoup-style hashing without one-wayness

Purely functional uniquely-represented deques

Simple and cache-oblivious tries on fixed-length strings

Local updates in weight-balanced search trees

Dynamic 2-dimensional orthogonal range reporting in external memory and linear space

Single-pass streaming quantile estimation using moments

Solving a system of sums-of-powers polynomials

Sublinear finite-precision sampling in a stream

Decidability of first-order theory of real closed fields with functions

How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

Keyed queues with depth queries and delete