Fractional Problems: 2.1-colorable, 2.8-SAT

Some graphs are 2-colorable, some graphs are 3-colorable, some graphs are...Does it make sense to say that a graph is 2.1-colorable? It does!(Source_ Factional Graph Theory by Schneinerman and Ullman-- I saw a talk on this by Jim Propp a long time ago.)

Def 1: A graph is (a,b)-colorable (with a \le b) if you can assign to every vertex a set of a numbers from {1,...,b} such that if u and v are adjacent then the set of numbers are disjoint. Note that k-colorable is (1,k)-colorable. Let chi_b(G) be the least a such that G is (a,b)-col.
 The fractional chrom num of G is lim_{b-->infinity} chi_b(G)/b.

Def 3:  We restate the ordinary Chrom Number problem as an integer program (and NOT by using that
Chrom Num \le SAT \le IP).  In fact, our Int Prog will be LARGE. For every ind set I of G we have a 0-1 valued var x_I which will be 1 iff x_I is all one color. We want to minimize \Sum_I x_I with the constraint that, for every vertex v in the graph. sum_{v in I} x_I \ge 1, so every vertex is colored.
: Fractional Chrom number is what you get if you relax the above IP to an LP with x_I in [0,1] instead of {0,1}.

Defs 1 and 2  turn out to be equiv. The wikipedia entry on Fractional Chromatic Number (see here) is pretty good and has some applications to real world things.

QUESTION: 2-col is in P, 3-col is NPC. What about, say, 2.1-col. It turns out that, for every c>2, c-col is NPC.

Open question (which Jim Propp used to begin his lecture): Every planar graph is 5-col has an EASY proof. Every planar graph is 4-col has a HARD (or at least tedious) proof. Is there a nice proof that every planar graph is (say) 4.5-colorable? The answer is Yes, Every planar graph is 4.5 colorable.  I blogged on it here.

Are there other fractional problems related to NPC problems. YES- at a Dagstuhl there was a paper on (2+epsilon)-SAT. (by Austrin, Guruswami, Hastad) (see here).

What is fractional SAT? Lets recall ordinary k-SAT: every clause has k literals and you need to make at least one of them true. What if you wanted to make at least 2 of them true? (a/b)-SAT is if every clause has exactly b literals and you want an assignment that makes at least a in each clause true.

GOOD NEWS: for all epsilon, (2+epsilon) is NP-complete. Its not so much good that its true, but its good that its known.

BAD NEWS: The proof is hard, uses lots of tools.

ODD NEWS: The speaker said that they PROVED there was no easy proof.

I think its worth having your students try to DEFINE these terms on their own. The NPC proofs may be over their heads (they may be over my head), but the definitions are nice and the students might be able to derive them.

QUESTION: Do other NPC problems have Fractional versions? I would think yes. This could lead to a host of open problems OR perhaps they have already been asked. If you know of any, please comment.

How valuable is a Fields Medal?

(Johan Hastad won the Knuth Prize! The below post was written before I knew that but has a mild connection to it. See here for more info on the Hastad winning it, or see Lance's tweet, or see Boaz's blog post here. There will prob be other blogs about it as well. ADDED LATER: Lipton and Regan have a post on this here.)




The Fields Medal was recently awarded to

Caucher Birkar

Alessio Figalli

Peter Scholze

Akshay Benkatesh

I was going to try to give one sentence about what they did, but Wikipedia does a better job than I ever could so I point there: here. Terry Tao also has some comments on the Fields Medal here. So does Doron Zeilberger here.

How much is a Fields medal worth?

1) The winners get $15,000 each.

2) Winning a Fields medal gets one a higher salary and the ability to change schools, so the $15,000 might not be the main monetary part.  All Field Medalists are under 40 so the salary increases and such last for a much longer time then (say) a Nobel prize given for life achievements to someone much older. So you may rather win a Fields' medal when you are 39 than a Nobel when you are 70. The Abel prize is around 740,000 dollars and (I think) given for lifetime achievement so again, a Fields Prize may be better. (See here for more on the Abel Prize).  Which would I prefer to win? I would be delighted if that was my dilemma.

3) I am sure that none of the four winners went into math because of the allure of the $15,000 Fields Medal.

4) The title of this post is ambiguous. It can also be read as

how valuable is the actual medal?

The answer is $4000, much more than I would have thought. I only know this since it was recently stolen, see here.

