* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Thursday, October 9, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Israel’s Entertainment Industry Is Being Targeted by the Left in Hollywood and the Right at Home – The Wall Street Journal

    Inside the Fierce Clash Shaping Israel’s Entertainment Industry: Hollywood vs. Local Voices

    Offset Is Ready To Finalize Divorce With Cardi B for a Major Reason – Yahoo

    Offset Poised to Finalize Divorce from Cardi B for a Major Reason

    Beyond the Stage: 8 Performing Arts Centers Driving Entertainment and Education – Livability.com

    Beyond the Stage: 8 Performing Arts Centers Transforming Entertainment and Education

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Charlie Hunnam Reflects on Playing a Serial Killer in Monster: The Ed Gein Story – Yahoo

    Charlie Hunnam Reveals the Dark Challenges of Playing a Serial Killer in Monster: The Ed Gein Story

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology

    Wisconsin Dairy Leads the Way with Cutting-Edge Technology Systems

    ENERCON and Biome collaborate for wind turbine noise reduction technology – Yahoo Finance

    ENERCON and Biome Join Forces to Revolutionize Wind Turbine Noise Reduction

    US and investors gambling on unproven nuclear technology, warn experts – Financial Times

    US and investors gambling on unproven nuclear technology, warn experts – Financial Times

    Is Light-Speed Analog Computing the Future of Technology? – BIOENGINEER.ORG

    Could Light-Speed Analog Computing Transform the Future of Technology?

    ARM Institute opens technology project call to speed submarine manufacturing – The Robot Report

    ARM Institute Unveils Cutting-Edge Technology Project to Revolutionize Submarine Manufacturing

    Forget Cowbells. Cows Wear High-Tech Collars Now. – The New York Times

    Ditch the Cowbells: Discover the High-Tech Collars Transforming Cattle Care

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Israel’s Entertainment Industry Is Being Targeted by the Left in Hollywood and the Right at Home – The Wall Street Journal

    Inside the Fierce Clash Shaping Israel’s Entertainment Industry: Hollywood vs. Local Voices

    Offset Is Ready To Finalize Divorce With Cardi B for a Major Reason – Yahoo

    Offset Poised to Finalize Divorce from Cardi B for a Major Reason

    Beyond the Stage: 8 Performing Arts Centers Driving Entertainment and Education – Livability.com

    Beyond the Stage: 8 Performing Arts Centers Transforming Entertainment and Education

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Row K Entertainment Emerges as Major New Hollywood Buyer With Splashy TIFF Shopping Spree – TheWrap

    Charlie Hunnam Reflects on Playing a Serial Killer in Monster: The Ed Gein Story – Yahoo

    Charlie Hunnam Reveals the Dark Challenges of Playing a Serial Killer in Monster: The Ed Gein Story

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

    “Reba” cast, then and now: See the stars 24 years later (and who’s reunited for another show) – Yahoo

  • General
  • Health
  • News

    Cracking the Code: Why China’s Economic Challenges Aren’t Shaking Markets, Unlike America’s” – Bloomberg

    Trump’s Narrow Window to Spread the Truth About Harris

    Trump’s Narrow Window to Spread the Truth About Harris

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    Israel-Gaza war live updates: Hamas leader Ismail Haniyeh assassinated in Iran, group says

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    PAP Boss to Niger Delta Youths, Stay Away from the Protest

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Court Restricts Protests In Lagos To Freedom, Peace Park

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Fans React to Jazz Jennings’ Inspiring Weight Loss Journey

    Trending Tags

    • Trump Inauguration
    • United Stated
    • White House
    • Market Stories
    • Election Results
  • Science
  • Sports
  • Technology

    Wisconsin Dairy Leads the Way with Cutting-Edge Technology Systems

    ENERCON and Biome collaborate for wind turbine noise reduction technology – Yahoo Finance

    ENERCON and Biome Join Forces to Revolutionize Wind Turbine Noise Reduction

    US and investors gambling on unproven nuclear technology, warn experts – Financial Times

    US and investors gambling on unproven nuclear technology, warn experts – Financial Times

    Is Light-Speed Analog Computing the Future of Technology? – BIOENGINEER.ORG

    Could Light-Speed Analog Computing Transform the Future of Technology?

    ARM Institute opens technology project call to speed submarine manufacturing – The Robot Report

    ARM Institute Unveils Cutting-Edge Technology Project to Revolutionize Submarine Manufacturing

    Forget Cowbells. Cows Wear High-Tech Collars Now. – The New York Times

    Ditch the Cowbells: Discover the High-Tech Collars Transforming Cattle Care

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
Earth-News
No Result
View All Result
Home Science

Researchers Refute a Widespread Belief About Online Algorithms

November 20, 2023
in Science
Researchers Refute a Widespread Belief About Online Algorithms
Share on FacebookShare on Twitter

When they study these problems, scientists like to envision them as games against an adversary. The adversary chooses a devilish sequence of requests to make the online algorithm perform as badly as possible compared to its offline counterpart. To rob the adversary of some of its power, researchers use algorithms that include random decisions.

This strategy is quite effective, and researchers have suspected since the early 1990s that you can always find a randomized algorithm that reaches a specific performance goal: a competitive ratio proportional to log k, where k is the number of agents. This is called the randomized k-server conjecture, and researchers have shown that it’s true for some spaces, or specific collections of points (the equivalent of houses that could call for plumbers). But it hasn’t been proved for all cases.

