Aurelia Butler

Aston University researchers are part of a team that has sent data at a record rate of 402 terabits per second using commercially available optical fibre.
This beats their previous record, announced in March 2024, of 301 terabits or 301,000,000 megabits per second using a single, standard optical fibre.
“If compared to the internet connection speed recommendations of Netflix, of 3 Mbit/s or higher, for a watching a HD movie, this speed is over 100 million times faster.
The speed was achieved by using a wider spectrum, using six bands rather than the previous four, which increased capacity for data sharing. Normally just one or two bands are used.
The international research team included Professor Wladek Forysiak and Dr Ian Philips who are members of the University’s Aston Institute of Photonic Technologies (AIPT). Led by the Photonic Network Laboratory of the National Institute of Information and Communications Technology (NICT) which is based in Tokyo, Japan it also including Nokia Bell labs of the USA.
Together they achieved the feat by constructing the first optical transmission system covering six wavelength bands (O,E,S,C,L and U) used in fibre optical communication. Aston University contributed specifically by building a set of U-band Raman amplifiers, the longest part of the combined wavelength spectrum, where conventional doped fibre amplifiers are not presently available from commercial sources.
Optical fibres are small tubular strands of glass that pass information using light unlike regular copper cables that can’t carry data at such speeds.

As well as increasing capacity by approximately a third, the technique uses so-called “standard fibre” that is already deployed in huge quantities worldwide, so there would be no need to install new specialist cables.
As demand for data from business and individuals increases this new discovery could help keep broadband prices stable despite an improvement in capacity and speed.
Aston University’s Dr Philips said: “This finding could help increase capacity on a single fibre so the world would have a higher performing system.
“The newly developed technology is expected to make a significant contribution to expand the communication capacity of the optical communication infrastructure as future data services rapidly increase demand.”
His colleague Professor Wladek Forysiak added: ‘This is a ‘hero experiment’ made possible by a multi-national team effort and very recent technical advances in telecommunications research laboratories from across the world’.”
The results of the experiment were accepted as a post-deadline paper at the 47th International Conference on Optical Fiber Communications (OFC 2024) in the USA on 28 March.
To help support some of its work in this area Aston University has received funding from EPSRC (UKRI), the Royal Society (RS Exchange grant with NICT) and the EU (European Training Network). More

For hundreds of years, the clarity and magnification of microscopes were ultimately limited by the physical properties of their optical lenses. Microscope makers pushed those boundaries by making increasingly complicated and expensive stacks of lens elements. Still, scientists had to decide between high resolution and a small field of view on the one hand or low resolution and a large field of view on the other.
In 2013, a team of Caltech engineers introduced a microscopy technique called FPM (for Fourier ptychographic microscopy). This technology marked the advent of computational microscopy, the use of techniques that wed the sensing of conventional microscopes with computer algorithms that process detected information in new ways to create deeper, sharper images covering larger areas. FPM has since been widely adopted for its ability to acquire high-resolution images of samples while maintaining a large field of view using relatively inexpensive equipment.
Now the same lab has developed a new method that can outperform FPM in its ability to obtain images free of blurriness or distortion, even while taking fewer measurements. The new technique, described in a paper that appeared in the journal Nature Communications, could lead to advances in such areas as biomedical imaging, digital pathology, and drug screening.
The new method, dubbed APIC (for Angular Ptychographic Imaging with Closed-form method), has all the advantages of FPM without what could be described as its biggest weakness — namely, that to arrive at a final image, the FPM algorithm relies on starting at one or several best guesses and then adjusting a bit at a time to arrive at its “optimal” solution, which may not always be true to the original image.
Under the leadership of Changhuei Yang, the Thomas G. Myers Professor of Electrical Engineering, Bioengineering, and Medical Engineering and an investigator with the Heritage Medical Research Institute, the Caltech team realized that it was possible to eliminate this iterative nature of the algorithm.
Rather than relying on trial and error to try to home in on a solution, APIC solves a linear equation, yielding details of the aberrations, or distortions introduced by a microscope’s optical system. Once the aberrations are known, the system can correct for them, basically performing as though it is ideal, and yielding clear images covering large fields of view.
“We arrive at a solution of the high-resolution complex field in a closed-form fashion, as we now have a deeper understanding in what a microscope captures, what we already know, and what we need to truly figure out, so we don’t need any iteration,” says Ruizhi Cao (PhD ’24), co-lead author on the paper, a former graduate student in Yang’s lab, and now a postdoctoral scholar at UC Berkeley. “In this way, we can basically guarantee that we are seeing the true final details of a sample.”
As with FPM, the new method measures not only the intensity of the light seen through the microscope but also an important property of light called “phase,” which is related to the distance that light travels. This property goes undetected by human eyes but contains information that is very useful in terms of correcting aberrations. It was in solving for this phase information that FPM relied on a trial-and-error method, explains Cheng Shen (PhD ’23), co-lead author on the APIC paper, who also completed the work while in Yang’s lab and is now a computer vision algorithm engineer at Apple. “We have proven that our method gives you an analytical solution and in a much more straightforward way. It is faster, more accurate, and leverages some deep insights about the optical system.”

