Computers Math

In infectious disease outbreaks, digital contact tracing alone could reduce the number of cases, but not as much as manual contract tracing, new University of Otago-led research published in the Cochrane Library reveals.
Senior Research Fellow in the Department of Preventive and Social Medicine, Dr Andrew Anglemyer, led this systematic review of the effectiveness of digital technologies for identifying contacts of an identified positive case of an infectious disease, in order to isolate them and reduce further transmission of the disease.
The team of researchers summarised the findings of six observational studies from outbreaks of different infectious diseases in Sierra Leone, Botswana and the USA and six studies that simulated the spread of diseases in an epidemic with mathematical models.
The results of the review suggest the need for caution by health authorities relying heavily on digital contact tracing systems.
“Digital technologies, combined with other public health interventions, may help to prevent the spread of infectious diseases but the technology is largely unproven in real-world, outbreak settings,” Dr Anglemyer says.
“Modelling studies provide low certainty of evidence of a reduction in cases, and this only occurred when digital contact tracing solutions were used together with other public health measures such as self-isolation,” he says.

advertisement

“However, limited evidence shows that the technology itself may produce more reliable counts of contacts.”
Overall, the team of researchers from New Zealand, the USA, the UK and Australia conclude there is a place for digital technologies in contact tracing.
“The findings of our review suggest that to prevent the spread of infectious diseases, governments should consider digital technologies as a way to improve current contact tracing methods, not to replace them,” the researchers state.
“In the real world, they won’t be pitted against each other, the technology would hopefully just augment the current contact tracing methods in a given country.”
They recommend governments consider issues of privacy and equity when choosing digital contact tracing systems.

advertisement

“If governments implement digital contact tracing technologies, they should ensure that at-risk populations are not disadvantaged and they need to take privacy concerns into account.
“The COVID-19 pandemic is disproportionately affecting ethnic minorities, the elderly and people living in high deprivation. These health inequities could be magnified with the introduction of digital solutions that do not consider these at-risk populations, who are likely to have poor access to smartphones with full connectivity.”
Contact tracing teams in the studies reviewed reported that digital data entry and management systems were faster to use than paper systems for recording of new contacts and monitoring of known contacts and possibly less prone to data loss.
But the researchers conclude there is “very low certainty evidence” that contact tracing apps could make a substantial impact on the spread of COVID-19, while issues of low adoption, technological variation and health equity persist.
Accessibility or privacy and safety concerns were identified in some of the studies. Problems with system access included patchy network coverage, lack of data, technical problems with hardware or software that were unable to be resolved by local technical teams and higher staff training needs including the need for refresher training. Staff also noted concerns around accessibility and logistical issues in administering the systems, particularly in marginalised or under-developed areas of the world.
The research, published today by the Cochrane Library a collection of high-quality, independent evidence to inform healthcare decision-making, has been carried out as the COVID-19 pandemic shows no signs of waning and the World Health Organization and more than 30 countries are exploring how digital technology solutions could help stop the spread of the virus.
Senior Research Fellow Tim Chambers from the University of Otago, Wellington, and Associate Professor Matthew Parry from the Department of Statistics, were also co-authors of the paper. More

More than a decade ago, electronic medical records were all the rage, promising to transform health care and help guide clinical decisions and public health response.
With the arrival of COVID-19, researchers quickly realized that electronic medical records (EMRs) had not lived up to their full potential — largely due to widespread decentralization of records and clinical systems that cannot “talk” to one another.
Now, in an effort to circumvent these impediments, an international group of researchers has successfully created a centralized medical records repository that, in addition to rapid data collection, can perform data analysis and visualization.
The platform, described Aug.19 in Nature Digital Medicine, contains data from 96 hospitals in five countries and has yielded intriguing, albeit preliminary, clinical clues about how the disease presents, evolves and affects different organ systems across different categories of patients COVID-19.
For now, the platform represents more of a proof-of-concept than a fully evolved tool, the research team cautions, adding that the initial observations enabled by the data raise more questions than they answer.
However, as data collection grows and more institutions begin to contribute such information, the utility of the platform will evolve accordingly, the team said.

