Tag Archives: Math

Surprising Limits Discovered in Quest for Optimal Solutions

Feature, , ,

Quanta Magazine

Algorithms that zero in on solutions to optimization problems are the beating heart of machine reasoning. New results reveal surprising limits.

Our lives are a succession of optimization problems. They occur when we search for the fastest route home from work or attempt to balance cost and quality on a trip to the store, or even when we decide how to spend limited free time before bed.

These scenarios and many others can be represented as a mathematical optimization problem. Making the best decisions is a matter of finding their optimal solutions. And for a world steeped in optimization, two recent results provide both good and bad news.

In a paper posted in August 2020, Amir Ali Ahmadi of Princeton University and his former student, Jeffrey Zhang, who is now at Carnegie Mellon University, established that for some quadratic optimization problems — in which pairs of variables can interact — it’s computationally infeasible to find even locally optimal solutions in a time-efficient manner.

But then, two days later, Zhang and Ahmadi released a second paper with a positive takeaway. They proved that it’s always possible to quickly identify whether a cubic polynomial — which can feature three-way interactions between variables — has a local minimum, and to find it if it does.

The limits are not what their discoverers expected.

Read the full story in Quanta Magazine

Watch a Drone Swarm Fly Through a Fake Forest Without Crashing

News, , ,

WIRED

Each copter doesn’t just track where the others are. It constantly predicts where they’ll go.

ENRICA SORIA NEEDED soft trees. The mathematical engineer and robotics PhD student from the Swiss Federal Institute of Technology Lausanne, or EPFL, had already built a computer model to simulate the trajectories of five autonomous quadcopters flying through a dense forest without hitting anything. But an errant copter wouldn’t survive a tête-à-tête with a physical tree.

So Soria built a fake forest the size of a bedroom. Motion-capture cameras lined a rail hanging above the space to track the movement of the quadcopters. And for “trees,” Soria settled on a grid of eight green collapsible kids’ play tunnels from Ikea, made of a soft fabric. “Even if the drones crash into them,” Soria recalls thinking, “they won’t break.”

Read the full story in WIRED

This Human-Sized Origami Reimagines Emergency Shelters

News, , ,

WIRED

When flat, the structure is about the size of a twin mattress. But when it’s inflated, walls widen, and a roof snaps into place.

ONE BRIGHT APRIL day on a Harvard University lawn, David Melancon stepped out of a white plastic tent carrying a table. Then another. Then he made a few trips to produce 14 chairs. Then a bike, followed by a yellow bike pump. Finally, he carried out a large orange Shop-Vac. Melancon, a PhD candidate in applied mathematics, then closed the tent’s makeshift door behind him. This was what his team dubbed their “clown car” demonstration—proof that a huge number of objects could fit inside a tent which, only a few moments before, had been a flat stack of plastic about the size of a twin mattress, then inflated into an origami-inspired shelter.

Read the full story in WIRED

The Coach Who Led the U.S. Math Team Back to the Top

Profile, Q&A, , ,

QUANTA MAGAZINE

Po-Shen Loh has harnessed his competitive impulses and iconoclastic tendencies to reinvigorate the U.S. Math Olympiad program.

Po-Shen Loh has resurrected the United States International Mathematical Olympiad team, leading it to four first-place rankings in the last six years as the team’s head coach.

But in 2002, when a friend suggested Loh apply for an open position as a grader with the team, he hesitated. “I had never thought to apply before,” Loh said. “Not because I didn’t want to. But because I thought there are better people out there.”

He eventually agreed, and by the end of the team’s June 2002 training program, he’d made an impression. “Somehow I got voted best lecturer,” he said. In 2013 the Mathematical Association of America, which coordinates the team, asked Loh to become the head coach. He accepted, and two years later the U.S. achieved a top ranking in the IMO for the first time in 21 years.

Read the full story in Quanta Magazine

New Quantum Algorithms Finally Crack Nonlinear Equations

News, ,

QUANTA MAGAZINE

Two teams found different ways for quantum computers to process nonlinear systems by first disguising them as linear ones.

Sometimes, it’s easy for a computer to predict the future. Simple phenomena, such as how sap flows down a tree trunk, are straightforward and can be captured in a few lines of code using what mathematicians call linear differential equations. But in nonlinear systems, interactions can affect themselves: When air streams past a jet’s wings, the air flow alters molecular interactions, which alter the air flow, and so on. This feedback loop breeds chaos, where small changes in initial conditions lead to wildly different behavior later, making predictions nearly impossible — no matter how powerful the computer.

“This is part of why it’s difficult to predict the weather or understand complicated fluid flow,” said Andrew Childs, a quantum information researcher at the University of Maryland. “There are hard computational problems that you could solve, if you could [figure out] these nonlinear dynamics.”

That may soon be possible. In separate studies posted in November, two teams — one led by Childs, the other based at the Massachusetts Institute of Technology — described powerful tools that would allow quantum computers to better model nonlinear dynamics.

Read the full story in Quanta Magazine