Federico Lebrón

The boolean satisfiability problem

Categories: Programming, Computer Science

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.

A categorical view of covariance and contravariance in C++

Categories: Programming, Mathematics, Computer Science

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".

Braess's paradox and the price of anarchy

Categories: Game Theory, Mathematics

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.

An introduction to incidence matrices

Categories: Computer Science, Mathematics

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.