Jan
18
comment What is the motivation of Levy-Prokhorov metric?
Just a sidenote: the metric you defined in #2 is the total variation distance.
Dec
13
awarded Supporter
Dec
1
awarded Nice Question
Oct
29
awarded Good Answer
Oct
28
awarded Yearling
Oct
28
awarded Yearling
Oct
12
awarded Yearling
Oct
12
awarded Yearling
Sep
9
awarded Excavator
Sep
9
revised Literature around NP vs EXPTIME
fixed link
Jul
29
awarded Popular Question
May
7
awarded Nice Question
Apr
13
revised What is the evidence for average case separation between EXP and NEXP?
added 762 characters in body
Apr
13
comment What is the evidence for average case separation between EXP and NEXP?
@PhilipWhite Normally padding arguments go the other way, e.g. $EXP \ne NEXP$ implies $P \ne NP$ but not the other way around.
Apr
13
comment What is the evidence for average case separation between EXP and NEXP?
@D.W. I didn't claim those problems are NP-complete. I meant that the existence of one-way functions implies that $AvgP \nsupseteq DistNP$ which implies that problems complete for $DistNP$ are hard in the average case.
Apr
10
comment Intersecting Complexity Classes with Advice
@HenryYuen: I think that a Language $L$ is in $(NP \cap coNP)/poly$ iff there is a language $K$ in $NP \cap coNP$ and $a_i$ advice of polynomial length s.t. $x \in L$ iff $(x, a_{|x|}) \in K$.
Apr
10
asked What is the evidence for average case separation between EXP and NEXP?
Mar
10
revised Assigning probability to membership in an NP-complete language
fixed equation
Nov
19
awarded Nice Answer
Nov
19
revised Why did the Federalist Party collapse?
added 2 characters in body
1 2 3 4 5