• Home
  • Insight
  • Blog
  • Business
  • Entertainment
  • Health
  • Politics
  • Shop
    • Gift Shop
    • Value Shop
    • Store
    • Bargain Shop
    • Discount
  • Sports
  • Tech
  • Travel
  • USA
  • Video
  • World
    • Asia
    • Africa
    • South America
    • North America
    • Europe
    • Oceania
Wednesday, November 18, 2026
No Result
View All Result
Subscribe Now
  • Home
  • Insight
  • Blog
  • Business
  • Entertainment
  • Health
  • Politics
  • Shop
    • Gift Shop
    • Value Shop
    • Store
    • Bargain Shop
    • Discount
  • Sports
  • Tech
  • Travel
  • USA
    Mary Peltola Emerges Victorious in Alaska Senate Race, Making History for Democrats

    Mary Peltola Emerges Victorious in Alaska Senate Race, Making History for Democrats

    Stranded in Conflict: Palestinians Navigate the Tenuous Balance of War and Peace Amid Ceasefire Efforts

    Stranded in Conflict: Palestinians Navigate the Tenuous Balance of War and Peace Amid Ceasefire Efforts

    Trump Administration Revokes Pay Increase for Head Start Educators

    Trump Administration Revokes Pay Increase for Head Start Educators

    Unexpected Triumph: Gay Candidates Achieve Unforeseen Victories in Challenging Races

    Unexpected Triumph: Gay Candidates Achieve Unforeseen Victories in Challenging Races

    Microsoft Outlook Experiences Prolonged Outage Affecting Users Nationwide

    Microsoft Outlook Experiences Prolonged Outage Affecting Users Nationwide

    Gunfire Erupts in D.C.: Authorities Search for Suspect Amid Rising Concerns Over Public Safety

    Gunfire Erupts in D.C.: Authorities Search for Suspect Amid Rising Concerns Over Public Safety

    LAUSD Takes Strong Action Against Hate Speech Following Racial Slur Incidents

    LAUSD Takes Strong Action Against Hate Speech Following Racial Slur Incidents

    Beloved Former Los Angeles Times Columnist Steve Harvey Passes Away at 80

    Beloved Former Los Angeles Times Columnist Steve Harvey Passes Away at 80

    Exploring Diversity: ‘Ten Lives’ Showcases the Varied Economic Journeys of Americans

    Exploring Diversity: ‘Ten Lives’ Showcases the Varied Economic Journeys of Americans

  • Video
  • World
    • Asia
    • Africa
    • South America
    • North America
    • Europe
    • Oceania
The Insight Post
  • Home
  • Insight
  • Blog
  • Business
  • Entertainment
  • Health
  • Politics
  • Shop
    • Gift Shop
    • Value Shop
    • Store
    • Bargain Shop
    • Discount
  • Sports
  • Tech
  • Travel
  • USA
    Mary Peltola Emerges Victorious in Alaska Senate Race, Making History for Democrats

    Mary Peltola Emerges Victorious in Alaska Senate Race, Making History for Democrats

    Stranded in Conflict: Palestinians Navigate the Tenuous Balance of War and Peace Amid Ceasefire Efforts

    Stranded in Conflict: Palestinians Navigate the Tenuous Balance of War and Peace Amid Ceasefire Efforts

    Trump Administration Revokes Pay Increase for Head Start Educators

    Trump Administration Revokes Pay Increase for Head Start Educators

    Unexpected Triumph: Gay Candidates Achieve Unforeseen Victories in Challenging Races

    Unexpected Triumph: Gay Candidates Achieve Unforeseen Victories in Challenging Races

    Microsoft Outlook Experiences Prolonged Outage Affecting Users Nationwide

    Microsoft Outlook Experiences Prolonged Outage Affecting Users Nationwide

    Gunfire Erupts in D.C.: Authorities Search for Suspect Amid Rising Concerns Over Public Safety

    Gunfire Erupts in D.C.: Authorities Search for Suspect Amid Rising Concerns Over Public Safety

    LAUSD Takes Strong Action Against Hate Speech Following Racial Slur Incidents

    LAUSD Takes Strong Action Against Hate Speech Following Racial Slur Incidents

    Beloved Former Los Angeles Times Columnist Steve Harvey Passes Away at 80

    Beloved Former Los Angeles Times Columnist Steve Harvey Passes Away at 80

    Exploring Diversity: ‘Ten Lives’ Showcases the Varied Economic Journeys of Americans

    Exploring Diversity: ‘Ten Lives’ Showcases the Varied Economic Journeys of Americans

  • Video
  • World
    • Asia
    • Africa
    • South America
    • North America
    • Europe
    • Oceania
