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, 6 months
  • Last seen more than 1 year ago
12 votes
3 answers
509 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

17 votes
2 answers
622 views

Can we approximate the number of words accepted by an NFA?

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
451 views

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

2 votes
0 answers
111 views

$k$-XOR collision free families

9 votes
5 answers
1k views

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

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?

3 votes
1 answer
92 views

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

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)

9 votes
2 answers
893 views

Computing a transitive completion / path existence oracle

55 votes
18 answers
15k views

Most memorable CS paper titles

2 votes
0 answers
159 views

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

7 votes
1 answer
214 views

How to solve this generalization of binary search?

10 votes
1 answer
399 views

Maximum weight "fair" matching

3 votes
1 answer
59 views

Complexity of distributively verifying that the diameter is small

4 votes
1 answer
189 views

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

17 votes
2 answers
810 views

How small can a NFA be, compared to the minimal Unambiguous Finite Automaton (UFA) of the same regular language?

4 votes
0 answers
149 views

2-hop distributed coloring in the CONGEST model

1 vote
1 answer
85 views

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

4 votes
1 answer
229 views

What is known about computing distinct count range queries?

5 votes
1 answer
162 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''?

6 votes
3 answers
993 views

Algorithm for finding heavy hitters in a weighted stream

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

11 votes
3 answers
522 views

Are there non-constructive proofs of existence of "small" Turing machines / NFAs?

8 votes
1 answer
459 views

Competing against an optimal weighted majority in experts algorithm