Aaron Sterling

In December, members of the Antisec wing of the collective Anonymous claimed to have downloaded the email spools of the private intelligence firm Stratfor.  Today, Wikileaks held a press conference in which they announced that over 20 media organizations had been secretly analyzing the 5 million+ emails, and they would now begin releasing the emails.  [...] - Aaron Sterling

I joined Twitter at the end of December 2011 because I realized that I was using my computer less and less, and my smart phone more and more, relatively speaking — and I was using my phone to find and read content that intrigued me.  I plan to use my Twitter account almost as a [...] - Aaron Sterling

heh, and today is the day twitter is not responding :) - Rajarshi Guha

I’ve posted twice about Anonymous hacking into Stratfor — and, more generally, their hacktivism has been making bigger and bigger waves.  CNN recently ran a fairly positive story on the support hacktivists are providing the Occupy movement.  Many of these hacktivists are quite active on Twitter and elsewhere.  However, from the perspective of both international [...] - Aaron Sterling

This post is based on a book review I recently wrote on The Mathematics of Life, by Ian Stewart. A final version of the review will appear in a future issue of SIGACT News.  Please feel free to download a pdf version of the full preprint, or just read an abbreviated version of it here, [...] - Aaron Sterling

In an unfortunate coincidence, as a thematic followup to my previous post on hacking, a “throwaway” email I use, and partial credit card information of mine, has just been compromised in the recent hack of Zappos.com.  Infosec Island has a good blog post about this data breach,  and I was one of 24 million Zappos [...] - Aaron Sterling

I will return to blogging about theoretical computer science and algorithm-related mathematics next week, but I wanted to take a few minutes today to mention a rare research opportunity that has arisen as a result of the hack of the private global intelligence company Stratfor.  This opportunity is the list of 860,000 (MD5 hashed) passwords [...] - Aaron Sterling

Tying up loose ends from my three posts in December about rectangulation of orthogonal polygons. Derrick Stolee requested in a comment a resolution of the computational complexity of the 3D version of the problem of decomposing a shape into the minimum number of rectangles.  I found a reference that proves the problem is NP-complete, by [...] - Aaron Sterling

I had not planned to post until January, but I decided to say something briefly about a news story that relates to one of the first posts on this blog, about security firm HBGary’s insecure storage of data.  This story, as I am sure many of you have already guessed, is the hacking of Strategic [...] - Aaron Sterling

I would like to wish a very happy holiday season to all the readers of this blog.  I am excited about the research I have planned in 2012, and I hope you are even more excited about your own year-to-come. This will be my last post until the new year.  As a holiday gift, please [...] - Aaron Sterling

In this third (and final) post on polygon rectangulation, I will consider how to find the rectangulation of minimum total length for an orthogonal polygon.  In part one of this short series, we considered rectangulations with a minimum number of rectangles; and, in part two, we considered rectangulations with a minimum number of “fat” rectangles.  [...] - Aaron Sterling

This post is the second in a series on polygon rectangulation. In my previous post, I discussed methods to decompose an orthogonal polygon into a minimum number of rectangles.  (See that post for definitions and motivation.)  In my next post, I will consider finding a rectangulation of a minimum length — a topic very important [...] - Aaron Sterling

Over the next few posts, I will consider problems of polygon rectangulation: given as input an orthogonal polygon (all interior angles are 90 or 270 degrees), decompose into adjacent, nonoverlapping rectangles that fully cover .  Different problems impose different conditions on what constitutes a “good” rectangulation.  Today we will discuss how to find a rectangulation [...] - Aaron Sterling

Two days ago, I added a “bounty” to a year-old unanswered question that Noam Nisan asked on CSTheory about the relationship between the Polynomial Hierarchy and the complexity class PP (probabilistic polynomial time).  I remember thinking when the question was first asked, “Wow, there is something important going on here,” but no one has posted [...] - Aaron Sterling

In today’s post, I will discuss a little-known combinatorics paper by E.N. Gilbert from 1965, in which he independently discovered the “logarithmic Welch” construction of Costas arrays.  Costas arrays are named after the late IEEE fellow John Costas, whose seminal paper on what are now called Costas arrays appeared, coincidentially, in 1965, the same year [...] - Aaron Sterling

There is a new post category on the CSTheory StackExchange Community Blog — Conference/Workshop Reports — and Dave Pritchard (who often goes by the nick daveagp online) has just posted the first such report, covering the sixth annual meeting of EuroComb in Budapest, a conference in honor of Gyula Katona’s 70th birthday, and the European [...] - Aaron Sterling

There is an active proposal at StackExchange to build a research-level Q and A site for theoretical physics. There is a Physics StackExchange site already, for questions at the high school or undergraduate level.  The new site would be expert-level only, like MathOverflow for math, or CSTheory for theoretical computer science. The new site is [...] - Aaron Sterling