This raises a linguistic question. The four people above can say

                                                          I WON a Fields Medal

The thief can say

                                                          I HAVE a Fields Medal

and hope that people don't quite realize that he didn't earn it.

(The article about the theft says the Fields medal is $11,500 dollars. Do they deduct the cost of the Medal itself? Or is the article wrong?)

While I Was Away

After the Oxford Workshop I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just very hot up to 106℉. The old Spanish cities knew how to optimize for shade and breeze, more than I can say for Oxford.

Meanwhile in a more moderate Brazilian climate, the International Congress of Mathematicians awarded their medals, including the Rolf Nevanlinna Prize to Constantinos Daskalakis in a year with several very strong candidates. The Nevanlinna prize gets awarded every four years to a researcher under 40 for contributions to mathematical aspects of information sciences. Costis was the then-student author of the 2004 Nash Equilbrium is PPAD-complete result and has gone on to be a leader in the algorithmic game theory community.

The ICM also distributes the Fields Medal, the highest honor in mathematics. Much ado is given to Peter Scholze who received the award this year at the age of thirty though remember that Alexander Razborov received his Nevanlinna prize at the age of 27 in 1990. Caucher Birkar also received the Fields Medal at the more standard age of 40 but had it for only a few minutes before it was literally stolen away.

I didn't realize how much I appreciate the convenience of Uber and Lyft until I had to get around cities where they don't exist. Meanwhile New York started to limit ride-sharing vehicles and I arrived in Madrid to a taxi strike protesting Uber in that city. The Yin and Yang of technology.

The Future of TCS Workshop, celebrating V Vazirani 60th, now online