Beyond eliminating the iterative nature of the phase-solving algorithm, the new technique also allows researchers to gather clear images over a large field of view without repeatedly refocusing the microscope. With FPM, if the height of the sample varied even a few tens of microns from one section to another, the person using the microscope would have to refocus in order to make the algorithm work. Since these computational microscopy techniques frequently involve stitching together more than 100 lower-resolution images to piece together the larger field of view, that means APIC can make the process much faster and prevent the possible introduction of human error at many steps.
“We have developed a framework to correct for the aberrations and also to improve resolution,” says Cao. “Those two capabilities can be potentially fruitful for a broader range of imaging systems.”
Yang says the development of APIC is vital to the broader scope of work his lab is currently working on to optimize image data input for artificial intelligence (AI) applications. “Recently, my lab showed that AI can outperform expert pathologists at predicting metastatic progression from simple histopathology slides from lung cancer patients,” says Yang. “That prediction ability is exquisitely dependent on obtaining uniformly in-focus and high-quality microscopy images, something that APIC is highly suited for.” More

A team of researchers led by the University of California San Diego has developed a soft, stretchy electronic device capable of simulating the feeling of pressure or vibration when worn on the skin. This device, reported in a paper published in Science Robotics, represents a step towards creating haptic technologies that can reproduce a more varied and realistic range of touch sensations.
The device consists of a soft, stretchable electrode attached to a silicone patch. It can be worn like a sticker on either the fingertip or forearm. The electrode, in direct contact with the skin, is connected to an external power source via wires. By sending a mild electrical current through the skin, the device can produce sensations of either pressure or vibration depending on the signal’s frequency.
“Our goal is to create a wearable system that can deliver a wide gamut of touch sensations using electrical signals — without causing pain for the wearer,” said study co-first author Rachel Blau, a nano engineering postdoctoral researcher at the UC San Diego Jacobs School of Engineering.
Existing technologies that recreate a sense of touch through electrical stimulation often induce pain due to the use of rigid metal electrodes, which do not conform well to the skin. The air gaps between these electrodes and the skin can result in painful electrical currents.
To address these issues, Blau and a team of researchers led by Darren Lipomi, a professor in the Aiiso Yufeng Li Family Department of Chemical and Nano Engineering at UC San Diego, developed a soft, stretchy electrode that seamlessly conforms to the skin.
The electrode is made of a new polymer material constructed from the building blocks of two existing polymers: a conductive, rigid polymer known as PEDOT:PSS, and a soft, stretchy polymer known as PPEGMEA. “By optimizing the ratio of these [polymer building blocks], we molecularly engineered a material that is both conductive and stretchable,” said Blau.
The polymer electrode is laser-cut into a spring-shaped, concentric design and attached to a silicone substrate. “This design enhances the electrode’s stretchability and ensures that the electrical current targets a specific location on the skin, thus providing localized stimulation to prevent any pain,” said Abdulhameed Abdal, a Ph.D. student in the Department of Mechanical and Aerospace Engineering at UC San Diego and the study’s other co-first author. Abdal and Blau worked on the synthesis and fabrication of the electrode with UC San Diego nano engineering undergraduate students Yi Qie, Anthony Navarro and Jason Chin.