advertisement

“COVID-19 caught the world off guard and has exposed important deficiencies in our ability to use electronic medical records to glean telltale insights that could inform response during a shapeshifting pandemic,” said Isaac Kohane, senior author on the research and chair of the Department of Biomedical Informatics in the Blavatnik Institute at Harvard Medical School. “The new platform we have created shows that we can, in fact, overcome some of these challenges and rapidly collect critical data that can help us confront the disease at the bedside and beyond.”
In its report, the Harvard Medical School-led multi-institutional research team provides insights from early analysis of records from 27,584 patients and 187,802 lab tests collected in the early days of epidemic, from Jan. 1 to April 11. The data came from 96 hospitals in the United States, France, Italy, Germany and Singapore, as part of the 4CE Consortium, an international research repository of electronic medical records used to inform studies of the COVID-19 pandemic.
“Our work demonstrates that hospital systems can organize quickly to collaborate across borders, languages and different coding systems,” said study first author Gabriel Brat, HMS assistant professor of surgery at Beth Israel Deaconess Medical Center and a member of the Department of Biomedical Informatics. “I hope that our ongoing efforts to generate insights about COVID-19 and improve treatment will encourage others from around the world to join in and share data.”
The new platform underscores the value of such agile analytics in the rapid generation of knowledge, particularly during a pandemic that places extra urgency on answering key questions, but such tools must also be approached with caution and be subject to scientific rigor, according to an accompanying editorial penned by leading experts in biomedical data science.
“The bar for this work needs to be set high, but we must also be able to move quickly. Examples such as the 4CE Collaborative show that both can be achieved,” writes Harlan Krumholz, senior author on the accompanying editorial and professor of medicine and cardiology and director of the Center for Outcomes Research and Evaluation at Yale-New Haven Hospital.

advertisement