No Result
View All Result
No Result
View All Result
Home Science

Undergraduate Upends a 40-Year-Old Data Science Conjecture

by Theinsightpost
March 16, 2025
in Science
0 0
0
Undergraduate Upends a 40-Year-Old Data Science Conjecture

In a 1985 paper, the computer scientist Andrew Yao, who would go on to win the A.M. Turing Award, asserted that among hash tables with a specific set of properties, the best way to find an individual element or an empty spot is to just go through potential spots randomly—an approach known as uniform probing. He also stated that, in the worst-case scenario, where you’re searching for the last remaining open spot, you can never do better than x. For 40 years, most computer scientists assumed that Yao’s conjecture was true.

Krapivin was not held back by the conventional wisdom for the simple reason that he was unaware of it. “I did this without knowing about Yao’s conjecture,” he said. His explorations with tiny pointers led to a new kind of hash table—one that did not rely on uniform probing. And for this new hash table, the time required for worst-case queries and insertions is proportional to (log x)2—far faster than x. This result directly contradicted Yao’s conjecture. Farach-Colton and Kuszmaul helped Krapivin show that (log x)2 is the optimal, unbeatable bound for the popular class of hash tables Yao had written about.

“This result is beautiful in that it addresses and solves such a classic problem,” said Guy Blelloch of Carnegie Mellon.

“It’s not just that they disproved [Yao’s conjecture], they also found the best possible answer to his question,” said Sepehr Assadi of the University of Waterloo. “We could have gone another 40 years before we knew the right answer.”

Krapivin on the King’s College Bridge at the University of Cambridge. His new hash table can find and store data faster than researchers ever thought possible.

Photoraph: Phillip Ammon for Quanta Magazine

In addition to refuting Yao’s conjecture, the new paper also contains what many consider an even more astonishing result. It pertains to a related, though slightly different, situation: In 1985, Yao looked not only at the worst-case times for queries, but also at the average time taken across all possible queries. He proved that hash tables with certain properties—including those that are labeled “greedy,” which means that new elements must be placed in the first available spot—could never achieve an average time better than log x.

Farach-Colton, Krapivin, and Kuszmaul wanted to see if that same limit also applied to non-greedy hash tables. They showed that it did not by providing a counterexample, a non-greedy hash table with an average query time that’s much, much better than log x. In fact, it doesn’t depend on x at all. “You get a number,” Farach-Colton said, “something that is just a constant and doesn’t depend on how full the hash table is.” The fact that you can achieve a constant average query time, regardless of the hash table’s fullness, was wholly unexpected—even to the authors themselves.

The team’s results may not lead to any immediate applications, but that’s not all that matters, Conway said. “It’s important to understand these kinds of data structures better. You don’t know when a result like this will unlock something that lets you do better in practice.”


Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

ShareTweetSend
Previous Post

Houthi rebels vow ‘escalation’ following deadly U.S. airstrikes in Yemen

Next Post

NYU and Israeli hospital team up to treat wounded IDF soldiers

Related News

Groundbreaking Electric Comb Promises Hair Regrowth in Mice Within Four Weeks, Paving the Way for Future Hair-Loss Solutions
Science

Groundbreaking Electric Comb Promises Hair Regrowth in Mice Within Four Weeks, Paving the Way for Future Hair-Loss Solutions

November 18, 2026
Miniature LSD Doses Administered in Rapid Succession Show Antidepressant Potential in Mice: Exploring the Impact of Timing vs. Tolerance
Science

