As of May 31, 2023, we have updated our Code of Conduct.
Kaveh's user avatar
Kaveh's user avatar
Kaveh's user avatar
Kaveh
  • Member for 11 years, 3 months
  • Last seen more than a week ago
40 votes
7 answers
4k views

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

32 votes
1 answer
2k views

Rice's theorem for non-semantic properties

21 votes
1 answer
11k 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
344 views

Extension of SQL capturing $\mathsf{P}$

16 votes
1 answer
2k views

Universal simulation of Turing machines

15 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
687 views

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

13 votes
1 answer
365 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
249 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?

6 votes
1 answer
714 views

Inductive vs. recursive definition

4 votes
2 answers
244 views

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

3 votes
1 answer
104 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
82 views

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