What kind of intel can EMRs provide?
In a pandemic, particularly one involving a new pathogen, rapid assessment of clinical records can provide information not only about the rate of new infections and the prevalence of disease, but also about key clinical features that can portend good or bad outcomes, disease severity and the need for further testing or certain interventions.
These data can also yield clues about differences in disease course across various demographic groups and indicative fluctuations in biomarkers associated with the function of the heart, kidney, liver, immune system and more. Such insights are especially critical in the early weeks and months after a novel disease emerges and public health experts, physicians and policymakers are flying blind. Such data could prove critical later: Indicative patterns can tell researchers how to design clinical trials to better understand the underlying drivers that influence observed outcomes. For example, if records are showing consistent changes in the footprints of a protein that heralds aberrant blood clotting, the researchers can choose to focus their monitoring, treatments on organ systems whose dysfunction is associated with these abnormalities or focus on organs that could be damaged by clots, notably the brain, heart and lungs.
The analysis of the data collected in March demonstrates that it is possible to quickly create a clinical sketch of the disease that can later be filled in as more granular details emerge, the researchers said.
In the current study, researchers tracked the following data:
Total number of COVID-19 patients
Number of intensive care unit admissions and discharges
Seven-day average of new cases per 100,000 people by country
Daily death toll
Demographic breakdown of patients
Laboratory tests to assess cardiac, immune and kidney and liver function, measure red and white blood cell counts, inflammatory markers such as C-reactive protein, as well as two proteins related to blood clotting (D-dimer) and cardiac muscle injury (troponin)
Telltale patterns
The report’s observations included:
Demographic analyses by country showed variations in the age of hospitalized patients, with Italy having the largest proportion of elderly patients (over 70 years) diagnosed with COVID-19.
At initial presentation to the hospital, patients showed remarkable consistency in lab tests measuring cardiac, immune, blood-clotting and kidney and liver function.
On day one of admission, most patients had relatively moderate disease as measured by lab tests, with initial tests showing moderate abnormalities but no indication of organ failure.
Major abnormalities were evident on day one of diagnosis for C-reactive protein — a measure of inflammation — and D-dimer protein, a chemical that measures blood clotting with test results progressively worsening in patients who went on to develop more severe disease or died.
Levels of the liver enzyme bilirubin, which indicate liver function, were initially normal across hospitals but worsened among persistently hospitalized patients, a finding suggesting that most patients did not have liver impairment on initial presentation.
Creatinine levels — which measure how well the kidneys are filtering waste — showed wide variations across hospitals, a finding that may reflect cross-country variations in testing, in the use of fluids to manage kidney function or differences in timing of patient presentation at various stages of the disease.
On average, white blood cell counts — a measure of immune response — were within normal ranges for most patients but showed elevations among those who had severe disease and remained hospitalized longer.
Even though the findings of the report are observations and cannot be used to draw conclusions, the trends they point to could provide a foundation for more focused and in-depth studies that get to the root of these observations, the team said.
“It’s clear that amid an emerging pathogen, uncertainty far outstrips knowledge,” Kohane said. “Our efforts establish a framework to monitor the trajectory of COVID-19 across different categories of patients and help us understand response to different clinical interventions.”
Co-investigators included Griffin Weber, Nils Gehlenborg, Paul Avillach, Nathan Palmer, Luca Chiovato, James Cimino, Lemuel Waitman, Gilbert Omenn, Alberto Malovini; Jason Moore, Brett Beaulieu-Jones; Valentina Tibollo; Shawn Murphy; Sehi L’Yi; Mark Keller; Riccardo Bellazzi; David Hanauer; Arnaud Serret-Larmande; Alba Gutierrez-Sacristan; John Holmes; Douglas Bell; Kenneth Mandl; Robert Follett; Jeffrey Klann; Douglas Murad; Luigia Scudeller; Mauro Bucalo; Katie Kirchoff; Jean Craig; Jihad Obeid; Vianney Jouhet; Romain Griffier; Sebastien Cossin; Bertrand Moal; Lav Patel; Antonio Bellasi; Hans Prokosch; Detlef Kraska; Piotr Sliz; Amelia Tan; Kee Yuan Ngiam; Alberto Zambelli; Danielle Mowery; Emily Schiver; Batsal Devkota; Robert Bradford; Mohamad Daniar; Christel Daniel; Vincent Benoit; Romain Bey; Nicolas Paris; Patricia Serre; Nina Orlova; Julien Dubiel; Martin Hilka; Anne Sophie Jannot; Stephane Breant; Judith Leblanc; Nicolas Griffon; Anita Burgun; Melodie Bernaux; Arnaud Sandrin; Elisa Salamanca; Sylvie Cormont; Thomas Ganslandt; Tobias Gradinger; Julien Champ; Martin Boeker; Patricia Martel; Loic Esteve; Alexandre Gramfort; Olivier Grisel; Damien Leprovost; Thomas Moreau; Gael Varoquaux; Jill-Jênn Vie; Demian Wassermann; Arthur Mensch; Charlotte Caucheteux; Christian Haverkamp; Guillaume Lemaitre; Silvano Bosari, Ian Krantz; Andrew South; Tianxi Cai.
Relevant disclosures:
Co-authors Riccardo Bellazzi of the University of Pavia and Arthur Mensch, of PSL University, are shareholders in Biomeris, a biomedical data analysis company. More

