* . *
  • About
  • Advertise
  • Privacy & Policy
  • Contact
Tuesday, September 16, 2025
Earth-News
  • Home
  • Business
  • Entertainment
    Here’s how NJ’s once-vibrant nightclub scene was born and why it died – Bergen Record

    The Rise and Fall of New Jersey’s Once-Vibrant Nightclub Scene: What Happened?

    The Emmys are back: Viewership soars to highest numbers in 4 years – yahoo.com

    The Emmys Return with a Bang: Viewership Hits a 4-Year High

    From Spinal Tap II to Ed Sheeran : your complete entertainment guide to the week ahead – The Guardian

    Fall’s Hottest Ski Films Are Going on Tour—Here’s the List – yahoo.com

    Experience the Thrill: Fall’s Hottest Ski Films Hit the Road-Don’t Miss the Tour!

    Ryan Reynolds reveals he called a journalist who said mean things about John Candy – yahoo.com

    Ryan Reynolds Reveals the Moment He Stood Up to a Journalist Who Insulted John Candy

    Entertainment Community Fund Launches Program Supporting Entrepreneurs – Playbill

    Entertainment Community Fund Unveils Exciting New Program to Empower Entrepreneurs

  • 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
    Will New Big Technology Engagements Reshape Innodata’s Growth Path? – Yahoo Finance

    Could New Major Tech Partnerships Propel Innodata to Unprecedented Growth?

    Unlocking AI Success: How People, Process, and Technology Form the Ultimate Triangle

    Billion-dollar coffins? New technology could make oceans transparent and Aukus submarines vulnerable – The Guardian

    Billion-Dollar Coffins? How New Technology Could Make Oceans Transparent and Expose Submarines

    What if artificial intelligence is just a “normal” technology? – The Economist

    What if artificial intelligence is just a “normal” technology? – The Economist

    Lincoln Trail College Receives $100,000 Grant from Marathon Petroleum Corporation for Technology Center – wwbl.com

    Lincoln Trail College Lands $100,000 Grant from Marathon Petroleum to Elevate Technology Center

    Aston Martin to integrate Pirelli’s cyber tyre technology in future models – Just Auto

    Aston Martin to Revolutionize Future Models with Pirelli’s Cutting-Edge Cyber Tyre Technology

    Trending Tags

    • Nintendo Switch
    • CES 2017
    • Playstation 4 Pro
    • Mark Zuckerberg
No Result
View All Result
  • Home
  • Business
  • Entertainment
    Here’s how NJ’s once-vibrant nightclub scene was born and why it died – Bergen Record

    The Rise and Fall of New Jersey’s Once-Vibrant Nightclub Scene: What Happened?

    The Emmys are back: Viewership soars to highest numbers in 4 years – yahoo.com

    The Emmys Return with a Bang: Viewership Hits a 4-Year High

    From Spinal Tap II to Ed Sheeran : your complete entertainment guide to the week ahead – The Guardian

    Fall’s Hottest Ski Films Are Going on Tour—Here’s the List – yahoo.com

    Experience the Thrill: Fall’s Hottest Ski Films Hit the Road-Don’t Miss the Tour!

    Ryan Reynolds reveals he called a journalist who said mean things about John Candy – yahoo.com

    Ryan Reynolds Reveals the Moment He Stood Up to a Journalist Who Insulted John Candy

    Entertainment Community Fund Launches Program Supporting Entrepreneurs – Playbill

    Entertainment Community Fund Unveils Exciting New Program to Empower Entrepreneurs

  • 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
    Will New Big Technology Engagements Reshape Innodata’s Growth Path? – Yahoo Finance

    Could New Major Tech Partnerships Propel Innodata to Unprecedented Growth?

    Unlocking AI Success: How People, Process, and Technology Form the Ultimate Triangle

    Billion-dollar coffins? New technology could make oceans transparent and Aukus submarines vulnerable – The Guardian

    Billion-Dollar Coffins? How New Technology Could Make Oceans Transparent and Expose Submarines

    What if artificial intelligence is just a “normal” technology? – The Economist

    What if artificial intelligence is just a “normal” technology? – The Economist

    Lincoln Trail College Receives $100,000 Grant from Marathon Petroleum Corporation for Technology Center – wwbl.com

    Lincoln Trail College Lands $100,000 Grant from Marathon Petroleum to Elevate Technology Center

    Aston Martin to integrate Pirelli’s cyber tyre technology in future models – Just Auto

    Aston Martin to Revolutionize Future Models with Pirelli’s Cutting-Edge Cyber Tyre Technology

    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

Hidlay takes World title by force, Haines finishes with silver, Carr fifth in men’s freestyle – USA Wrestling

Hidlay takes World title by force, Haines finishes with silver, Carr fifth in men’s freestyle – USA Wrestling

September 16, 2025
Netanyahu warns Israel may need ‘super-Sparta’ economy amid growing global isolation – Ynetnews

Netanyahu Urges Israel to Forge a ‘Super-Sparta’ Economy to Defy Rising Global Isolation

September 16, 2025
Here’s how NJ’s once-vibrant nightclub scene was born and why it died – Bergen Record

The Rise and Fall of New Jersey’s Once-Vibrant Nightclub Scene: What Happened?

September 16, 2025
Advocates Raise Alarm Over Health Care Cuts at Wheeling Town Hall – theintelligencer.net

Community Rallies in Outcry Against Proposed Health Care Cuts at Wheeling Town Hall Meeting

September 16, 2025
115th N.Y. Assembly candidates to be certified this week – Spectrum News

115th N.Y. Assembly Candidates Poised for Official Certification This Week

September 16, 2025
Antibiotic pollution could accelerate amphibian decline by turning a potential solution into a threat – Phys.org

Antibiotic pollution could accelerate amphibian decline by turning a potential solution into a threat – Phys.org

September 16, 2025
Fiji’s Ants Are Struggling. Scientists Say They’re Part of the Broader ‘Insect Apocalypse’ – Smithsonian Magazine

Fiji’s Ants Are Disappearing: A Stark Sign of the Global Insect Crisis

September 16, 2025

California Leads the Way with a Bipartisan, Science-Backed Ban on Ultra-Processed School Meals

September 16, 2025

Marwa Zaied: Leading the Revolution in Cancer Care and Longevity with Lifestyle Medicine

September 16, 2025
Will New Big Technology Engagements Reshape Innodata’s Growth Path? – Yahoo Finance

Could New Major Tech Partnerships Propel Innodata to Unprecedented Growth?

September 16, 2025

Categories

Archives

September 2025
MTWTFSS
1234567
891011121314
15161718192021
22232425262728
2930 
« Aug    
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 (822)
  • Economy (841)
  • Entertainment (21,720)
  • General (17,064)
  • Health (9,886)
  • Lifestyle (856)
  • News (22,149)
  • People (845)
  • Politics (851)
  • Science (16,052)
  • Sports (21,341)
  • Technology (15,823)
  • World (825)

Recent News

Hidlay takes World title by force, Haines finishes with silver, Carr fifth in men’s freestyle – USA Wrestling

Hidlay takes World title by force, Haines finishes with silver, Carr fifth in men’s freestyle – USA Wrestling

September 16, 2025
Netanyahu warns Israel may need ‘super-Sparta’ economy amid growing global isolation – Ynetnews

Netanyahu Urges Israel to Forge a ‘Super-Sparta’ Economy to Defy Rising Global Isolation

September 16, 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