Network profile

Jan Johannsen

Reputation

4,474

4.5k
4k
3.5k

2018
2019
2020
2021

Next tag badge

complexity-classes

127/100 score

12/20 answers

Badges

2

29

48

Newest

Steward

Next badge

108/500

Impact

108 posts edited

89 helpful flags

1,341 votes cast

6 Questions

Votes Activity Newest Views

4

votes

0

answers

105

views

Eliminating tautological axioms in tree-like $k$-DNF resolution

reference-request proof-complexity resolution

Nov 18 '19 at 8:47 Jan Johannsen 4,474

3

14

votes

2

answers

411

views

Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

cc.complexity-theory parameterized-complexity

Sep 19 '14 at 8:13 Marzio De Biasi 21.7k

6

votes

0

answers

276

views

Stronger reductions in parameterized complexity

cc.complexity-theory reference-request parameterized-complexity

Dec 2 '17 at 21:18 domotorp 13.1k

2

10

votes

4

answers

585

views

An easy case of SAT that is not easy for tree resolution

sat proof-complexity

Jan 23 '15 at 17:15 Community♦ 1

2

13

votes

1

answer

496

views

A 3-CNF formula that requires resolution width $5$

cc.complexity-theory lo.logic sat proof-complexity

Apr 13 '13 at 19:04 Community♦ 1

6

18

votes

2

answers

480

views

Uses of XORification

cc.complexity-theory reference-request boolean-functions proof-complexity

Nov 16 '11 at 23:53 Ryan Williams 25.7k

Theoretical Computer Science Stack Exchange works best with JavaScript enabled