When you search for something on the internet, do you scroll through page after page of suggestions — or pick from the first few choices?
Because most people choose from the tops of these lists, they rarely see the vast majority of the options, creating a potential for bias in everything from hiring to media exposure to e-commerce.
In a new paper, Cornell University researchers introduce a tool they’ve developed to improve the fairness of online rankings without sacrificing their usefulness or relevance.
“If you could examine all your choices equally and then decide what to pick, that may be considered ideal. But since we can’t do that, rankings become a crucial interface to navigate these choices,” said computer science doctoral student Ashudeep Singh, co-first author of “Controlling Fairness and Bias in Dynamic Learning-to-Rank,” which won the Best Paper Award at the Association for Computing Machinery SIGIR Conference on Research and Development in Information Retrieval.
“For example, many YouTubers will post videos of the same recipe, but some of them get seen way more than others, even though they might be very similar,” Singh said. “And this happens because of the way search results are presented to us. We generally go down the ranking linearly and our attention drops off fast.”
The researchers’ method, called FairCo, gives roughly equal exposure to equally relevant choices and avoids preferential treatment for items that are already high on the list. This can correct the unfairness inherent in existing algorithms, which can exacerbate inequality and political polarization, and curtail personal choice.
“What ranking systems do is they allocate exposure. So how do we make sure that everybody receives their fair share of exposure?” said Thorsten Joachims, professor of computer science and information science, and the paper’s senior author. “What constitutes fairness is probably very different in, say, an e-commerce system and a system that ranks resumes for a job opening. We came up with computational tools that let you specify fairness criteria, as well as the algorithm that will provably enforce them.”
Algorithms seek the most relevant items to searchers, but because the vast majority of people choose one of the first few items in a list, small differences in relevance can lead to huge discrepancies in exposure. For example, if 51% of the readers of a news publication prefer opinion pieces that skew conservative, and 49% prefer essays that are more liberal, all of the top stories highlighted on the home page could conceivably lean conservative, according to the paper.
“When small differences in relevance lead to one side being amplified, that often causes polarization, where some people tend to dominate the conversation and other opinions get dropped without their fair share of attention,” Joachims said. “You might want to use it in an e-commerce system to make sure that if you’re producing a product that 30% of people like, you’re getting a certain amount of exposure based on that. Or if you have a resume database, you could formulate safeguards to make sure it’s not discriminating by race or gender.”
The research was partly supported by the National Science Foundation and by Workday.

Story Source:
Materials provided by Cornell University. Original written by Melanie Lefkowitz. Note: Content may be edited for style and length. More

New research led by Flinders University PhD candidate Jasmine Petersen examining commercial physical activity apps has found that the social components of these apps hold great potential to increase physical activity engagement.
Sharing physical activity outcomes and progress to app communities and social networking platforms provides the necessary encouragement for people to engage more enthusiastically with their apps.
“Sharing posts and receiving encouragement provides the social support many people need to stay motivated with exercise programs — and this doesn’t change across different age groups,” says study co-author Dr Ivanka Prichard, from Flinders University’s Caring Futures Institute.
The study — “Psychological mechanisms underlying the relationship between commercial physical activity app use and physical activity engagement,” by Jasmine Petersen, Lucy Lewis, Eva Kemps and Ivanka Prichard — is published in Psychology of Sport and Exercise.
The study examined close to 1300 adults (88% female, aged between 18 and 83 years), over half of whom used a commercial physical activity app (e.g. Fitbit, Garmin, Strava). Results found that more competitive individuals responded best to the apps, engaging in significantly higher levels of physical activity due to the game-like incentives and rewards built into the apps.
Dr Prichard says this suggests that people with a general disposition toward competition may benefit most from using activity apps.
“App users are motivated by both the enjoyment derived from physical activity (intrinsic motivation) and the personal value placed on the outcomes of physical activity (identified regulation), and these combined motivations result in greater engagement in physical activity,” says Ms Petersen.
This study shows that the social components of physical activity apps are particularly beneficial in promoting engagement in physical activity due to their capacity to facilitate social support, and positively influence motivation and beliefs in one’s ability to perform physical activity.
However, it was also found that online interactions can have a negative effect on exercisers if social networking is used to make direct comparisons.
“Engagement in comparisons was associated with lower self-efficacy and higher external regulation, and in turn, lower physical activity,” says Dr Prichard, emphasising the importance of exercising for enjoyment and the benefits that exercise can provide to general health.
The team are now following up participants to see how commercial physical activity apps might support physical activity behaviour in light of COVID-19 restrictions.

Story Source:
Materials provided by Flinders University. Original written by Megan Andrews. Note: Content may be edited for style and length. More