Miniature LSD Doses Administered in Rapid Succession Show Antidepressant Potential in Mice: Exploring the Impact of Timing vs. Tolerance

November 14, 2026
Investigation Underway: Experts Seek Answers Behind Sudden Brooklyn Building Collapse
Science

Investigation Underway: Experts Seek Answers Behind Sudden Brooklyn Building Collapse

November 12, 2026
Preserve the Unseen: The Essential Role of Parasites in Ecosystems
Science

Preserve the Unseen: The Essential Role of Parasites in Ecosystems

November 11, 2026
Next Post
NYU and Israeli hospital team up to treat wounded IDF soldiers

NYU and Israeli hospital team up to treat wounded IDF soldiers

Discussion about this post

Subscribe To Our Newsletters

    Customer Support


    1251 Wilcrest Drive
    Houston, Texas
    77042 USA
    Call-832.795.1420
    e-mail – news@theinsightpost.com

    Subscribe To Our Newsletters

      Categories

      • Africa
      • Africa-East
      • African Sports
      • American Sports
      • Arts
      • Asia
      • Australia
      • Business
      • Business Asia
      • Business- Africa
      • Canada
      • Defense
      • Education
      • Egypt
      • Energy
      • Entertainment
      • Europe
      • European Soccer
      • Finance
      • Germany
      • Ghana
      • Health
      • Insight
      • International
      • Investing
      • Japan
      • Latest Headlines
      • Life & Living
      • Markets
      • Mobile
      • Movies
      • New Zealand
      • Nigeria
      • Politics
      • Scholarships
      • Science
      • South Africa
      • South America
      • Sports
      • Tech
      • Travel
      • Travel-Africa
      • UK
      • USA
      • Weather
      • World
      No Result
      View All Result

      Recent News

      Ghana Actors’ Guild Leadership Conflict Escalates to High Court in Tema

      Ghana Actors’ Guild Leadership Conflict Escalates to High Court in Tema

      November 18, 2026
      Fulham Sets £50 Million Price Tag on Calvin Bassey as Manchester United Eyes Transfer

      Fulham Sets £50 Million Price Tag on Calvin Bassey as Manchester United Eyes Transfer

      November 18, 2026
      EU Unveils €45 Billion Loan Proposal for Ukraine Amid High-Stakes Meeting of Trump, Xi, and Putin

      EU Unveils €45 Billion Loan Proposal for Ukraine Amid High-Stakes Meeting of Trump, Xi, and Putin

      November 18, 2026
      Cybercriminals Embrace Innovative AI Tool for Streamlined Hacking Operations

      Cybercriminals Embrace Innovative AI Tool for Streamlined Hacking Operations

      November 18, 2026
      • Home
      • Advertise With Us
      • About Us
      • Corporate
      • Consumer Rewards
      • Forum
      • Privacy Policy
      • Social Trends

      Theinsightpost ©2026 | All Rights Reserved. Theinsightpost is an Elnegy LLC company, registered in Texas, USA

      Welcome Back!

      Login to your account below

      Forgotten Password?

      Retrieve your password

      Please enter your username or email address to reset your password.

      Log In

      Add New Playlist

      We are using cookies to give you the best experience on our website.

      You can find out more about which cookies we are using or switch them off in .

      No Result
      View All Result
      • Home
      • Insight
      • Blog
      • Business
      • Entertainment
      • Health
      • Politics
      • Shop
        • Gift Shop
        • Value Shop
        • Store
        • Bargain Shop
        • Discount
      • Sports
      • Tech
      • Travel
      • USA
      • Video
      • World
        • Asia
        • Africa
        • South America
        • North America
        • Europe
        • Oceania

      Theinsightpost ©2026 | All Rights Reserved. Theinsightpost is an Elnegy LLC company, registered in Texas, USA

      The Insight Post
      Powered by  GDPR Cookie Compliance
      Privacy Overview

      This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.

      Strictly Necessary Cookies

      Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.

      Cookie Policy

      More information about our Cookie Policy