On June 29, 2018, a workshop was held, in conjunction with STOC 2018, to celebrate the accomplishments of Vijay Vazirani on the  occasion of his 60th birthday, organized by his PhD students, Aranyak Mehta, Naveen Garg and Samir Khuller. The workshop was called "TCS: Looking into the Future" and true to the title, it was precisely that!  In front of a large, enthusiastic audience, left over from STOC, the star-studded lineup of speakers outlined some of the most avant-garde, far out ideas  on the future of computing.  Fortunately, this exciting and highly thought-provoking set of talks was recorded for posterity  and is available for all to view here
THE LAST WORD `here' IS THE LINK to the website which has links to the four talks.

The speakers were:

Len Adleman, Manuel Blum, Richard Karp, Leonard Schulman, Umesh Vazirani.

1) I URGE you to all WATCH those talks!

2) I really like it when talks are available on line after the fact so even if you didn't go (I didn't) you can still see the talks later.

3) So many talks to watch, so little time, alas!

4) Sorry for the white background for this post- that happens sometimes. NO comments on it please.

Three trick questions in Formal Lang Theory

There are three questions I ask in my Formal Lang Theory class that even the very best students get wrong. Two I knew were trick quesions, the other I was surprised by

1) If w is a string then SUBSEQ(w) is all strings you can form by replacing some symbols in w
with empty string. SUBSEQ(L) is defined in the obv way.

I ask the following in class (not on an exam). TRUE or FALSE and WHY and we'll discuss
If L is regular then SUBSEQ(L) is regular
If L is context free then SUBSEQ(L) is context free
If L is decidable then SUBSEQ(L) is decidable
If L is c.e. (used to be called r.e.) then SUBSEQ(L) is c.e.

The students pretty much get and prove that 1,2, and 4 are TRUE. They all think 3 is false.
But is true. For a strange reason

If L is ANY lang whatsoever then SUBSEQ(L) is regular. Comes from wqo theory. For more on this see a blog post I did when I was a guest blogger (it shows- the typeface is terrible) here

2) How many states does and NFA  need for { a^n : n \ne 1000} (or similar large numbers). ALL of the students think it takes about 1000 states. They are wrong: here

The two above I know people get wrong. The third one surprised me, yet every year the good students get it wrong

3) BILL: We showed that
a) 2-colorablility is in P, hence of course planar 2-colorability is in P
b) 3-colorability is NP-complete
c) 4-colorabilty of Planar graphs is in P

SO what about 3-colorability of planar graphs?

My very best student said the following last spring:

Planar 2-col is in P

Planar 4-col is in P

so I would guess that Planar 3-col is in P.

In prior years others made the same mistake.  My opinion of these students is NOT lowered, but I am surprised they make that guess. Of course, once you KNOW something you have a hard time recovering the state of mind of NOT knowing it, so my being surprised says more about my having drunk the Kool aid then their thought patterns.

Complexity in Oxford

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a wonderful workshop this past week. It's my first trip to Oxford since I came five years ago to celebrate the opening of the Andrew Wiles building, a building that hosted this weeks' workshop as well.

We also got a chance to see old math and physics texts. Here's Euclid's algorithm from an old printing of Euclid's Elements.

Unlike a research conference, this workshop had several talks that gave a broader overview of several directions in complexity with a different theme each day.

A few highlights of the many great talks.

Sasha Razborov gave a nice discussion of proof systems that help us understand what makes circuit bounds hard to prove.

Tuesday was a day for pseudorandomness, finding simple distributions that certain structure can't distinguish from random. Ryan O'Donnell talked about fooling polytopes (ANDs of weighted threshold functions). Avishay Tal talked about his new oracle with Ran Raz, viewing it in this lens as a distribution that the low-depth circuit can't distinguish but quantum can. I talked about some simple extensions to Raz-Tal and the possibilities of using their techniques to show that you can't pull out quantumness in relativized worlds.

Toni Pitassi talked about lifting--creating a tight connection between decision tree and 

complexity bounds to export lower bounds from one model to the other. Yuval Ishai talked about the continued symbiosis between complexity and theoretical cryptography.

Ryan Williams talked about his approach of using circuit satisfiability algorithms to prove lower bounds that led to his famed NEXP not in ACC⁰ result. He has had considerable recent progress including his recent work with Cody Murray getting reducing NEXP to nondeterministic quasipolynomial time.

Great to get away and just think complexity for a week. Seeing my former students Rahul Santhanam and Josh Grochow all grown up. And realizing I've become that old professor who regales (or bores) telling complexity stories from long ago. 

Need EASY approaches to getting unif random from non-random sources

Teaching crypto for the first time next semester I am looking into lots of stuff I always meant to look into but now I have to. NOT a complaint- good to be forced to expand my horizons (within TCS).

I"m also finding out that the web is great for easy and hard stuff but not so good for medium stuff.

Here is what I want to know so I am reaching out to my readers.

KNOWN: you want to generate a unif rand seq of 0's and 1's. The bits you can generate are Independent (yeah) but biased (boo). So here is what you do: generate 2 at a time and

if see 00 then DO NOT USE

if see 11 then DO NOT USE

if see 01 then generate 0

if see 10 then generate 1

KNOWN: You can do similar things if you have 00, 01, 10, 11 independent. And also if you have 000, 001, blah blah , 111 independent.

I tried looking up if there is a better way and I came across some complicated papers. I need material for a senior course. So, are there INTERMEDIARY results Suitable for a classroom, on better ways to us an imperfect source to get unif rand?

CRA Snowbird 2018

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me.

This week I attended the 2018 Computing Research Association Snowbird conference, a biennial meeting of Computer Science chairs and leadership mostly from the US. This is my fifth Snowbird meeting, once as a panelist talking about publications and now four times as a chair.

One cannot deny the success of computer science over the past decade. Our enrollments have jumped dramatically, our students at all levels get great jobs, CS departments are expanding. CS research and ideas play fundamental roles in society usually but not always for the better. We have our challenges, how to we hire new faculty when most PhDs take industry jobs and how to cover the increasingly heavy course enrollments, but we do not have the existential discussions you might find in similar meetings in other disciplines.

While the best part of the meeting happens in informal discussions in the hallways and on the mountain, several sessions bring out some specific topics in the minds of participants. A few that caught my interest.

In the first Snowbird of the #metoo era, we had some good discussion and a few scary stories about what women face at conferences and academic departments. The ACM has a new conference harassment policy and many CS communities, including theoretical computer science, are tackling this issue head on. This is part of a longer and larger struggle the field has had in attracting and retaining women and underrepresented minorities into the community.

One session focused on pushing metric-based rankings of computer science programs with presentations of Microsoft Academic Search, CRA’s own CS metrics and Emery Berger’s CS Rankings. CS Rankings has grown in popularity, particularly among undergrads looking at grad schools and Emery discussed how he’s created an advisory board that carefully considers how to count papers.

Personally I prefer the reputation-based rankings like US News, but I was definitely the tiny minority in the room.