Reputation
Next privilege 25,000 Rep.
Access to site analytics
Badges
5 80 144
Newest
 Good Answer
Impact
~259k people reached

Dec
9
comment Are ill-posed inverse problems in NP?
You could add an extra parameter k and ask if there is an "estimation" with value k (or within a constant factor of k) then it becomes a decision problem. But I am not sure of how you formalize "estimation" and I am not sure how you would check the answer. Perhaps you just want to show such problems are NP-hard? (E.g. if you can solve them you can solve SAT)
Nov
29
reviewed Close Empty sudoku and NP-completeness
Nov
22
comment Finding the number of independent rows of a matrix
Rank is computable in $n^{2.373}$ operations. Unclear to me that reduced echelon form has also this operation count.
Nov
12
awarded  Enlightened
Nov
12
awarded  Enlightened
Nov
12
awarded  Nice Answer
Nov
12
awarded  Nice Answer
Nov
12
answered Potentially equal complexity classes without known contradictory relativizations
Nov
12
comment How is the MA version of SETH proven to be false?
Not a silly question! Short answer is that I don't know yet.
Nov
11
awarded  Good Answer
Nov
10
comment How is the MA version of SETH proven to be false?
Actually I will say that what I prove is much stronger than: "there is a $1.9^n$ time Merlin-Arthur protocol for refuting k-TAUT", i.e., unsatisfiable k-CNF formulas. You can get about $2^{n/2}$ time for refuting any UNSAT circuit of sublinear depth, as far as I can tell. But as I said, the paper is coming soon.
Nov
10
comment How is the MA version of SETH proven to be false?
I will post a paper in a public forum...
Nov
10
comment How is the MA version of SETH proven to be false?
A paper is coming soon. Thanks for your patience.
Nov
10
comment Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
you're welcome!
Nov
9
awarded  Nice Answer
Nov
8
comment Does the isomorphism conjecture imply exponential lower bounds on witnesses density?
Right, you have to be careful how you formulate the conjecture to avoid trivial counterexamples. Googling revealed to me that I am not the first, so I suggest reading the work of people who have thought about this for more than 10 minutes :)
Nov
8
awarded  Nice Answer
Nov
8
reviewed Close The most applicable areas in Theoretical Computer Science
Nov
8
reviewed Close Reduction from Vertex Cover to Max-Cut?
Nov
7
answered Does the isomorphism conjecture imply exponential lower bounds on witnesses density?