Parity Games in Quasipolynomial Time
28 March 2017 | 11:35 am

In one of the hallway discussions of last week's Dagstuhl I learned about an upcoming STOC paper Deciding Parity Games in Quasipolynomial Time by Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan. Hugo Gimbert and Rasmus Ibsen-Jensen offer a simplified proof of the correctness of the algorithm.

A Parity Game works as follows: An instance is a finite directed graph where every vertex has at least one outgoing edge, integer weights on the vertices and a designated starting vertex. Alice and Bob take turns choosing the next vertex by following an edge from the current vertex. They play this game infinitely long and Alice wins if the the largest weight seen infinitely often is even. Not trivial to show but the game is determined and memoryless, no matter the graph some player has a winning strategy, and that strategy depends only the current vertex and not the history so far. That puts the problem into NP∩co-NP and unlikely to be NP-complete.

Like graph isomorphism, whether there exists a polynomial-time algorithm to determine the winner of a parity game remains open. Also like graph isomorphism we now have a quasipolynomial-time (exponential in logk) algorithm, an exponential improvement. Parity games have some applications to verification and model checking and some at Dagstuhl claim the problem is more important than graph isomorphism.

One difference: If you had to guess who would make the big breakthrough in graph isomorphism, László Babai would be at the top of your list. But many of the authors of this new parity games paper, like Frank Stephan and Sanjay Jain, focus mostly on computability and rarely worry about time bounds. Their algorithm does have the flavor of a priority argument often found in computability theory results. A nice crossover paper.

The Dagstuhl Family
23 March 2017 | 9:17 am

This week I'm at the Dagstuhl workshop on Computational Complexity of Discrete Problems. As you long time readers know Dagstuhl is a German center that hosts weekly computer science workshops. I've been coming to Dagstuhl for some 25 years now but for the first time brought my family, my wife Marcy and daughter Molly, so they can see where I have spent more than half a year total of my life. Molly, currently a freshman at the University of Chicago, was the only Chicago representative, though the attendees included four Chicago PhDs, a former postdoc and a former professor.

We had a different ice breaker, where each person wrote topics they think about which ended up looking look like an interesting bipartite graph.


Molly has a few thoughts on Dagstuhl:

The coolest thing about the study of computer science is this place.

Okay, I know my dad would disagree with me (he probably thinks the coolest thing about computer science is the computer science itself). But for me, someone quite removed from the math and science and thinking, this place is by far the coolest thing about the computer science community. The point of it is isolation, as well simultaneous connection. The isolation comes in the form of a meeting center in rural Germany, separated from the world, devices which can (and do) block wifi in rooms like lecture rooms and the dining hall, resulting in a week without much interaction with the outside world. The connection stems from this very isolation -- in this highly isolated place, people are forced to connect with each other face-to-face, and to get to know each other, as well as the ideas and problems people are working on. The isolation creates a heightened sense of community, both in social and intellectual senses of the word. Forced to be so close and so interconnected, it’s no wonder so many problems get solved here.

I’m glad I got to come see why my father has been coming here for a quarter century. He is very old.

If you want to help your bad students DO NOT give an easy exam
20 March 2017 | 3:54 am


1) When I was a grad student TAing Formal Lang Theory we had a final ready to give out but noticed that one problem was too hard. So we changed it. But we made it too easy. Whoops. My thought at the time was this will help the bad students. I was wrong. Roughly speaking the students who got 70-80 on the midterm now got 90-100 on the final whereas the students who got 30-40 on the midterm got 35-45 on the final. So the bad students improved, but the better students improved more.

2) When I teach Discrete Math to LOTS of students we have a policy about midterm regrade requests. Rather than have them argue in person they have to:

In writing make a clear concise argument as to why it was mis-graded

If your argument displays that you really don't know the material, even when you can reflect on it, you can lose points. (True Story: We ask for an example of a Boolean Function with two satisfying assignments. They gave us a formula with only one, so they got -5. In the regrade request they try to still argue that it has two satisfying assignments. They lost 2 more points.)

In reality the policy is more preventative and we rarely remove points. However even this policy benefits the better students more than the poor ones who have a hard time even articulating why what they wrote is actually right (likely it is not).

3) Just this winter teaching a 3-week 1-credit course we were grading a problem and giving lots of 15/25 since the students were all making the same mistake. Half way through I got suspicious that maybe WE were incorrect. Looking at the exact wording of the question I realized WE were wrong, and, given the wording and what they would quite reasonably think we wanted, they were right. So we went back and upgraded many students from 15 to 25. And again, this lifted students in the 70's to 90's, but did NOTHING for the students below 50 since none of them had anything like a correct answer to any way to view the question.

Okay, so what does all of this mean?  It means that an easy exam or a generous grading policy is devastating for the bad students.

However, that's just my experience- what are your experiences with this?





More News from this Feed See Full Web Site