Simply put, string theory is a proposed method of explaining everything. Actually, there’s nothing simple about it. String theory is a theoretical framework from physics that describes one-dimensional, vibrating fibrous objects called “strings,” which propagate through space and interact with each other. Piece by piece, energetic minds are discovering and deciphering fundamental strings of the physical universe using mathematical models. Among these intrepid explorers are Utah State University mathematicians Thomas Hill and his faculty mentor, Andreas Malmendier.
With colleague Adrian Clingher of the University of Missouri-St. Louis, the team published findings about two branches of string theory in the paper, “The Duality Between F-theory and the Heterotic String in D=8 with Two Wilson Lines,” in the August 7, 2020 online edition of ‘Letters in Mathematical Physics.’ The USU researchers’ work is supported by a grant from the Simons Foundation.
“We studied a special family of K3 surfaces — compact, connected complex surfaces of dimension 2 — which are important geometric tools for understanding symmetries of physical theories,” says Hill, who graduated from USU’s Honors Program with a bachelor’s degree in mathematics in 2018 and completed a master’s degree in mathematics this past spring. “In this case, we were examining a string duality between F-theory and heterotic string theory in eight dimensions.”
Hill says the team proved the K3 surfaces they investigated admit four unique ways to slice the surfaces as Jacobian elliptic fibrations, formations of torus-shaped fibers. The researchers constructed explicit equations for each of these fibrations.
“An important part of this research involves identifying certain geometric building blocks, called ‘divisors,’ within each K3 surface,” he says. “Using these divisors, crucial geometric information is then encoded in an abstract graph.”
This process, Hill says, enables researchers to investigate symmetries of underlying physical theories demonstrated by the graph.
“You can think of this family of surfaces as a loaf of bread and each fibration as a ‘slice’ of that loaf,” says Malmendier, associate professor in USU’s Department of Mathematics and Statistics. “By examining the sequence of slices, we can visualize, and better understand, the entire loaf.”
The undertaking described in the paper, he says, represents hours of painstaking “paper and pencil” work to prove theorems of each of the four fibrations, followed by pushing each theorem through difficult algebraic formulas.
“For the latter part of this process, we used Maple Software and the specialized Differential Geometry Package developed at USU, which streamlined our computational efforts,” Malmendier says.

Story Source:
Materials provided by Utah State University. Original written by Mary-Ann Muffoletto. Note: Content may be edited for style and length. More

Jonathan Boreyko, an associate professor in mechanical engineering, has developed an aircraft thermal management technology that stands ready for adaptation into other areas.
The research was published in Advanced Functional Materials on Aug. 18, 2020.
Boreyko was the recipient of a Young Investigator Research Program award in 2016, given by the Air Force Office of Scientific Research. This award funded the development of planar bridging-droplet thermal diodes, a novel approach to thermal management. Boreyko’s research has shown this new approach to be both highly efficient and extremely versatile.
“We are hopeful that the one-way heat transfer of our bridging-droplet diode will enable the smart thermal management of electronics, aircraft, and spacecraft,” said Boreyko.
Diodes are a special kind of device that allow heat to conduct in only one direction by use of engineered materials. For management of heat, diodes are attractive because they enable the dumping of heat entering one side, while resisting heat on the opposite side. In the case of aircraft (the focus of Boreyko’s funding), heat is absorbed from an overheated plane, but resisted from the outside environment.
Boreyko’s team created a diode using two copper plates in a sealed environment, separated by a microscopic gap. The first plate is engineered with a wick structure to hold water, while the opposite plate is coated with a water-repelling (hydrophobic) layer. The water on the wicking surface receives heat, causing evaporation into steam. As the steam moves across the narrow gap, it cools and condenses into dew droplets on the hydrophobic side. These dew droplets grow large enough to “bridge” the gap and get sucked back into the wick, starting the process again.
If the source of heat were instead applied the hydrophobic side, no steam can be produced because the water remains trapped in the wick. This is why the device can only conduct heat in one direction.
What does this look like in practice? An object producing heat, like a CPU chip, overheats if this heat is not continually removed. Boreyko’s invention is affixed to this heat source. Generated heat is transferred through the conducting plate, into the water. Water turns to steam and moves away from the source of the heat. The hydrophobic, nonconducting side prevents heat from entering via the air or other heat sources that may be near, allowing the diode to manage the heat only from its main subject.
Boreyko’s team measured a nearly 100-fold increase in heat conduction when the wicked side was heated, compared to the hydrophobic side. This is a significant improvement to existing thermal diodes. According to Boreyko, current diodes are either not very effective, only conducting a few times more heat in one direction, or require gravity. This new bridging-droplet thermal diode can be used upright, sideways, or even upside-down, and would even work in space where gravity is negligible.
The team has filed a provisional patent and is in search of industry partners to carry on the work.

