Federico Lebrón

Recently the students for the class I TA in had to solve a couple of exercises involving the boolean satisfiability problem, also known as SAT. I'd like to talk about some aspects of it which, while by no means new, should be interesting for someone being introduced to the problem.

I had often heard the expression "C++ now has covariant return types". To be honest, I vaguely knew covariance was a mathematical term, and I was also pretty sure it had nothing to do with statistical covariance.

Now that I understand a bit more about category theory, I feel I can clarify some things about this usage of the word "covariance" in programming languages. Surprisingly, it is not a terrible bastardization of the mathematical term, as C++ and Java have done to the word "functor".

A few days ago I attended a series of lectures on graph theory and optimization at the National University of Rosario, Santa Fe. I'd like to discuss one of the topics presented there by Nicolás Stier-Moses, from Columbia University. This topic is selfish routing, Braess's paradox, and the price of anarchy, in the field of algorithmic game theory.

I'll give a brief overview of these points in his talk, and present one of his results, a short proof of the upper bound on the price of anarchy in linear path cost congestion routing problems.

Given a graph , with , , we can define a matrix , called 's incidence matrix, defined as such:

In this post, we study some of this matrix's algebraic properties.

Given a graph , with , , we can consider the matrix defined as such:

We call this the adjacency matrix. In this article we study some of its algebraic properties.