# Is computational hardness the rule or the exception?

As a cryptographer, I am used to the viewpoint that computational problems are presumed hard unless proven otherwise. We cryptographers constantly come up with new hardness assumptions, and generally use the heuristic that if a problem doesn't have an obvious algorithm then it must be hard. We've had some interesting failures (see here for a recent example), but this heuristic seems … Continue reading Is computational hardness the rule or the exception?

# Erdős’s Book and the Asymptotic Religion

In an undergraduate algorithms class we learn that an algorithm is a high level way to describe a computer program. The running time of the algorithm is the number of operations it takes on inputs of a particular size- the smaller the better. So, as even Barack Obama knows, if you implement Quick-Sort, with its … Continue reading Erdős’s Book and the Asymptotic Religion

# Structure vs. Combinatorics in Computational Complexity

(Also available as a pdf file. Apologies for the many footnotes, feel free to skip them.) Computational problems come in all different types and from all kinds of applications, arising from engineering as well the mathematical, natural, and social sciences, and involving abstractions such as graphs, strings, numbers, and more. The universe of potential algorithms … Continue reading Structure vs. Combinatorics in Computational Complexity

# Reasons to care: In honor of Scott Aaronson

Update (5/7): This post earned me a spot on the not-so-exclusive club of people called names such as a "narrow-minded" "biased" "religious worshiper" "who  doesn't want to learn something difficult and new" by Luboš Motl. Interestingly, he mostly takes issue with my discounting the possibility that the complexity of SAT is something like \$latex n^{1000}\$ or \$latex … Continue reading Reasons to care: In honor of Scott Aaronson