Like most researchers, Rabani and his co-authors — Sébastien Bubeck of Microsoft Research and Christian Coester of the University of Oxford — figured the conjecture was true. “I had no reason to doubt it,” Coester said.

But that started to change as they worked on another online problem. It had connections to the k-server problem, and the known lower limit on the competitive ratio was unexpectedly high. It made them think perhaps a goal as low as log k for the k-server problem was overly optimistic.

Rabani said it was Coester who first suggested that the randomized k-server conjecture might be false. “As soon as he said it, it all made sense.”

To disprove the conjecture, the authors played the adversary, creating a perfect storm that would prevent any online algorithm from reaching a competitive ratio of log k. Their strategy had two parts: They constructed a family of complex, fractal-like spaces and designed a distribution of request sequences that would be difficult for any possible algorithm. On the algorithm’s very first move, the structure of the space meant it had to choose between two identical paths, one of which would eventually require extra travel based on the requests. Then the authors used a method called recursion to build spaces that multiplied these decision points, forcing the algorithm into a morass of bad options and driving up the cost.

The choices reminded Rabani of the Robert Frost poem “The Road Not Taken,” in which a traveler contemplates two potential paths through a yellow wood. “We just apply the poem recursively,” he joked. “And then things go really bad.”

The authors showed that, in the spaces they had constructed, a randomized algorithm can never achieve a competitive ratio better than (log k)2, pushing a universal goal of log k forever out of reach. They had refuted the conjecture.

This work, which won a Best Paper Award at the 2023 Symposium on Theory of Computing, marks a “solidly theoretical” milestone, Gupta said. This kind of result helps indicate what kind of performance we can hope for from our algorithms. In practice, however, algorithm designers often aren’t planning around worst-case scenarios, with an omnipotent adversary and complete ignorance of the future. When algorithms are unleashed on real-world problems, they often exceed theoretical expectations.

The paper, which also proved cutoffs for randomized algorithms used for other problems, could also have implications for future work in the field. The result clearly “highlights the power” of the technique the authors used, Gupta said.

Perhaps those future findings will defy researchers’ expectations as this one did, Rabani said. “This is one of the cases where it feels really good to be wrong.”

Quanta is conducting a series of surveys to better serve our audience. Take our computer science reader survey and you will be entered to win free Quanta merchandise.

>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/researchers-refute-a-widespread-belief-about-online-algorithms-20231120/

Tags: RefuteResearchersscience
Previous Post

NSF Director Panchanathan headlines the Canadian Science Policy Conference in Ottawa, signs international collaboration arrangement

Next Post

X’s CEO tells staff data will show efforts to fight hate, as advertisers flee

Research team explores inclusion at conferences – EurekAlert!

Research team explores inclusion at conferences – EurekAlert!

October 9, 2025
If you feel you don’t really belong, here is some science-based advice – New Scientist

If you feel you don’t really belong, here is some science-based advice – New Scientist

October 9, 2025
Opinion | The most important Nobel prizes – The Washington Post

Opinion | The most important Nobel prizes – The Washington Post

October 9, 2025
Video: Owner Lists Shih Tzu’s ‘Toxic Traits’ & Internet Can’t Relate to It Enough – Yahoo

Watch: Owner Reveals Hilarious ‘Toxic Traits’ of Their Shih Tzu That Have Everyone Talking

October 9, 2025

Wisconsin Dairy Leads the Way with Cutting-Edge Technology Systems

October 9, 2025
What Ibrahima Konate wants from Liverpool contract talks – Yahoo Sports

Ibrahima Konate’s Ambitious Goals in His Liverpool Contract Negotiations

October 9, 2025
IRONMAN World Championship Kona 2025: Date, start time and how to watch live – TRI247

IRONMAN World Championship Kona 2025: Date, start time and how to watch live – TRI247

October 9, 2025
Canada’s economy is in serious trouble. Now Mark Carney is coming to Washington to talk tariffs – CNN

Canada’s economy is in serious trouble. Now Mark Carney is coming to Washington to talk tariffs – CNN

October 9, 2025
Israel’s Entertainment Industry Is Being Targeted by the Left in Hollywood and the Right at Home – The Wall Street Journal

Inside the Fierce Clash Shaping Israel’s Entertainment Industry: Hollywood vs. Local Voices

October 9, 2025
Better Food, Better Health: Redefining Chronic Disease Care Through Nutrition – The American Journal of Managed Care® (AJMC®)

Better Food, Better Health: Redefining Chronic Disease Care Through Nutrition – The American Journal of Managed Care® (AJMC®)

October 9, 2025

Categories

Archives

October 2025
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
2728293031  
« Sep    
Earth-News.info

The Earth News is an independent English-language daily published Website from all around the World News

Browse by Category

  • Business (20,132)
  • Ecology (859)
  • Economy (879)
  • Entertainment (21,752)
  • General (17,496)
  • Health (9,921)
  • Lifestyle (892)
  • News (22,149)
  • People (881)
  • Politics (890)
  • Science (16,090)
  • Sports (21,380)
  • Technology (15,860)
  • World (862)

Recent News

Research team explores inclusion at conferences – EurekAlert!

Research team explores inclusion at conferences – EurekAlert!

October 9, 2025
If you feel you don’t really belong, here is some science-based advice – New Scientist

If you feel you don’t really belong, here is some science-based advice – New Scientist

October 9, 2025
  • About
  • Advertise
  • Privacy & Policy
  • Contact

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

No Result
View All Result

© 2023 earth-news.info

Go to mobile version