In tests, the electrode device was worn on the forearm by 10 participants. In collaboration with behavioral scientists and psychologists at the University of Amsterdam, the researchers first identified the lowest level of electrical current detectable. They then adjusted the frequency of the electrical stimulation, allowing participants to experience sensations categorized as either pressure or vibration.
“We found that by increasing the frequency, participants felt more vibration rather than pressure,” said Abdal. “This is interesting because biophysically, it was never known exactly how current is perceived by the skin.”
The new insights could pave the way for the development of advanced haptic devices for applications such as virtual reality, medical prosthetics and wearable technology.
This work was supported by the National Science Foundation Disability and Rehabilitation Engineering program (CBET-2223566). This work was performed in part at the San Diego Nanotechnology Infrastructure (SDNI) at UC San Diego, a member of the National Nanotechnology Coordinated Infrastructure, which is supported by the National Science Foundation (grant ECCS-1542148). More

Osteoporosis is so difficult to detect in early stage it’s called the “silent disease.” What if artificial intelligence could help predict a patient’s chances of having the bone-loss disease before ever stepping into a doctor’s office?
Tulane University researchers made progress toward that vision by developing a new deep learning algorithm that outperformed existing computer-based osteoporosis risk prediction methods, potentially leading to earlier diagnoses and better outcomes for patients with osteoporosis risk.
Their results were recently published in Frontiers in Artificial Intelligence.
Deep learning models have gained notice for their ability to mimic human neural networks and find trends within large datasets without being specifically programmed to do so. Researchers tested the deep neural network (DNN) model against four conventional machine learning algorithms and a traditional regression model, using data from over 8,000 participants aged 40 and older in the Louisiana Osteoporosis Study. The DNN achieved the best overall predictive performance, measured by scoring each model’s ability to identify true positives and avoid mistakes.
“The earlier osteoporosis risk is detected, the more time a patient has for preventative measures,” said lead author Chuan Qiu, a research assistant professor at the Tulane School of Medicine Center for Biomedical Informatics and Genomics. “We were pleased to see our DNN model outperform other models in accurately predicting the risk of osteoporosis in an aging population.”
In testing the algorithms using a large sample size of real-world health data, the researchers were also able to identify the 10 most important factors for predicting osteoporosis risk: weight, age, gender, grip strength, height, beer drinking, diastolic pressure, alcohol drinking, years of smoking, and income level.
Notably, the simplified DNN model using these top 10 risk factors performed nearly as well as the full model which included all risk factors.
While Qiu admitted that there is much more work to be done before an AI platform can be used by the public to predict an individual’s risk of osteoporosis, he said identifying the benefits of the deep learning model was a step in that direction.
“Our final aim is to allow people to enter their information and receive highly accurate osteoporosis risk scores to empower them to seek treatment to strengthen their bones and reduce any further damage,” Qiu said. More

The growing prevalence of high-speed wireless communication devices, from 5G mobile phones to sensors for autonomous vehicles, is leading to increasingly crowded airwaves. This makes the ability to block interfering signals that can hamper device performance an even more important — and more challenging — problem.
With these and other emerging applications in mind, MIT researchers demonstrated a new millimeter-wave multiple-input-multiple-output (MIMO) wireless receiver architecture that can handle stronger spatial interference than previous designs. MIMO systems have multiple antennas, enabling them to transmit and receive signals from different directions. Their wireless receiver senses and blocks spatial interference at the earliest opportunity, before unwanted signals have been amplified, which improves performance.
Key to this MIMO receiver architecture is a special circuit that can target and cancel out unwanted signals, known as a nonreciprocal phase shifter. By making a novel phase shifter structure that is reconfigurable, low-power, and compact, the researchers show how it can be used to cancel out interference earlier in the receiver chain.
Their receiver can block up to four times more interference than some similar devices. In addition, the interference-blocking components can be switched on and off as needed to conserve energy.
In a mobile phone, such a receiver could help mitigate signal quality issues that can lead to slow and choppy Zoom calling or video streaming.
“There is already a lot of utilization happening in the frequency ranges we are trying to use for new 5G and 6G systems. So, anything new we are trying to add should already have these interference-mitigation systems installed. Here, we’ve shown that using a nonreciprocal phase shifter in this new architecture gives us better performance. This is quite significant, especially since we are using the same integrated platform as everyone else,” says Negar Reiskarimian, the X-Window Consortium Career Development Assistant Professor in the Department of Electrical Engineering and Computer Science (EECS), a member of the Microsystems Technology Laboratories and Research Laboratory of Electronics (RLE), and the senior author of a paper on this receiver.
Reiskarimian wrote the paper with EECS graduate students Shahabeddin Mohin, who is the lead author, Soroush Araei, and Mohammad Barzgari, an RLE postdoc. The work was recently presented at the IEEE Radio Frequency Circuits Symposium and received the Best Student Paper Award.

