Reputation
19,958
Next privilege 20,000 Rep.
Access 'trusted user' tools
Badges
5 79 143
Newest
 Enlightened
Impact
~252k people reached

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?
Nov
7
answered Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
Nov
6
awarded  Enlightened
Nov
2
awarded  Nice Answer
Oct
23
comment Is there a non-deterministic linear time algorithm for CNF-SAT?
@MichaelWehar if you use a counting sort, you can sort n keys in the range [0,k] in time O(n+k) in a reasonable random access model (e.g. Random access Turing machine, where you can take O(log n) time to write down an index, then can jump to that index of the tape in 1 step). If you encode each literal as an (log n+1) bit string, then the total number of clauses and variables is at most O(n/log n), in which case O(log n)-time operations on all the literals are fine. Extending to two tape TM is not straightforward, at least with counting sort.
Oct
20
awarded  Good Answer