JeffE

# 514 Actions

 2018 2017 Mar 6 awarded Yearling Feb 3 awarded Constituent Jan 29 awarded Caucus Nov 9 awarded Good Answer Oct 23 awarded Enlightened Oct 22 awarded Nice Answer Aug 13 reviewed Approve Is detecting “doubly” arithmetic progressions 3SUM-hard? Mar 28 awarded Enlightened Mar 28 awarded Nice Answer Mar 6 awarded Yearling Mar 6 reviewed Approve Are the functions always asymptotically comparable? Nov 7 awarded Good Answer May 28 comment 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR @YuvalFilmus In retrospect, sure. But that's not the easiest way to think about it. May 28 comment 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR This is a $3/2$-approximation in expectation. To get the high probability result required by the original question, you need to run this algorithm several times and return the best of the resulting colorings. May 28 answered 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR Apr 24 awarded Good Answer Mar 29 comment Reducing max flow to bipartite matching? This is the standard textbook reduction FROM bipartite matching TO maximum flow. The question is asking for a reduction in the opposite direction: FROM maximum flow TO bipartite matching. Mar 6 awarded Yearling Feb 18 awarded Nice Answer Jan 25 awarded Nice Answer