Stack Exchange

Jan Johannsen

Munich, Germany

TCS researcher at LMU Munich. I am interested in computational complexity and logic, especially where the two intersect. My main field of work is propositional proof complexity.

top accounts reputation activity bookmarks subscriptions
Top Questions
Top Answers
41
Which (non-Earth) planet appears in the most Star Trek episodes?
scifi.stackexchange.com

21
Minimum True Monotone 3SAT
cstheory.stackexchange.com

19
Has there been any research on $k$-SAT above the satisfiability threshold?
cstheory.stackexchange.com

18
Entscheidungsproblem vs. Unvollständigkeitssatz (soft question)
cstheory.stackexchange.com

16
Theoretical explanations for practical success of SAT solvers?
cstheory.stackexchange.com

16
$\mathsf{FP}^{\mathsf{NP}[\log n]}$ versus $\mathsf{FP}^{\mathsf{NP}||}$
cstheory.stackexchange.com

15
Golden ratio or Pi in the running time
cstheory.stackexchange.com

15
What are the compelling reasons for believing $L\neq P$?
cstheory.stackexchange.com

15
What is an equivalent definition of mP/poly in terms of a Turing machine?
cstheory.stackexchange.com

14
Statements that imply $\mathbf{P}\neq \mathbf{NP}$
cstheory.stackexchange.com

14
Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$
cstheory.stackexchange.com

14
Who was the candy man Riff Raff was expecting?
scifi.stackexchange.com

14
Proof Complexity of a Proof or Disproof of P = NP
cs.stackexchange.com

12
When have we found better bounds for known algorithms?
cstheory.stackexchange.com

11
Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
cstheory.stackexchange.com

11
What is the best known FPT result for 3-hitting set?
cstheory.stackexchange.com

10
Are there any propositional proof systems which are not Cook-Reckhow proof systems?
cstheory.stackexchange.com

10
Why is the circuit class AC0 unavoidable?
cstheory.stackexchange.com

9
How often is the ECCC queue cleared?
cstheory.stackexchange.com

9
Do Higher-Order Functions provide more power to Functional Programming?
cstheory.stackexchange.com

9
Spinal Tap: Units confusion in building Stonehenge stage prop
musicfans.stackexchange.com

8
Ruzzo-Simon-Tompa oracle access mechanism
cstheory.stackexchange.com

8
Well known classes of boolean formulas that require exponentially long resolution proofs
cstheory.stackexchange.com

8
Well known classes of boolean formulas that require exponentially long resolution proofs
cstheory.stackexchange.com

8
Set of functions computable in polynomial time
cstheory.stackexchange.com

8
Simply-stated restriction on imperative programming language that captures the elementary functions?
cstheory.stackexchange.com

8
Does rock + rap/hip-hop genre have a name?
musicfans.stackexchange.com

8
Graph theoretic restriction to Proofs in Proof Complexity Theory
cstheory.stackexchange.com

7
Semi-decidable problems with linear bound
cs.stackexchange.com

7
Boolean circuits which correspond to L/poly
cstheory.stackexchange.com

1 2