Communications of the ACM


The Heat Method for Distance Computation

Communications of the ACM

The heat method allows distance to be rapidly updated for new source points or curves. We introduce the heat method for solving the single- or multiple-source shortest path problem on both flat and curved domains. A key insight is that distance computation can be split into two stages: first find the direction along which distance is increasing, then compute the distance itself. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard sparse linear systems. These systems can be factored once and subsequently solved in near-linear time, substantially reducing amortized cost.


Technical Perspective: Solving Imperfect Information Games

Communications of the ACM

The study of games is as old as computer science itself. Babbage, Turing, and Shannon devised algorithms and hardware to play the game of chess. Game theory began with questions regarding optimal strategies in card games and chess, later developed into a formal system by von Neumann. Chess subsequently became the drosophila--or common fruitfly, the most studied organism in genetics--of artificial intelligence research. Early successes in chess and other games shaped the emerging field of AI: many planning algorithms first used in games became pillars of subsequent research; reinforcement learning was first developed for a checkers playing program; and the performance of game-playing programs has frequently been used to measure progress in AI.


Heads-Up Limit Hold'em Poker Is Solved

Communications of the ACM

Poker is a family of games that exhibit imperfect information, where players do not have full knowledge of past events. While many perfect information games have been solved (e.g., Connect-Four and checkers), no nontrivial imperfect information game played competitively by humans has previously been solved. In this paper, we announce that the smallest variant of poker in-play, heads-up limit Texas hold'em, is now essentially weakly solved. Furthermore, this computation formally proves the common wisdom that the dealer in the game holds a significant advantage. This result was enabled by a new algorithm, CFR, which is capable of solving extensive-form games three orders of magnitude larger than previously possible.


Heidelberg Laureate Forum

Communications of the ACM

It is fall in Heidelberg and the leaves on the trees are already turning. This is the fifth year of the Heidelberg Laureate Forum (http://www.heidelberg-laureate-forum.org/) and it continues to be a highlight of the year for me and for about 250 others who participate. This year, computer science was heavily represented. There were fewer mathematicians, but they made up for smaller numbers by their extraordinary qualifications. A new cohort of laureates was added this year: recipients of the ACM Prize for Computing.a


Social Agents

Communications of the ACM

The use of the agent paradigm to understand and design complex systems occupies an important and growing role in different areas of social and natural sciences and technology. Application areas where the agent paradigm delivers appropriate solutions include online trading,16 disaster management,10 and policy making.11 However, the two main agent approaches, Multi-Agent Systems (MAS) and Agent-Based Modeling (ABM) differ considerably in methodology, applications, and aims. MAS focus on solving specific complex problems using autonomous heterogeneous agents, while ABM is used to capture the dynamics of a (social or technical) system for analytical purposes. ABM is a form of computational modeling whereby a population of individual agents is given simple rules to govern their behavior such that global properties of the whole can be analyzed.9


Overcoming Disabilities

Communications of the ACM

Michel Fornasier, one of the presenters of the Cybathlon, uses his bionic hand prosthesis to demonstrate one of the Cybathlon disciplines. In the movie Star Wars: The Empire Strikes Back, Luke Skywalker is given a mechanical hand that moves and perform functions as well as his real hand. Konrad Kording, an avid Star Wars fan, has no doubt that advances in brain-machine interfaces (BMIs) will make this bit of science fiction a reality; he just doesn't know when. "We have applications for one channel and a few channels," says Kording, a neuroscientist and professor of Physical Medicine and Rehabilitation, Physiology, and Biomedical Engineering at Northwestern University in Evanston, IL. "The question is, what are the BMI applications with hundreds of thousands of channels, and no one knows that at the moment." The channels he's referring to are electrical wires or optical connectors that can be attached to the brain and can be controlled and measured.


Censoring Sensors

Communications of the ACM

Following the wave of U.K. terror attacks in the spring of 2017, prime minister Theresa May called on technology companies like Facebook and YouTube to create better tools for screening out controversial content--especially digital video--that directly promotes terrorism. Meanwhile, in the U.S., major advertisers including AT&T, Verizon, and WalMart have pulled ad campaigns from YouTube after discovering their content had been appearing in proximity to videos espousing terrorism, anti-Semitism, and other forms of hate speech. In response to these controversies, Google expanded its advertising rules to take a more aggressive stance against hate speech, and released a suite of tools allowing advertisers to block their ads from appearing on certain sites. The company also deployed new teams of human monitors to review videos for objectionable content. In a similar vein, Facebook announced that it would add 3,000 new employees to screen videos for inappropriate content.


Healthcare Robotics

Communications of the ACM

The use of robots in healthcare represents an exciting opportunity to help a large number of people. Robots can be used to enable people with cognitive, sensory, and motor impairments, help people who are ill or injured, support caregivers, and aid the clinical workforce. This article highlights several recent advancements on these fronts, and discusses their impact on stakeholders. It also outlines several key technological, logistical, and design challenges faced in healthcare robot adoption, and suggests possible avenues for overcoming them. Robots are "physically embodied systems capable of enacting physical change in the world."


fulltext

Communications of the ACM

Cambit pieces can be assembled to create a dozen different imaging systems. The cameras in our phones and tablets have turned us all into avid photographers, regularly using them to capture special moments and document our lives. One notable feature of camera phones is they are compact and fully automatic, enabling us to point and shoot without having to adjust any settings. However, when we need to capture photos of high aesthetic quality, we resort to more sophisticated DSLR cameras in which a variety of lenses and flashes can be used interchangeably. This flexibility is important for spanning the entire range of real-world imaging scenarios, while enabling us to be more creative.


Opportunities for Women, Minorities in Information Retrieval

Communications of the ACM

Diversity was a central theme in the ACM SIGIR 2017 held in Shinjuku Ward in Tokyo, Japan. Fuji, a view of Shinjuku sky-scrapers, including the Tokyo Metropolitan Government (Office), as seen from Keio Plaza the conference hotel, and fireworks celebrating the 40th anniversary. The colorfulness of the fireworks and the circles within and enclosing the logo represent diversity and inclusion." SIGIR 2017 featured a session on Women in IR (Information Retrieval) organized by Laura Dietz of the University of New Hampshire on the first day, just before the welcome party. A week before the conference, I received an email from the secretary of the session, Maram Hasanain, a graduate student in computer science (CS) at Qatar University, asking if I would like to prepare a one-minute introduction of myself for the session. I was so overwhelmed by her beautifully written e-mail, and the excitement of a first-time contact with someone from Qatar, that I immediately accepted her invitation.