ALGO 2020 Plenary Speakers
Location: MS Teams "ALGO Plenary Room". Unsure about Italy time zone? [Please check here].
ALGO: Plenary Speaker (Monday, Sept. 7, 17:00-18:00, Chair Fabrizio Grandoni)
Consider a setting in which inputs to and outputs from a computational
problem are so large, that there is not time to read them in their
entirety. However, if one is only interested in small parts of the
output at any given time, is it really necessary to solve the entire
computational problem? Is it even necessary to view the whole input?
We survey recent work in the model of "local computation algorithms"
which for a given input, supports queries by a user to values of
specified bits of a legal output. The goal is to design local
computation algorithms in such a way that very little of the input
needs to be seen in order to determine the value of any single bit
of the output. Though this model describes sequential computations,
techniques from local distributed algorithms have been extremely
important in designing efficient local computation algorithms.
In this talk, we describe results on a variety of problems for which
sublinear time and space local computation algorithms have been
developed -- we will give special focus to finding maximal
independent sets and generating random objects.
ALGO: Plenary Speaker (Tuesday, Sept. 8, 13:00-14:00, Chair Dennis Huisman)
Consolidation carriers, such as package express companies and less-than-truckload companies, employ a hub-and-spoke network to move shipments from their origins to their destinations. Shipments are sorted and consolidated at the terminals to ensure high utilization of the vehicles moving shipments between terminals.
We discuss computationally efficient and effective algorithms for two problems arising in this context. First, determining a load and flow plan, i.e., when and where to operate vehicles in the network and how to route shipments through the network. Second, given a load and flow plan how to make adjustments on the day of operations to efficiently and effectively react to deviations from expected shipment volumes (which were used to create the load and flow plan). The focus will be on algorithms that can handle instances encountered at large real-world carriers operating large hub-and-spoke service networks.
ALGO: Plenary Speaker (Wednesday, Sept. 9, 17:00-18:00, Chair Jens Stoye)
Last year at the BCB/WABI joint conference I presented a tutorial on Integer
Linear Programming (ILP) in computational biology, based on the
newly published book on that topic. In writing the book, I examined
more than fifty problems in computational biology where ILP has
been (mostly) successful in solving realistic problem instances,
and did extensive empirical investigation of many of these problems.
While, the empirical results strongly support the utility of ILP
in computational biology, I also ran into a few problems in
computational biology where ILP was less effective than desired,
or was almost totally ineffective. So, in the last year, along with
two students, I have tried to see if these hard problems could be
more effectively solved using approaches based on SATISFIABILITY
and SAT-solving. This approach creates Boolean formulas in Conjunctive
Normal Form (CNF) that express the requirements of problem instances,
along with optimization targets, and then run a SAT-solver to see
if these CNF formulas can be satisfied. This approach is not
well-investigated in computational biology, currently discussed in only a
small number of papers in the computational biology literature.
I expected that the SAT approach would do no better than ILP did
on these hard problems, but was very surprised that the situation
(although somewhat nuanced) is mostly the opposite: SAT-solving
often works very well, and so provides another powerful tool that
should be explored and exploited in computational biology.
In this talk, I will describe the SAT-solving approach; how we did it;
what we learned; how I tried to maintain my sanity while
doing it; strange observations we saw; and also give some (hopefully
correct) advice on how to start working in this area. I will focus
on three specific problems: Protein folding under the HP model;
Gene Sorting by Reversals; and Building Optimal Phylogenetic Networks
to represent clusters and trees.
Much of this work was joint with Hannah Brown, and some with Lei
Zuo, supported by NSF grant 1528234 and REU supplement.
ALGO: Plenary Speaker (Thursday, Sept. 10, 13:30-14:30, Chair Alfredo Navarra)
This talk will present some of the most recent results about the design of techniques for locally certifying the legality of a global state of a distributed system with respect to a given predicate. The talk will also discuss the connections between these techniques and fault-tolerant distributed computing. Classical techniques involve the assignment of certificates to the nodes, which are supposed to form a global proof that the system satisfies the predicate, and which can be verified locally (nodes interact with their neighbors only). More recent techniques are based on interactive proofs, i.e., they involve interactions with an external party, motivated by the development of cloud computing.
ALGO: Plenary Speaker (Thursday, Sept. 10, 17:00-18:00, Chair Christos Kaklamanis)
Although sequential algorithms with (nearly) optimal
running time for finding shortest paths in undirected graphs with
non-negative edge weights have been known for several decades,
near-optimal parallel algorithms have turned out to be a much tougher
challenge. In this talk, we present a (1+epsilon)-approximate
parallel algorithm for computing shortest paths in undirected graphs,
achieving polylog depth and near-linear work. All prior all prior
(1+epsilon)-algorithms with polylog depth perform at least superlinear
work. Improving this long-standing upper bound obtained by Cohen
(STOC'94) has been open for 25 years. Our algorithm uses several new
tools. Prior work uses hopsets to introduce shortcuts in the graph.
We introduce a new notion that we call low hop emulators. We also
introduce compressible preconditioners, which we use in conjunction
with Serman's framework (SODA '17) for the uncapacitated minimum cost
flow problem. Join work with Alex Andoni and Peilin Zhong.