Story Source:
Materials provided by Virginia Tech. Note: Content may be edited for style and length. More

Patients who need surgery to fix major bone fractures use fewer opioid pills after their procedure if they’re reminded of their values — and those reminders don’t necessarily need to come from a doctor, according to a new study published in the Journal of Medical Internet Research.
“We showed that opioid medication utilization could be decreased by more than a third in an at-risk patient population by delivering psychotherapy via a chatbot,” said the study’s lead author, Christopher Anthony, MD, the associate director of Hip Preservation at Penn Medicine and an assistant professor of Orthopaedic Surgery. “While it must be tested with future investigations, we believe our findings are likely transferrable to other patient populations.”
Although opioids can be appropriate to treat the pain that results from an injury like a broken leg or arm, there is a concern that a large prescription of opioids might be an on-ramp to dependence for many. The researchers — who included Edward Octavio Rojas, MD, a resident in Orthopaedic Surgery at the University of Iowa Hospitals & Clinics — believe a low-effort, patient-centered approach to reducing the number of opioids taken can be a valuable method for cutting into the opioid epidemic.
To test this approach, 76 patients who went to a Level 1 Trauma Center at the University of Iowa Hospitals & Clinics for fractures that required a surgery to fix were randomly divided into two groups. Although each group received the same prescription of an opioid medication for pain, just one group was enrolled in a daily text-messaging program. That group received two daily text messages to their phones for two weeks after their procedure from an automated “chatbot” — a computer that uses artificial intelligence to send messages — starting the day after their surgery. The goal of each message was to help focus patients and hone their coping skills for the inevitable pain after such a procedure.
While they don’t expressly discourage using opioid pills, the messages, designed by a pain psychologist who specialized in acceptance and commitment therapy (ACT), are designed to direct thoughts away from taking a painkiller.
Each message fell under one of six “core principles”: Values, Acceptance, Present Moment Awareness, Self-As-Context, Committed Action, and Diffusion.
So, for example, a message a patient could receive under the Acceptance principle could be: “Feelings of pain and feelings about your experience of pain are normal after surgery. Acknowledge and accept these feelings as part of the recovery process. Remember how you feel now is temporary and your healing process will continue. Call to mind pleasant feelings or thoughts that you experienced today.” Or a Committed Action message might urge a patient to work toward a life goal, even if some pain might be present.
Overall, the patients who didn’t receive the messages took 41 opioid tablets after their surgeries, on average. The group who were regularly contacted by the chatbot averaged just 26, a 37 percent difference. Moreover, they reported less pain, overall, just two weeks after their procedure.
Importantly, the messages each patient received were not curated for their individual personality. This type of effectiveness was seen without the messages needing to be overly personalized. Combined with the using a chatbot instead of a human-intensive effort, this could be a low-cost, low-effort for orthopaedic and other procedures that provides significant protection from opioid dependence.
“A realistic goal for this type of work is to decrease opioid utilization to as few tablets as possible, with the ultimate goal being to eliminate the need for opioid medication in the setting of fracture care,” Anthony said.
This study was funded by a grant from the Orthopaedic Trauma Association.
Co-authors included Valerie Keffala, PhD; Natalie Ann Glass, PhD; Benjamin J. Miller, MD; Mathew Hogue, MD; Michael Wiley, MD; Matthew Karam, MD; and John Lawrence Marsh, MD, all of the University of Iowa, as well as Apurva Shah, MD, of the Children’s Hospital of Philadelphia. More

