Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 12 years, 2 months
  • Last seen this week
40 votes
7 answers
4k views

Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

33 votes
1 answer
2k views

Rice's theorem for non-semantic properties

21 votes
1 answer
12k views

Easy reduction from 3SAT to Hamiltonian path problem

21 votes
3 answers
1k views

How to formulate a computational problem rigorously?

20 votes
3 answers
350 views

Extension of SQL capturing $\mathsf{P}$

17 votes
1 answer
2k views

Universal simulation of Turing machines

16 votes
1 answer
1k views

Easy to state open problems in computability theory

15 votes
3 answers
4k views

An efficient data structure supporting Insert, Delete, and MostFrequent

14 votes
1 answer
746 views

Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$

13 votes
1 answer
381 views

Proving the security of Nisan-Wigderson pseudo-random number generator

11 votes
1 answer
5k views

Short and slick proof of the strong duality theorem for linear programming

10 votes
0 answers
253 views

Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

8 votes
1 answer
1k views

Is there a continuous hash?

7 votes
1 answer
738 views

Inductive vs. recursive definition

4 votes
2 answers
251 views

Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?

3 votes
1 answer
133 views

Number of grid points in d-dimensional sphere of radius r

3 votes
1 answer
1k views

What is the probability of friendship conditioned on the number of mutual friends

2 votes
0 answers
84 views

Does a function distribute over lists or does it commute with them?

1 vote
0 answers
94 views

Can we compute most significant digit of a binary number in O(1) on RAM model?