Blocking interference
Digital MIMO systems have an analog and a digital portion. The analog portion uses antennas to receive signals, which are amplified, down-converted, and passed through an analog-to-digital converter before being processed in the digital domain of the device. In this case, digital beamforming is required to retrieve the desired signal.
But if a strong, interfering signal coming from a different direction hits the receiver at the same time as a desired signal, it can saturate the amplifier so the desired signal is drowned out. Digital MIMOs can filter out unwanted signals, but this filtering occurs later in the receiver chain. If the interference is amplified along with the desired signal, it is more difficult to filter out later.
“The output of the initial low-noise amplifier is the first place you can do this filtering with minimal penalty, so that is exactly what we are doing with our approach,” Reiskarimian says.
The researchers built and installed four nonreciprocal phase shifters immediately at the output of the first amplifier in each receiver chain, all connected to the same node. These phase shifters can pass signal in both directions and sense the angle of an incoming interfering signal. The devices can adjust their phase until they cancel out the interference.
The phase of these devices can be precisely tuned, so they can sense and cancel an unwanted signal before it passes to the rest of the receiver, blocking interference before it affects any other parts of the receiver. In addition, the phase shifters can follow signals to continue blocking interference if it changes location.

“If you start getting disconnected or your signal quality goes down, you can turn this on and mitigate that interference on the fly. Because ours is a parallel approach, you can turn it on and off with minimal effect on the performance of the receiver itself,” Reiskarimian adds.
A compact device
In addition to making their novel phase shifter architecture tunable, the researchers designed them to use less space on the chip and consume less power than typical nonreciprocal phase shifters.
Once the researchers had done the analysis to show their idea would work, their biggest challenge was translating the theory into a circuit that achieved their performance goals. At the same time, the receiver had to meet strict size restrictions and a tight power budget, or it wouldn’t be useful in real-world devices.
In the end, the team demonstrated a compact MIMO architecture on a 3.2-square-millimeter chip that could block signals which were up to four times stronger than what other devices could handle. Simpler than typical designs, their phase shifter architecture is also more energy efficient.
Moving forward, the researchers want to scale up their device to larger systems, as well as enable it to perform in the new frequency ranges utilized by 6G wireless devices. These frequency ranges are prone to powerful interference from satellites. In addition, they would like to adapt nonreciprocal phase shifters to other applications.
This research was supported, in part, by the MIT Center for Integrated Circuits and Systems. More

Artificial intelligence models often play a role in medical diagnoses, especially when it comes to analyzing images such as X-rays. However, studies have found that these models don’t always perform well across all demographic groups, usually faring worse on women and people of color.
These models have also been shown to develop some surprising abilities. In 2022, MIT researchers reported that AI models can make accurate predictions about a patient’s race from their chest X-rays — something that the most skilled radiologists can’t do.
That research team has now found that the models that are most accurate at making demographic predictions also show the biggest “fairness gaps” — that is, discrepancies in their ability to accurately diagnose images of people of different races or genders. The findings suggest that these models may be using “demographic shortcuts” when making their diagnostic evaluations, which lead to incorrect results for women, Black people, and other groups, the researchers say.
“It’s well-established that high-capacity machine-learning models are good predictors of human demographics such as self-reported race or sex or age. This paper re-demonstrates that capacity, and then links that capacity to the lack of performance across different groups, which has never been done,” says Marzyeh Ghassemi, an MIT associate professor of electrical engineering and computer science, a member of MIT’s Institute for Medical Engineering and Science, and the senior author of the study.
The researchers also found that they could retrain the models in a way that improves their fairness. However, their approached to “debiasing” worked best when the models were tested on the same types of patients they were trained on, such as patients from the same hospital. When these models were applied to patients from different hospitals, the fairness gaps reappeared.
“I think the main takeaways are, first, you should thoroughly evaluate any external models on your own data because any fairness guarantees that model developers provide on their training data may not transfer to your population. Second, whenever sufficient data is available, you should train models on your own data,” says Haoran Zhang, an MIT graduate student and one of the lead authors of the new paper. MIT graduate student Yuzhe Yang is also a lead author of the paper, which will appear in Nature Medicine. Judy Gichoya, an associate professor of radiology and imaging sciences at Emory University School of Medicine, and Dina Katabi, the Thuan and Nicole Pham Professor of Electrical Engineering and Computer Science at MIT, are also authors of the paper.
Removing bias
As of May 2024, the FDA has approved 882 AI-enabled medical devices, with 671 of them designed to be used in radiology. Since 2022, when Ghassemi and her colleagues showed that these diagnostic models can accurately predict race, they and other researchers have shown that such models are also very good at predicting gender and age, even though the models are not trained on those tasks.

