Skip to main content
R B's user avatar
R B's user avatar
R B's user avatar
R B
  • Member for 10 years, 5 months
  • Last seen more than a month ago
8 votes
0 answers
151 views

What is the least compressible probability distribution? (under entropy constraint, for an expected squared error metric)

10 votes
1 answer
447 views

Is subtractive dithering the optimal algorithm for sending a real number using one bit?

2 votes
0 answers
108 views

$k$-XOR collision free families

6 votes
1 answer
269 views

What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

2 votes
1 answer
174 views

How many samples are needed to reconstruct a path?

1 vote
1 answer
122 views

How to play the following game? (placing balls into bins)

1 vote
0 answers
73 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

2 votes
0 answers
158 views

What is the competitive ratio of a $d$-way associative LRU cache?

3 votes
1 answer
92 views

What is the maximal load of a "latency-bounded" Cuckoo Hash?

4 votes
1 answer
188 views

Probability of a $k$-path in a random graph

7 votes
1 answer
213 views

How to solve this generalization of binary search?

3 votes
1 answer
59 views

Complexity of distributively verifying that the diameter is small

4 votes
0 answers
148 views

2-hop distributed coloring in the CONGEST model

9 votes
5 answers
1k views

W[1]-hard problems with FPT time approximation algorithms

1 vote
1 answer
81 views

Does the following 2-rounds distributed algorithm approximates a maximal matching well?

5 votes
1 answer
161 views

What is known about learning a maximal independent set in a (very) sparse graph?

4 votes
0 answers
98 views

How to construct an $(n,m,k)$ ``separating set''?

4 votes
1 answer
229 views

What is known about computing distinct count range queries?

1 vote
0 answers
64 views

What is known about data structures for encoding a set while considering approximate Rank queries?

6 votes
1 answer
400 views

How much memory is needed for counting distinct elements in a stream exactly with high probability

5 votes
0 answers
105 views

Constructing a large bit-vector set with the following property

7 votes
1 answer
394 views

Complexity of "destroying" the graph's minimum spanning tree weight

6 votes
2 answers
267 views

Parametrized complexity of the 2-Long Paths Problem

2 votes
2 answers
331 views

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

8 votes
3 answers
274 views

Showing that interval-sum queries on a binary array can not be done using linear space and constant time

3 votes
0 answers
186 views

Finding median in a changing array

8 votes
1 answer
458 views

Competing against an optimal weighted majority in experts algorithm

6 votes
0 answers
119 views

Lower bounds for randomized frequency estimation algorithms

4 votes
0 answers
71 views

Constructing a bad sequence for counter algorithm

6 votes
3 answers
991 views

Algorithm for finding heavy hitters in a weighted stream