COMPUTER SCIENCE Researchers from the University of Copenhagen and the Technical University of Denmark (DTU) thought that they were five years away from solving a math riddle from the 1980’s. In reality, and without knowing, they had nearly cracked the problem and had just given away much of the solution in a research article. The solution could be used to improve tomorrow’s phones and computers.
Jacob Holm and Eva Rotenberg
The two computer scientists, Assistant Professor Jacob Holm of UCPH and Associate Professor Eva Rotenberg of DTU almost gave their solution away in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the math riddle.
A veritable brain teaser. That’s how one can safely describe this mathematical problem in the discipline of graph theory. Two mathematicians from the University of Copenhagen’s Department of Computer Science and DTU have now solved a problem that the world’s quickest and most clever have been struggling with since the 1980’s.
The two computer scientists, Assistant Professor Jacob Holm of UCPH and Associate Professor Eva Rotenberg of DTU almost gave their solution away in the summer of 2019, after submitting a research article that became the precursor to the article in which they finally solved the math riddle.
“We had nearly given up on getting the last piece and solving the riddle. We thought we had a minor result, one that was interesting, but in no way solved the problem. We guessed that there would be another five years of work, at best, before we would be able to solve the puzzle,” explains Jacob Holm, who is a part of BARC, the algorithm section at UCPH’s Department of Computer Science.

advertisement

The three utilities problem
In 1913, a precursor to the now solved mathematical conundrum was published in “The Strand Magazine” as “The Three Utilities Problem”. It caused the magazine’s readers to scratch their heads and ponder. In the problem, each of three cottages must have water, gas and electricity, while the “lines” between the houses and water, electricity and gas may not cross each other — which is not possible.
A solution between the lines
Simply put, the puzzle is about how to connect a number of points in a graph without allowing the lines connecting them to cross. And how, with a mathematical calculation — an algorithm — you can make changes to an extensive “graph network” to ensure that no lines intersect without having to start all over again. Properties that can be used for, among other things, building immense road networks or the tiny innards of computers, where electrical circuitry on circuit boards may not cross.
Jacob Holm has been interested in the mathematical conundrum since 1998, but the answer was only revealed while the two researchers were reading through their already submitted research article. In the meantime, the researchers heard about a novel mathematical technique that they realized could be applied to the problem.

advertisement

“While reading our research article, we suddenly realized that the solution was before our eyes. Our next reaction was ‘oh no – we’ve shot ourselves in the foot and given away the solution,’ says Associate Professor Eva Rotenberg of DTU.
About graph theory
A GRAPH is a very simple construction used to model things that can be described as objects and the connections between them. Graph theory is both an area of mathematics and an important tool in computer science.
In this context, a graph can be illustrated by a diagram consisting of a number of points (nodes, vertices) associated with a number of lines (edges). Each edge is illustrated as a line (or curved piece) with nodes as its two endpoints.
About the solution
There are two kinds of updates in dynamic graphs: One can delete an edge and you can insert a new edge. These two operations must be made by the user, while an algorithm keeps track of the network’s drawing at all times. This is the algorithm that the researchers have found the recipe for.
Read the research article: https://arxiv.org/abs/1911.03449
Could be used for computer electronics
This is when the two researchers got busy writing the research paper and tying up loose ends to solve the conundrum that Holm had been working on intermittently since 1998.
“We worked on the article non-stop, for five to six weeks. And, it ended up filling more than 80 pages,” says Eva Rotenberg.
Fortunately, no one beat them to the solution and the two researchers were able to present their results at the main theoretical computer science conferences, which were meant to be held in Chicago, but ended up being held virtually.
So, what can the solution to this mathematical conundrum be used for? The two researchers don’t know for sure, but they have a few suggestions.
“Our research is basic research, so we rarely know what it will end up being used for. Even from the start, we find applications difficult to imagine,” says Jacob Holm, who adds:
“the design of microchips and circuit boards, found in all electronics, could be an area where our result ends up being used. When drawing wires on a circuit board, they must never intersect. Otherwise, short circuits will occur. The same applies to microchips, which contain millions of transistors and for which one must have a graph drawing.”
### More