17 posts · 14,586 views
Biocomputing and other nonstandard applications of theoretical computer science.
Aaron Sterling
17 posts
Sort by: Latest Post, Most Popular
View by: Condensed, Full
- January 27, 2012
- 10:00 AM
- 479 views
Watermarking molecules
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Joachim J. Eggers, W.D. Ihlenfeldt, & Bern Girod. (2001) Digital Watermarking of Chemical Structure Sets. Information Hiding, 200-214. DOI: 10.1007/3-540-45496-9_15
- January 20, 2012
- 10:00 AM
- 670 views
Ian Stewart’s Mathematics of Life
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Ian Stewart. (2011) The Mathematics of Life. Book: ISBN 0465022383. info:/
- January 13, 2012
- 10:00 AM
- 363 views
Password analysis from the Stratfor hack
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Moshe Zviran, & William J. Haga. (1999) Password Security: An Empirical Study. Journal of Management Information Systems, 15(4), 161-185. info:/
- January 6, 2012
- 10:00 AM
- 586 views
Polygon rectangulation wrap up
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Victor J. Dielissen, & Anne Kaldewaij. (1991) Rectangular partition is polynomial in two dimensions but NP-complete in three. Information Processing Letters, 38(1), 1-6. info:/10.1016/0020-0190(91)90207-X
- December 16, 2011
- 10:00 AM
- 2,876 views
Polygon rectangulation, part 3: Minimum-length rectangulation
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Andrzej Lingas, Ron Y. Pinter, Ronald R. Rivest, & Adi Shamir. (1982) Minimum edge length partitioning of rectilinear polygons. Proceedings of the 20th Allerton Conference on Communication, 53-63. info:/
- December 9, 2011
- 10:00 AM
- 654 views
Polygon rectangulation, part 2: Minimum number of fat rectangles
by Aaron Sterling in Nanoexplanations
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, … Continue reading →... Read more »
O'Rourke, J., & Tewari, G. (2004) The structure of optimal partitions of orthogonal polygons into fat rectangles. Computational Geometry, 28(1), 49-71. DOI: 10.1016/j.comgeo.2004.01.007
J. O'Rourke, & G. Tewari. (2002) Partitioning orthogonal polygons into fat rectangles in polynomial time. Canadian Conference on Computational Geometry, 97-100. info:/
- December 2, 2011
- 04:13 PM
- 523 views
Polygon rectangulation, part 1: Minimum number of rectangles
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
W.T. Liou, J.J.M. Tan, & R.C.T. Lee. (1989) Minimum Partitioning Simple Rectilinear Polygons in O(n log log n) Time. Symposium on Computational Geometry, 344-353. info:/10.1145/73833.73871
FERRARI, L., SANKAR, P., & SKLANSKY, J. (1984) Minimal rectangular partitions of digitized blobs. Computer Vision, Graphics, and Image Processing, 28(1), 58-71. DOI: 10.1016/0734-189X(84)90139-7
- October 9, 2011
- 08:36 PM
- 555 views
An independent discovery of Costas arrays
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Gilbert, E. (1965) Latin Squares which Contain No Repeated Digrams. SIAM Review, 7(2), 189. DOI: 10.1137/1007035
- August 13, 2011
- 09:27 AM
- 1,132 views
DNA self-assembly of multicolored rectangles
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
X. Ma, & F. Lombardi. (2008) Combinatorial Optimization Problems in Designing DNA Self-Assembly Tile Sets. IEEE International Workshop on Design and Test of Nano Devices, Circuits and Systems, 73-76. DOI: 10.1109/NDCS.2008.7
Ma, X., & Lombardi, F. (2009) On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly. IEEE Transactions on Circuits and Systems II: Express Briefs, 56(1), 31-35. DOI: 10.1109/TCSII.2008.2010161
Mika Göös, & Pekka Orponen. (2011) Synthesizing Minimal Tile Sets for Patterned DNA Self-Assembly. DNA Computing and Molecular Programming, LNCS, 71-82. DOI: 10.1007/978-3-642-18305-8_7
- July 30, 2011
- 01:31 PM
- 1,041 views
The Dershowitz/Falkovich proof of the Extended Church-Turing Thesis
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Nachum Dershowitz, & Evgenia Falkovich. (2011) A Formalization and Proof of the Extended Church-Turing Thesis. International Workshop on the Development of Computational Models. info:/
- July 17, 2011
- 02:09 PM
- 1,105 views
The SZR model of the zombie apocalypse
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Philip Munz, Ioan Hudea, Joe Imad, & Robert J. Smith?. (2009) When Zombies Attack!: Mathematical Modelling of an Outbreak of Zombie Infection. Infectious Disease Modelling Research Progress, 133-150. info:/
- July 4, 2011
- 01:23 PM
- 1,077 views
A mathematical proof of the Church-Turing Thesis?
by Aaron Sterling in Nanoexplanations
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. … Continue reading →... Read more »
Nachum Dershowitz, & Yuri Gurevich. (2008) A Natural Axiomatization of Computability and Proof of Church's Thesis. The Bulletin of Symbolic Logic. DOI: 10.2178/bsl/1231081370
- June 26, 2011
- 03:54 PM
- 920 views
STOC 2011: Infinitary Ramsey Theory yields a complexity dichotomy theorem for CSPs over graphs
by Aaron Sterling in Nanoexplanations
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 … Continue reading →... Read more »
Manuel Bodirsky, & Michael Pinsker. (2011) Schaefer's Theorem for Graphs. Proceedings of 43rd Annual ACM Symposium on the Theory of Computing. info:/
- April 3, 2011
- 05:20 PM
- 1,057 views
Connected Guards in Orthogonal Art Galleries
by Aaron Sterling in Nanoexplanations
The Art Gallery Problem is one of the fundamental problems in computational geometry. It’s easy to state, easy to motivate, and “simple” variations of it can be very hard to solve. The problem: given a building, what is the fewest … Continue reading →... Read more »
Val Pinciu. (2003) Connected Guards in Orthogonal Art Galleries. ICCSA 2003, Lecture Notes in Computer Science, 886-893. DOI: 10.1007/3-540-44842-X_90
- March 12, 2011
- 08:00 AM
- 435 views
Computational action: the question I didn’t ask Jeannette Wing
by Aaron Sterling in Nanoexplanations
my thoughts about a presentation Jeannette Wing gave, based on articles she has written about Computational Thinking... Read more »
Wing, J. (2008) Computational thinking and thinking about computing. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366(1881), 3717-3725. DOI: 10.1098/rsta.2008.0118
- March 5, 2011
- 08:00 AM
- 479 views
Minimum edge length partitioning of rectilinear polygons
by Aaron Sterling in Nanoexplanations
The title of this blog post is the same as that of a seminal paper in computational geometry and VLSI design by Lingas, Pinter, Rivest and Shamir from 1982. The authors present an O(n^4) algorithm to produce a minimum-length rectangular partitioning of a rectilinear polygon without holes.... Read more »
Andrzej Lingas, Ron Y. Pinter, Ronald R. Rivest, & Adi Shamir. (1982) Minimum edge length partitioning of rectilinear polygons. Proceedings of the 20th Allerton Conference on Communication, 53-63. info:/
- February 28, 2011
- 08:00 AM
- 634 views
Treewidth of molecular graphs
by Aaron Sterling in Nanoexplanations
In 2003, Yamaguchi et al. tested the treewidth of 9712 molecules, and found that 19.4% had treewidth one, 75.7% had treewidth two, 4.9% had treewidth three, and only one molecule had treewidth four. They also tested the local tree-width; you can see those results in Table 2 of their paper here. Their conclusion: “tree-width of compounds is not only a useful complexity measure, but it is also an appropriate factor to consider in characterizing chemical compounds.”... Read more »
Atsuko Yamaguchi, Kiyoko F. Aoki, & Hiroshi Mamitsuka. (2003) Graph Complexity of Chemical Compounds in Biological Pathways. Genome Informatics, 376-377. info:/
topics
join us!
Do you write about peer-reviewed research in your blog? Use ResearchBlogging.org to make it easy for your readers — and others from around the world — to find your serious posts about academic research.
If you don't have a blog, you can still use our site to learn about fascinating developments in cutting-edge research from around the world.
