Stack Exchange

Denis

ENS Lyon, Lyon, France

http://perso.ens-lyon.fr/denis.kuperberg

top accounts reputation activity favorites subscriptions
Top Questions
32 votes

Problems with big open complexity gaps

cc.complexity-theory complexity-classes big-list asked Feb 26 '15 at 12:11
cstheory.stackexchange.com

30 votes

Consequences of NP=PSPACE

cc.complexity-theory complexity-classes conditional-results asked Feb 13 '14 at 17:11
cstheory.stackexchange.com

28 votes

Nontrivial membership in NP

reductions np asked Feb 17 '14 at 14:08
cstheory.stackexchange.com

23 votes

EXPSPACE-complete problems

cc.complexity-theory reference-request big-list expspace asked Oct 22 '14 at 15:49
cstheory.stackexchange.com

23 votes

Probabilities in a riddle involving axiom of choice

pr.probability sequences-and-series axiom-of-choice asked Dec 9 '13 at 16:16
mathoverflow.net

16 votes

Intermediate problems between PSPACE and EXPTIME

cc.complexity-theory complexity-classes exp-time-algorithms pspace asked Jun 9 '17 at 13:50
cstheory.stackexchange.com

14 votes

Büchi automata with acceptance strategy

fl.formal-languages automata-theory regular-language nondeterminism asked May 9 '12 at 13:05
cstheory.stackexchange.com

13 votes

Distance between regular languages

reference-request fl.formal-languages regular-language asked Jun 3 '13 at 13:24
cstheory.stackexchange.com

13 votes

Faulty computers

logic-puzzle strategy liars asked Oct 6 '14 at 23:58
puzzling.stackexchange.com

11 votes

Implementation of surreal numbers for games

reference-request gt.game-theory implementation board-games combinatorial-game-theory asked Oct 3 '14 at 11:56
cstheory.stackexchange.com

1 2

Top Answers
109
Interview riddle
math.stackexchange.com

44
Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?
cstheory.stackexchange.com

32
What is the smallest Turing machine where it is unknown if it halts or not?
cstheory.stackexchange.com

29
Are there any examples of non-computable real numbers?
math.stackexchange.com

25
Most important new papers in computational complexity
cstheory.stackexchange.com

23
rescue operation - where is your partner?
puzzling.stackexchange.com

22
Essays and thoughts on mathematics
mathoverflow.net

16
What is a limit point
math.stackexchange.com

15
Parameterized complexity of inclusion of regular languages
cstheory.stackexchange.com

13
A simple problem whose decidability is not known
cstheory.stackexchange.com

13
What notable automaton models have polynomially-decidable containment?
cstheory.stackexchange.com

13
Are all mathematical statements true or false?
math.stackexchange.com

12
Linear span of the empty set
math.stackexchange.com

12
On the realisation of monoids as syntactic monoids of languages
cstheory.stackexchange.com

12
Caterpillar decomposition of trees
cstheory.stackexchange.com

12
Counterintuitive results for undergraduates
cstheory.stackexchange.com

11
The paradox with the first uncountable ordinal
mathoverflow.net

10
Deterministic Büchi + its complement covers LTL?
cstheory.stackexchange.com

9
Are Boolean circuits 'universal'
cstheory.stackexchange.com

9
A quine in pure lambda calculus
cs.stackexchange.com

8
What exactly are equivalence classes
math.stackexchange.com

8
Is the game 2048 always solveable?
math.stackexchange.com

7
Have I negated the statement “for every prime number $p$, $p+7$ is composite” correctly?
math.stackexchange.com

7
Useless math that became useful
mathoverflow.net

7
Context-free language and regular expressions
cs.stackexchange.com

7
If L is a non-regular language over {a}, are all Myhill-Nerode classes singletons?
cs.stackexchange.com

7
Stephen Hawking's impact on computer science
cstheory.stackexchange.com

7
For a specific unbounded Turing machine, is its Halting problem undecidable?
cstheory.stackexchange.com

7
When $\lim_{x \to\infty} f(x)$ exists and $\lim_{x \to\infty} f'(x) = 0$, can $\lim_{x \to\infty} f''(x) \neq 0$?
math.stackexchange.com

7
decidability of fullness of intersection of a CSL with a regular language
cstheory.stackexchange.com

1 2