user avatar
user avatar
user avatar
aelguindy
  • Member for 10 years, 5 months
  • Last seen more than a week ago
  • Zürich, Switzerland
603 votes
6 answers
124k views

What's new in purely functional data structures since Okasaki?

  • 8,651
268 votes
39 answers
135k views

What Books Should Everyone Read?

  • 16.3k
228 votes
60 answers
95k views

Major unsolved problems in theoretical computer science?

  • 2,213
128 votes
11 answers
11k views

How hard is unshuffling a string?

  • 22.8k
120 votes
18 answers
9k views

Examples of the price of abstraction?

91 votes
14 answers
19k views

What kind of mathematical background is needed for complexity theory?

  • 3,741
80 votes
5 answers
4k views

Techniques for Reversing the Order of Quantifiers

  • 16.3k
72 votes
8 answers
10k views

Are runtime bounds in P decidable? (answer: no)

  • 1,496
68 votes
7 answers
4k views

Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?

42 votes
22 answers
5k views

What hierarchies and/or hierarchy theorems do you know?

  • 3,741
39 votes
5 answers
1k views

Results in Theoretical CS independent of ZFC

  • 491
37 votes
9 answers
2k views

Surprising Results in Complexity (Not on the Complexity Blog List)

  • 11.7k
34 votes
11 answers
2k views

Approximation algorithms for problems in P

  • 941
30 votes
3 answers
2k views

Justification of log f in DTIME hierarchy theorem

29 votes
1 answer
3k views

Halting problem, uncomputable sets: common mathematical proof?

  • 403
26 votes
2 answers
1k views

Complexity of factoring in number fields

  • 5,983
22 votes
2 answers
1k views

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

  • 2,015
20 votes
2 answers
3k views

What are the limits of total functional programming?

19 votes
3 answers
1k views

graphs where vertex coloring is in P but independent set is NP complete

  • 779
15 votes
3 answers
2k views

Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

  • 1,496
14 votes
1 answer
1k views

Does zero integrality gap imply zero duality gap for certain problems?

  • 779
13 votes
1 answer
542 views

Given a graph, decide if its edge connectivity is at least n/2 or not

13 votes
3 answers
746 views

Can any program be implemented mechanically?

  • 199