“Many popular machine learning models have superhuman demographic prediction capacity — radiologists cannot detect self-reported race from a chest X-ray,” Ghassemi says. “These are models that are good at predicting disease, but during training are learning to predict other things that may not be desirable.” In this study, the researchers set out to explore why these models don’t work as well for certain groups. In particular, they wanted to see if the models were using demographic shortcuts to make predictions that ended up being less accurate for some groups. These shortcuts can arise in AI models when they use demographic attributes to determine whether a medical condition is present, instead of relying on other features of the images.
Using publicly available chest X-ray datasets from Beth Israel Deaconess Medical Center in Boston, the researchers trained models to predict whether patients had one of three different medical conditions: fluid buildup in the lungs, collapsed lung, or enlargement of the heart. Then, they tested the models on X-rays that were held out from the training data.
Overall, the models performed well, but most of them displayed “fairness gaps” — that is, discrepancies between accuracy rates for men and women, and for white and Black patients.
The models were also able to predict the gender, race, and age of the X-ray subjects. Additionally, there was a significant correlation between each model’s accuracy in making demographic predictions and the size of its fairness gap. This suggests that the models may be using demographic categorizations as a shortcut to make their disease predictions.
The researchers then tried to reduce the fairness gaps using two types of strategies. For one set of models, they trained them to optimize “subgroup robustness,” meaning that the models are rewarded for having better performance on the subgroup for which they have the worst performance, and penalized if their error rate for one group is higher than the others.
In another set of models, the researchers forced them to remove any demographic information from the images, using “group adversarial” approaches. Both of these strategies worked fairly well, the researchers found.

“For in-distribution data, you can use existing state-of-the-art methods to reduce fairness gaps without making significant trade-offs in overall performance,” Ghassemi says. “Subgroup robustness methods force models to be sensitive to mispredicting a specific group, and group adversarial methods try to remove group information completely.”
Not always fairer
However, those approaches only worked when the models were tested on data from the same types of patients that they were trained on — for example, only patients from the Beth Israel Deaconess Medical Center dataset.
When the researchers tested the models that had been “debiased” using the BIDMC data to analyze patients from five other hospital datasets, they found that the models’ overall accuracy remained high, but some of them exhibited large fairness gaps.
“If you debias the model in one set of patients, that fairness does not necessarily hold as you move to a new set of patients from a different hospital in a different location,” Zhang says.
This is worrisome because in many cases, hospitals use models that have been developed on data from other hospitals, especially in cases where an off-the-shelf model is purchased, the researchers say.
“We found that even state-of-the-art models which are optimally performant in data similar to their training sets are not optimal — that is, they do not make the best trade-off between overall and subgroup performance — in novel settings,” Ghassemi says. “Unfortunately, this is actually how a model is likely to be deployed. Most models are trained and validated with data from one hospital, or one source, and then deployed widely.”
The researchers found that the models that were debiased using group adversarial approaches showed slightly more fairness when tested on new patient groups that those debiased with subgroup robustness methods. They now plan to try to develop and test additional methods to see if they can create models that do a better job of making fair predictions on new datasets.
The findings suggest that hospitals that use these types of AI models should evaluate them on their own patient population before beginning to use them, to make sure they aren’t giving inaccurate results for certain groups.
The research was funded by a Google Research Scholar Award, the Robert Wood Johnson Foundation Harold Amos Medical Faculty Development Program, RSNA Health Disparities, the Lacuna Fund, the Gordon and Betty Moore Foundation, the National Institute of Biomedical Imaging and Bioengineering, and the National Heart, Lung, and Blood Institute. More

