P vs NP

If it is easy to verify whether a solution to a problem is correct, is the problem easy to solve? This question is posed as the P vs NP problem and is considered one of the most important unsolved problems in Mathematics. This post will be brief and forgo many technical details surrounding the question for the sake of accessibility.

dp

Continue reading

Advertisements

Finding Adam

This post will outline the paper Finding Adam in random growing trees by Bubeck, Devroye, and Lugosi. The main question examined in this paper is simply stated and relatively unstudied: given a tree, which has been generated under some attachment model, find the first vertex. “First” here meaning oldest. Think about the spread of a rumor, or disease. In these situations, the resulting distribution is known, but the starting point is not.

Continue reading

Welcome

Posts on with high probability focus on topics in combinatorics, probability, and theoretical computer science. Most are mathematically accessible to anyone who’s curious enough to read them!

Nim

Nim is a simple game, in which 2 players take turns removing objects from piles until there are no more objects left. This post will define basic terms for combinatorial game theory, detail the rules of nim, and explain how to win the game.

Continue reading

History of Common Games

Games are the perfect mix of chaos and strategy: they are dynamic, since players’ decisions affect them, but there often exists an optimal way to play. This post discusses

  • why we can solve some games but not others.
  • how we solve these games.
  • different processes developed along the way.

The solvability of tic-tac-toe, set take-away, Connect 4, checkers, and chess will be examined in further detail.

Continue reading