Dr. Kim Binsted Talks Mars at The President’s Series on Hawai‘i Island

What Will It Be Like to Live on Mars?
Planning for Human Exploration of Space

On April 5, ICS Professor Kim Binsted will discuss the HI-SEAS (Hawai‘i Space Exploration Analog and Simulation) project as part of The President’s Series on Hawai‘i Island.


HI-SEAS is an analog habitat for human spaceflight to Mars, located on an isolated Mars-like site on the Mauna Loa side of the saddle area at 8200 feet above sea level. The fourth phase of the project began in August of 2015 and lasted for one year. Learn what was discovered about what humans will need to stay happy and healthy during an extended mission to Mars.

Wednesday, April 5, 5 p.m.
RSVP by March 30
808-956-9340 or events@uhfoundation.org

Hawaiʻi Community College – Pālamanui Outdoor Theatre (Campus Piko)
73-4225 Ane Keohokālole Hwy, Kailua-Kona

More information: The President’s Series – Hawai‘i Island


ICS Lunch and Seminar Series: John Iacono on 3/16

Thursday, March 16, 12:00pm, POST318B (ICSpace)

Subquadratic Algorithms for Algebraic Generations of 3SUM

John Iacono
Professor, Computer Science and Engineering
NYU Polytechnic School of Engineering


The 3SUM problem asks if an input n-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The motivations are threefold. Raz, Sharir, and de Zeeuw gave a O(n11/6) upper bound on the number of solutions of trivariate polynomial equations when the solutions are taken from the Cartesian product of three n-sets of real numbers. We give algorithms for the corresponding problem of counting such solutions. Grønlund and Pettie recently designed subquadratic algorithms for 3SUM. We generalize their results to 3POL. Finally, we shed light on the General Position Testing (GPT) problem: “Given n points in the plane, do three of them lie on a line?”, a key problem in computational geometry.
We prove that there exist bounded-degree algebraic decision trees of depth O(n12/7+ε) that solve 3POL, and that 3POL can be solved in O(n2(log log n)3/2/(log n)1/2) time in the real-RAM model. Among the possible applications of those results, we show how to solve GPT in subquadratic time when the input points lie on o((log n)1/6/(log log n)1/2) constant-degree polynomial curves. This constitutes a first step towards closing the major open question of whether GPT can be solved in subquadratic time.

To obtain these results, we generalize important tools — such as batch range searching and dominance reporting — to a polynomial setting. We expect these new tools to be useful in other applications.

Full article: Luis Barba, Jean Cardinal, John Iacono, Stefan Langerman, Aurélien Ooms, Noam Solomon: Subquadratic Algorithms for Algebraic Generalizations of 3SUM. CoRR abs/1612.02384 (2016)


Lee Altenberg Publishes in PNAS


Altenberg, L., Liberman, U., and Feldman, M.W. 2017. A Unified Reduction Principle for the Evolution of Mutation, Migration, and Recombination. Proceedings of the National Academy of Sciences, Early edition: March 6. doi: 10.1073/pnas.1619655114.


Abstract: Modifier-gene models for the evolution of genetic information transmission between generations of organisms exhibit the reduction principle: Selection favors reduction in the rate of variation production in populations near equilibrium under a balance of constant viability selection and variation production. Whereas this outcome has been proven for a variety of genetic models, it has not been proven in general for multiallelic genetic models of mutation, migration, and recombination modification with arbitrary linkage between the modifier and major genes under viability selection. We show that the reduction principle holds for all of these cases by developing a unifying mathematical framework that characterizes all of these evolutionary models.