Skip to main content
Share Your Experience: Take the 2024 Developer Survey
R B's user avatar
R B's user avatar
R B's user avatar
R B
  • Member for 10 years, 4 months
  • Last seen more than a month ago
55 votes
18 answers
15k views

Most memorable CS paper titles

27 votes
1 answer
2k views

Deciding emptiness of intersection of regular languages in subquadratic time

18 votes
2 answers
839 views

Bounds on the size of the smallest NFA for L_k-distinct

17 votes
2 answers
803 views

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

17 votes
4 answers
2k views

Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs

17 votes
2 answers
617 views

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

16 votes
1 answer
446 views

Can constant ambiguity reduce the state complexity of a regular languages?

15 votes
1 answer
633 views

Does PSPACE-completeness imply approximation hardness?

15 votes
2 answers
600 views

Does XOR automata (NXA) for finite languages benefit from cycles?

14 votes
4 answers
1k views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

13 votes
1 answer
651 views

Is DAG subset sum approximable?

12 votes
4 answers
4k views

Interesting results in TCS which are easily explainable to programmers without technical background

11 votes
3 answers
521 views

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

11 votes
3 answers
459 views

Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

11 votes
2 answers
1k views

For which families of graphs is Generalized Geography in $P$?

10 votes
2 answers
452 views

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

10 votes
1 answer
396 views

Maximum weight "fair" matching

10 votes
1 answer
446 views

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

9 votes
0 answers
308 views

Additive error in counting the number of 1's in a sliding window?

9 votes
1 answer
316 views

Secretary hiring game

9 votes
5 answers
1k views

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

9 votes
2 answers
886 views

Computing a transitive completion / path existence oracle

8 votes
2 answers
244 views

What is the value of this "game" (counters rebalancing)?

8 votes
1 answer
458 views

Competing against an optimal weighted majority in experts algorithm

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

8 votes
0 answers
82 views

Finding a median in a union of sets given as sorted arrays [duplicate]

8 votes
0 answers
172 views

Is 4-colors precoloring extension for planar graphs fixed parameter tractable?

8 votes
0 answers
151 views

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

7 votes
1 answer
211 views

How to solve this generalization of binary search?

7 votes
0 answers
277 views

Integer queue summation