In a breakthrough that brings to mind Lucky Luke — the man who shoots faster than his shadow — Rasmus Kyng and his team have developed a superfast algorithm that looks set to transform an entire field of research. The groundbreaking work by Kyng’s team involves what is known as a network flow algorithm, which tackles the question of how to achieve the maximum flow in a network while simultaneously minimising transport costs.
Imagine you are using the European transportation network and looking for the fastest and cheapest route to move as many goods as possible from Copenhagen to Milan. Kyng’s algorithm can be applied in such cases to calculate the optimal, lowest-cost traffic flow for any kind of network — be it rail, road, water or the internet. His algorithm performs these computations so fast that it can deliver the solution at the very moment a computer reads the data that describes the network.
Computations as fast as a network is big
Before Kyng, no one had ever managed to do that — even though researchers have been working on this problem for some 90 years. Previously, it took significantly longer to compute the optimal flow than to process the network data. And as the network became larger and more complex, the required computing time increased much faster, comparatively speaking, than the actual size of the computing problem. This is why we also see flow problems in networks that are too large for a computer to even calculate.
Kyng’s approach eliminates this problem: using his algorithm, computing time and network size increase at the same rate — a bit like going on a hike and constantly keeping up the same pace however steep the path gets. A glance at the raw figures shows just how far we have come: until the turn of the millennium, no algorithm managed to compute faster than m1.5, where m stands for the number of connections in a network that the computer has to calculate, and just reading the network data once takes m time. In 2004, the computing speed required to solve the problem was successfully reduced to m1.33. Using Kyng’s algorithm, the “additional” computing time required to reach the solution after reading the network data is now negligible.
Like a Porsche racing a horse-drawn carriage
The ETH Zurich researchers have thus developed what is, in theory, the fastest possible network flow algorithm. Two years ago, Kyng and his team presented mathematical proof of their concept in a groundbreaking paper. Scientists refer to these novel, almost optimally fast algorithms as “almost-linear-time algorithms,” and the community of theoretical computer scientists responded to Kyng’s breakthrough with a mixture of amazement and enthusiasm.

Kyng’s doctoral supervisor, Daniel A. Spielman, Professor of Applied Mathematics and Computer Science at Yale and himself a pioneer and doyen in this field, compared the “absurdly fast” algorithm to a Porsche overtaking horse-drawn carriages. As well as winning the 2022 Best Paper Award at the IEEE Annual Symposium on Foundations of Computer Science (FOCS), their paper was also highlighted in the computing journal Communications of the ACM, and the editors of popular science magazine Quanta named Kyng’s algorithm one of the ten biggest discoveries in computer science in 2022.
The ETH Zurich researchers have since refined their approach and developed further almost-linear-time algorithms. For example, the first algorithm was still focused on fixed, static networks whose connections are directed, meaning they function like one-way streets in urban road networks. The algorithms published this year are now also able to compute optimal flows for networks that incrementally change over time. Lightning-fast computation is an important step in tackling highly complex and data-rich networks that change dynamically and very quickly, such as molecules or the brain in biology, or human friendships.
Lightning-fast algorithms for changing networks
On Thursday, Simon Meierhans — a member of Kyng’s team — presented a new almost-linear-time algorithm at the Annual ACM Symposium on Theory of Computing (STOC) in Vancouver. This algorithm solves the minimum-cost maximum-flow problem for networks that incrementally change as new connections are added. Furthermore, in a second paper accepted by the IEEE Symposium on Foundations of Computer Science (FOCS) in October, the ETH researchers have developed another algorithm that also handles connections being removed.
Specifically, these algorithms identify the shortest routes in networks where connections are added or deleted. In real-world traffic networks, examples of such changes in Switzerland include the complete closure and then partial reopening of the Gotthard Base Tunnel in the months since summer 2023, or the recent landslide that destroyed part of the A13 motorway, which is the main alternative route to the Gotthard Road Tunnel.
Confronted with such changes, how does a computer, an online map service or a route planner calculate the lowest-cost and fastest connection between Milan and Copenhagen? Kyng’s new algorithms also compute the optimal route for these incrementally or decrementally changing networks in almost-linear time — so quickly that the computing time for each new connection, whether added through rerouting or the creation of new routes, is again negligible.

