Following is a conference report on SODA 2014 by my student Mahnush Movahedi [Jared]
SODA Conference Notes
This report is for those of you that could not attend SODA 2014 and are eager to know about it. There were many exciting talks at SODA ranging from algorithms, complexity, approximation algorithm, discrete optimization, combinatorics, graph theory and game theory in three parallel sessions.
Herbert Edelsbrunner was the invited plenary speaker for the first day. He described his journey to the fascinating world of geometric forms in his talk named “Shape, Homology, Persistence, and Stability”. Assume we are given a set S of points in a plain, alpha shape is an interpretation for the concept of the the shape formed by these points (it is a generalization of the convex hull). We can generalize this alpha shape in 2-dimensional to higher dimensions, specifically 3-dimensional case. In his talk he discussed homology and persistence. Persistent homology is an algebraic method for measuring topological features of shapes. Stability of persistent homology diagrams under perturbations was a key point in his talk.
Day two at SODA, I was especially intrigued by a session about distributed algorithms and self-organizing particle systems. David Doty gave a very interesting talk on the paper “Timing in chemical reaction networks”. He started the talk by showing a movie in which a white blood cell chases a bacteria by the power of chemical reactions. Chemical Reaction Networks (CRN) attempt to formally model the behavior of chemical systems. CRNs can be considered as an implementable a programming language for the design of artificial molecular control circuitry.
It has been shown that CRN can simulate bounded-space Turing machine with an arbitrary small positive probability of error. A+B→C+D is an example of reaction in the CRNs model, where A,B,C,D are molecular species. The “program” for a CRN consists of a set of reactions of this type, along with an initial population of molecular species. The “computation” occurs according to a statistical process that repeatedly chooses one reaction from the set and applies it to the appropriate chemical species.
Angluin, Aspnes, and Eisenstat in their paper “Fast computation by population protocols with a leader” relate the CRN reaction to leader election protocol. Starting from a uniform initial configuration of n copies of L , when two candidate leaders encounter each other, one drops out (by the reaction L+L→L+N ). However, electing a leader in this manner incurs an exponential slowdown and there is no way for the leader to know when it has been elected. These problems motivate the need for a timer CRN. In the search for a timer CRN, David shows that if a CRN respects finite density (at most O(n ) additional molecules can be produced from n initial molecules), then starting from any dense initial configuration (all molecular species initially present have initial count Theta(n), where n is the initial molecular count and volume), every producible species is produced in constant time with high probability. This implies that no CRN obeying the stated constraints can function as a timer. I had a chance to have lunch with David and discuss this work more. He is a fun and knowledgeable person who believes that implementing a timer is a core issue behind any population protocol.
Jared Saia talked about work with Valerie King on “Faster Agreement via a Spectral Method for Detecting Malicious Behavior”. To understand the work, lets start with the definition of Byzantine agreement: 1) bring n processors each with a private bit to agreement on a single common bit; and 2) ensure that this bit is the same as the input of one good processor. This problem is more difficult in the presence of a strong adversary, who has full information, can actively control the behavior of constant fraction of the processors and finally can control the scheduling of the delivery of messages. Jared presented an algorithm that can solve Byzantine Agreement for n processors in expected O(n^3) communication time, expected polynomial computation time per processor, and expected polynomial bits of communication. The algorithm is based on repeatedly generating a fair global coin, which is generated by coin flips from individual processors. The adversary can corrupt this process by generating biased individual coin flips. Spectral analysis is used in this work to detect such adversarial behavior. Each processor maintain a matrix containing the sum of the coin flips received in each iteration. The top right eigenvector of this matrix is used to detect adversarial processors, since entries with high absolute value in this eigenvectr correspond to processors that are trying to bias the global coin. Overall, a very nice paper.
I also would like to mention another talk that I found interesting: Intrinsic Universality in Tile Self-assembly Requires Cooperation presented by Andrew Winslow proves that Winfree’s abstract Tile Assembly Model is not intrinsically universal when restricted to use noncooperative (temperature 1) tile binding. The Tile Assembly Model is a simple model with translatable but un-rotatable square or cube tiles as its fundamental components. Tiles’ sides are labeled with glue colors, each with an integer strength. Two tiles that are placed next to each other interact if the glue colors on their abutting sides match, and they bind if the strengths on their abutting sides match and sum to at least a certain (integer) temperature. Temperature 1 binding, is where all tiles bind to each other if they match on at least one side; similarly you can define temperature 2 or more. It is interesting that the Tile Assembly Model is indeed intrinsically universal when temperature 2 binding is used but it is not intrinsically universal when restricted to temperature 1 binding.
I also enjoyed the game theory session which was full of new ideas. “Constrained Signaling in Auction Design” by Shaddin Dughmi, Nicole Immorlica, Aaron Roth is a well-written paper that focuses on auctions where the auctioneer does not have the capacity to describe to the buyers the exact identity of the good. Instead, the auctioneer describes the good using defined signals. Dimitris Paparas talked about “The Complexity of Optimal Multidimensional Pricing”. This paper is about the problem of computing a revenue-optimal pricing. They show that the decision version of this problem is NP-complete for distributions of support size 3 as well as for identical distributions. In his talk, on “The Complexity of Optimal Mechanism Design”, Christos Tzamos proved that optimal mechanism design is complex, and that a revenue-optimal auction in multi-item settings cannot be found and implemented in a computationally efficient way.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted. This work may be published or be a basis for publication in the future. Copyright may be transferred without further notice and this version may no longer be accessible.
Filed under: Uncategorized
Congratulations to Mahnush Movahedi and Varsha Dani for getting the
best paper award at the 15th International Conference on Distributed
Computing and Networking (ICDCN) (distributed computing track) for the paper:
Valerie King and I were also co-authors on the paper.