Denis

ENS Lyon, Lyon, France

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

top accounts reputation activity subscriptions

Problems with big open complexity gaps

cc.complexity-theory complexity-classes big-list asked Feb 26, 2015 at 12:11

cstheory.stackexchange.com

36 votes

Probabilities in a riddle involving axiom of choice

pr.probability sequences-and-series axiom-of-choice asked Dec 9, 2013 at 16:16

mathoverflow.net

31 votes

Consequences of NP=PSPACE

cc.complexity-theory complexity-classes conditional-results asked Feb 13, 2014 at 17:11

cstheory.stackexchange.com

29 votes

Nontrivial membership in NP

reductions np asked Feb 17, 2014 at 14:08

cstheory.stackexchange.com

23 votes

EXPSPACE-complete problems

cc.complexity-theory reference-request big-list expspace asked Oct 22, 2014 at 15:49

cstheory.stackexchange.com

22 votes

Circular track riddle

nt.number-theory puzzle asked Jul 19, 2020 at 15:10

mathoverflow.net

17 votes

Intermediate problems between PSPACE and EXPTIME

cc.complexity-theory complexity-classes exp-time-algorithms pspace asked Jun 9, 2017 at 13:50

cstheory.stackexchange.com

14 votes

Distance between regular languages

reference-request fl.formal-languages regular-language asked Jun 3, 2013 at 13:24

cstheory.stackexchange.com

14 votes

Büchi automata with acceptance strategy

fl.formal-languages automata-theory regular-language nondeterminism omega-language asked May 9, 2012 at 13:05

cstheory.stackexchange.com

14 votes

Faulty computers

logic-puzzle strategy liars asked Oct 6, 2014 at 23:58

puzzling.stackexchange.com

Top Answers

110

Interview riddle

math.stackexchange.com

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

cstheory.stackexchange.com

What is a limit point

math.stackexchange.com

Are there any examples of non-computable real numbers?

math.stackexchange.com

What is the smallest Turing machine where it is unknown if it halts or not?

cstheory.stackexchange.com

Most important new papers in computational complexity

cstheory.stackexchange.com

rescue operation - where is your partner?

puzzling.stackexchange.com

Essays and thoughts on mathematics

mathoverflow.net

Linear span of the empty set

math.stackexchange.com

Theoretical Computer Science vs other Sciences?

cstheory.stackexchange.com

Parameterized complexity of inclusion of regular languages

cstheory.stackexchange.com

What notable automaton models have polynomially-decidable containment?

cstheory.stackexchange.com

Are all mathematical statements true or false?

math.stackexchange.com

A simple decision problem whose decidability is not known

cstheory.stackexchange.com

Counterintuitive results for undergraduates

cstheory.stackexchange.com

Are Boolean circuits 'universal'

cstheory.stackexchange.com

Caterpillar decomposition of trees

cstheory.stackexchange.com

On the realisation of monoids as syntactic monoids of languages

cstheory.stackexchange.com

Combinatorics of a badminton tournament

cstheory.stackexchange.com

The paradox with the first uncountable ordinal

mathoverflow.net

Deterministic Büchi + its complement covers LTL?

cstheory.stackexchange.com

How to acknowledge answers of TCS in the paper?

cstheory.stackexchange.com

Useless math that became useful

mathoverflow.net

A quine in pure lambda calculus

cs.stackexchange.com

Complexity of Unknotting problems

cstheory.stackexchange.com

Proof and computational complexity

cstheory.stackexchange.com

For a specific unbounded Turing machine, is its Halting problem undecidable?

cstheory.stackexchange.com

What exactly are equivalence classes

math.stackexchange.com

Constraints on sliding windows

cstheory.stackexchange.com

Is coRE closed under concatenation?

cstheory.stackexchange.com