But what exactly is it that makes Kyng’s approach to computations so much faster than any other network flow algorithm? In principle, all computational methods are faced with the challenge of having to analyse the network in multiple iterations in order to find the optimal flow and the minimum-cost route. In doing so, they run through each of the different variants of which connections are open, closed or congested because they have reached their capacity limit.
Compute the whole? Or its parts?
Prior to Kyng, computer scientists tended to choose between two key strategies for solving this problem. One of these was modelled on the railway network and involved computing a whole section of the network with a modified flow of traffic in each iteration. The second strategy — inspired by power flows in the electricity grid — computed the entire network in each iteration but used statistical mean values for the modified flow of each section of the network in order to make the computation faster.
Kyng’s team has now tied together the respective advantages of these two strategies in order to create a radical new combined approach. “Our approach is based on many small, efficient and low-cost computational steps, which — taken together — are much faster than a few large ones,” says Maximilian Probst Gutenberg, a lecturer and member of Kyng’s group, who played a key role in developing the almost-linear-time algorithms.
A brief look at the history of this discipline adds an additional dimension to the significance of Kyng’s breakthrough: flow problems in networks were among the first to be solved systematically with the help of algorithms in the 1950s, and flow algorithms played an important role in establishing theoretical computer science as a field of research in its own right. The well-known algorithm developed by mathematicians Lester R. Ford Jr. and Delbert R. Fulkerson also stems from this period. Their algorithm efficiently solves the maximum-flow problem, which seeks to determine how to transport as many goods through a network as possible without exceeding the capacity of the individual routes.
Fast and wide-ranging
These advances showed researchers that the maximum-flow problem, the minimum-cost problem (transshipment or transportation problem) and many other important network-flow problems can all be viewed as special cases of the general minimum-cost flow problem. Prior to Kyng’s research, most algorithms were only able to solve one of these problems efficiently, though they could not do even this particularly quickly, nor could they be extended to the broader minimum-cost flow problem. The same applies to the pioneering flow algorithms of the 1970s, for which the theoretical computer scientists John Edward Hopcroft, Richard Manning Karp and Robert Endre Tarjan each received a Turing Award, regarded as the “Nobel Prize” of computer science. Karp received his in 1985; Hopcroft and Tarjan won theirs in 1986.
Shift in perspective from railways to electricity
It wasn’t until 2004 that mathematicians and computer scientists Daniel Spielman and Shang-Hua Teng — and later Samuel Daitch — succeeded in writing algorithms that also provided a fast and efficient solution to the minimum-cost flow problem. It was this group that shifted the focus to power flows in the electricity grid. Their switch in perspective from railways to electricity led to a key mathematical distinction: if a train is rerouted on the railway network because a line is out of service, the next best route according to the timetable may already be occupied by a different train. In the electricity grid, it is possible for the electrons that make up a power flow to be partially diverted to a network connection through which other current is already flowing. Thus, unlike trains, the electrical current can, in mathematical terms, be “partially” moved to a new connection.
This partial rerouting enabled Spielman and his colleagues to compute such route changes much faster and, at the same time, to recalculate the entire network after each change. “We rejected Spielman’s approach of creating the most powerful algorithms we could for the entire network,” says Kyng. “Instead, we applied his idea of partial route computation to the earlier approaches of Hopcroft and Karp.” This computation of partial routes in each iteration played a major role in speeding up the overall flow computation.
A turning point in theoretical principles
Much of the ETH Zurich researchers’ progress comes down to the decision to extend their work beyond the development of new algorithms. The team also uses and designs new mathematical tools that speed up their algorithms even more. In particular, they have developed a new data structure for organising network data; this makes it possible to identify any change to a network connection extremely quickly; this, in turn, helps make the algorithmic solution so amazingly fast. With so many applications lined up for the almost-linear-time algorithms and for tools such as the new data structure, the overall innovation spiral could soon be turning much faster than before.
Yet laying the foundations for solving very large problems that couldn’t previously be computed efficiently is only one benefit of these significantly faster flow algorithms — because they also change the way in which computers calculate complex tasks in the first place. “Over the past decade, there has been a revolution in the theoretical foundations for obtaining provably fast algorithms for foundational problems in theoretical computer science,” writes an international group of researchers from University of California, Berkeley, which includes among its members Rasmus Kyng and Deeksha Adil, a researcher at the Institute for Theoretical Studies at ETH Zurich. More