Michael Lampis

Member for 12 years, 11 months
Last seen this week

lamsade.dauphine.fr/~mlampis

Summary

Reputation

3,416

3.4k
3.1k
2.8k

2020
2021
2022
2023

Top tag

cc.complexity-theory

Next privilege

5,000 Rep.

Approve tag wiki edits

Badges

20

29

Newest

Nice Question

Next badge

0/1

Excavator

Answers

View all 30 answers

Score Activity Newest

15

Integer linear programming in logarithmic number of variables

Jan 28, 2015

15

Does Hadwiger conjecture imply that NP = coNP?

Apr 3, 2019

12

Inappoximability status of Max One in Three SAT for satisfiable instances

Dec 5, 2012

10

Finding number of cycles of length $k$ in a graph

Oct 24, 2013

10

Problems that are easy on unweighted graphs, but hard for weighted graphs

Feb 18, 2014

Questions

View all 7 questions

Score Activity Newest Views

46

Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?

Jan 19, 2013

19

Algorithmic advantages of pathwidth over treewidth

Nov 26, 2014

17

Clique-width expressions with logarithmic depth

Feb 10, 2014

11

Complexity of $(\Delta-1)$-coloring graphs of maximum degree $\Delta$

Feb 8

7

Is the complexity of ARC KAYLES still open?

Jun 11, 2013

Tags

View all 39 tags

cc.complexity-theory

104

Score

17

posts

graph-theory

55

Score

10

posts

graph-algorithms

55

Score

7

posts

np-hardness

43

Score

10

posts

sat

36

Score

5

posts

Reputation

+80

Is there a SETH (Strong Exponential Time Hypothesis) for CSP (Constraint Satisfaction Problem)?

+40

Do fast satisfiability algorithms imply fast algorithms for parity SAT?

+10

Clique-width expressions with logarithmic depth

+10

Clique-width expressions with logarithmic depth

Badges

View all badges

This user doesn’t have any gold badges yet.

20

silver badges

Enthusiast

Mar 31, 2013
Good Question

Jan 21, 2013
Necromancer

× 4

Dec 10, 2017

29

bronze badges

Self-Learner

Jun 18, 2015
Curious

Jan 2, 2023
Revival

× 2

Dec 5, 2014

Accounts

Theoretical Computer Science

3,416
20
29

Computer Science

101
1

101
1

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast

223

upvotes

20

downvotes

68

question votes

175

answer votes