The RSS feed of the CSTheory Community Blog was broken for a couple weeks.  Thanks to Jukka Suomela, we discovered this (just recently), and the feed is now valid again.  Here are the posts that appeared while the feed was down. Lower Bounds by Negative Adversary Method, by Artem Kaznatcheev.  Artem provides a technical introduction [...] - Aaron Sterling

One of my research interests is the DNA self-assembly of multicolored shapes.  Almost all DNA self-assembly literature — both theory and practice — has focused on the assembly of either 1-color or 2-color shapes.  Nevertheless, if we think of the DNA assembly as a substrate, or scaffolding, upon which transistors or nanomachines are placed later, [...] - Aaron Sterling

SHW5C3KGKVSY The list of accepted papers for the 17th International Conference on DNA Computing and Molecular Programming is now up.  This isn’t breaking news, but I haven’t seen it mentioned on other theory blogs, so I figured it was worth posting. Some of these papers, and ones they cite, will be my blogging focus over [...] - Aaron Sterling

In a previous post, I considered a proof of the Church-Turing Thesis that Dershowitz and Gurevich published in the Bulletin of Symbolic Logic in 2008.  It is safe to say that the proof is controversial — not because it is technically inaccurate, but because it relies on an axiomatization of computation that excludes randomness, parallelism [...] - Aaron Sterling

The first technical post is now up on the CSTheory Community Blog.  It is Quantum Query Complexity, by Artem Kaznatcheev.  Artem is currently working on a followup post on the “negative adversary method,” a fairly recent proof technique in quantum computing, which we will post there soon. I hope you enjoy the new blog!  I [...] - Aaron Sterling

You’ve watched all the movies.  You’ve read all the books.  You’ve even practiced tactial skirmishes with lifesize zombie targets.  But now, all of a sudden, you are thinking, “I didn’t know there would be math!” Actually, if you’re a regular reader of this blog, I imagine you are thinking, “I didn’t know there would be [...] - Aaron Sterling

Quantum computing expert Joe Fitzsimmons and I have just agreed to be co-editors of the brand-new blog Theoretical Computer Science, the community blog of the TCS question and answer site cstheory.stackexchange.com.  The first post of the new blog is here.  The blog is hosted under the StackExchange network, and the graphic designer for StackExchange is [...] - Aaron Sterling

My post from yesterday on the Church-Turing Thesis now bears a green-and-white checkbox icon labeled “Editor’s Selection.”  This is because yesterday afternoon, an editor of ResearchBlogging.org selected it (and two other posts, by different bloggers) as “interesting and notable ResearchBlogging.org posts in the physical sciences, chemistry, engineering, computer science, geosciences and mathematics” for this week. [...] - Aaron Sterling

The Church-Turing Thesis lies at the junction between computer science, mathematics, physics and philosophy.  The Thesis essentially states that everything computable in the “real world” is exactly what is computable within our accepted mathematical abstractions of computation, such as Turing machines.  This is a strong statement, and, of course, if one had tried to say the [...] - Aaron Sterling

In this post, I will discuss Schaefer’s Theorem for Graphs by Bodirsky and Pinsker, which Michael Pinsker presented at STOC 2011.  I love the main proof technique of this paper: start with a finite object, blow it up to an infinite object, use techniques from infinitary Ramsey Theory to show that the infinite object must [...] - Aaron Sterling

A Twitterish post on two blog entries about nanoscale hardware: On the theory side, Olexandr Isayev, a chemist at Case Western, blogs about a new paper by Erik Winfree and Lulu Qian, in which they design DNA circuitry capable of computing a square root. On the practical industry side, Joerg Heber, Senior Editor at Nature [...] - Aaron Sterling

I recently completed a review for SIGACT News of the Handbook of Nature-Inspired and Innovative Computing, edited by Albert Zomaya.  The full review is here.  Below is the introduction to the review.  I enjoyed reading the book. The ambitious goal of the Handbook of Nature-Inspired and Innovative Computing is to “to be a Virtual Get Together [...] - Aaron Sterling

In this post, I will discuss Distributed Verification and Hardness of Distributed Approximation, by Das Sarma and seven other authors.  I enjoyed this paper for a couple reasons: first, it highlights a major difference between “traditional” computing and distributed computing; and, second, it puts forth a research program that seems to have a lot of [...] - Aaron Sterling

In this blog entry and the next one, I will discuss two distibuted computing papers at STOC 2011: Tight Bounds for Parallel Randomized Load Balancing by Lenzen and Wattenhoffer (this entry), and Distributed Verification and Hardness of Distributed Approximation by Das Sarma et al (next entry).  There have been at least two tracks on distributed [...] - Aaron Sterling