Latest news with #ACMSymposiumonTheoryofComputing
Scientific American
2 days ago
- Science
- Scientific American
New Proof Dramatically Compresses Space Needed for Computation
Once upon a time computers filled entire rooms, reading numbers from spinning tapes and churning them through wires to do chains of basic arithmetic. Today they slip into our pockets, performing in a tiny fraction of a second what used to take hours. But even as chips shrink and gain speed, theorists are flipping the question from how much computation space we can pack into a machine to how little is enough to get the job done. This inquiry lies at the heart of computational complexity, a measure of the limits of what problems can be solved and at what cost in time and space. For nearly 50 years theorists believed that if solving a problem takes t steps, it should also need roughly t bits of memory—the 0s and 1s that a machine uses to record information. (Technically, that equation was t/ log(t), but for the numbers involved log(t) is typically negligibly small.) If a task involves 100 steps, for instance, you'd expect to need at least 100 bits, enough to diligently log each step. Using fewer bits was thought to require more steps—like alphabetizing your books by swapping them one by one on the shelf instead of pulling them all out and reshelving them. But in a surprising finding described this week at the ACM Symposium on Theory of Computing in Prague, Massachusetts Institute of Technology computer scientist Ryan Williams found that any problem solvable in time t needs only about √ t bits of memory: a 100-step computation could be compressed and solved with something on the order of 10 bits. 'This result shows the prior intuition is completely false,' Williams says. 'I thought there must be something wrong [with the proof] because this is extremely unexpected.' The breakthrough relies on a 'reduction,' a means of transforming one problem into another that may seem unrelated but is mathematically equivalent. With reductions, packing a suitcase maps onto determining a monthly budget: the size of your suitcase represents your total budget, pieces of clothing correspond to potential expenses, and carefully deciding which clothes can fit is like allocating your budget. Solving one problem would then directly solve the other. This idea is at the core of Williams's result: any problem can be transformed into one you can solve by cleverly reusing space, deftly cramming the necessary information into just a square-root number of bits. Thus, the original problem must be solvable with this compact container. On supporting science journalism If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today. 'This progress is unbelievable,' says Mahdi Cheraghchi, a computer scientist at the University of Michigan. 'Before this result, there were problems you could solve in a certain amount of time, but many thought you couldn't do so with such little space.' Williams's finding, he adds, is 'a step in the right direction that we didn't know how to take.' While computers have continued to shrink, our theoretical understanding of their efficiency has exploded, suggesting that the real constraint is not how much memory we have but how wisely we use it.
News18
19-06-2025
- Science
- News18
Meet Eshan Chattopadhyay, Indian-Origin Cornell Professor, IIT Grad, Awarded Gödel Prize
Last Updated: From IIT-Kanpur to Gödel Prize: Eshan Chattopadhyay's work reshapes randomness and complexity theory. Eshan Chattopadhyay, an Indian-origin computer scientist and associate professor at Cornell University, has won the 2025 Gödel Prize. The Gödel Prize is one of the top honours in theoretical computer science. He shares the award with David Zuckerman of the University of Texas at Austin for a groundbreaking paper that tackles a long-standing challenge in computing: how to generate high-quality randomness from unreliable or weak sources. The research paper, titled 'Explicit Two-Source Extractors and Resilient Functions", was first presented in 2016 at the ACM Symposium on Theory of Computing, where it won the Best Paper award and was later published in the Annals of Mathematics in 2019. Chattopadhyay's work dives into randomness extraction, a crucial area in computer science and cryptography. One may think of it like this: if one had two rigged coins, this method would still find a way to give them fair, unpredictable outcomes. Though it might sound abstract to the uninitiated, its real-world impact is massive. Good randomness is the foundation of everything from secure communications and encryption to complex algorithms and data privacy. Without it, modern digital infrastructure becomes fragile. The paper's ideas have helped reshape how researchers approach pseudo-randomness, complexity theory and secure system design. Chattopadhyay, who did his BTech from IIT-Kanpur in 2011 and PhD from the University of Texas, has also held prestigious research positions at the Institute for Advanced Study in Princeton and the Simons Institute in Berkeley. Reacting to the award, he told Cornell it felt 'surreal and gratifying" to see his work recognised on such a global stage, as reported by LiveMint. The prize is jointly awarded by Special Interest Group on Algorithms and Computation Theory (ACM SIGACT) and the European Association for Theoretical Computer Science. The prize includes a $5,000 award. It recognises papers that have made lasting contributions to the field, both in theory and long-term relevance. Get breaking news, in-depth analysis, and expert perspectives on everything from geopolitics to diplomacy and global trends. Stay informed with the latest world news only on News18. Download the News18 App to stay updated!
Mint
18-06-2025
- Science
- Mint
Who is Eshan Chattopadhyay? All about Indian-origin professor awarded prestigious Godel Prize
Eshan Chattopadhyay, an Indian-origin computer scientist and associate professor at Cornell University, has received the 2025 Gödel Prize—one of the highest recognitions in the field of theoretical computer science. He shares the award with David Zuckerman of the University of Texas at Austin for their influential research on randomness extraction—an area crucial to encryption, cybersecurity, and algorithm design. The award was given for his breakthrough research paper titled 'Explicit Two-Source Extractors and Resilient Functions', which addresses a key challenge in computer science: how to generate high-quality randomness from unreliable sources, critical for secure computing and cryptographic systems. Published initially at the ACM Symposium on Theory of Computing (STOC) in 2016, where it also won the Best Paper award, and later in the Annals of Mathematics in 2019, the paper introduced new techniques that have since shaped major advances in pseudo-randomness and complexity theory. Chattopadhyay completed his BTech in computer science from IIT Kanpur in 2011, followed by a PhD at the University of Texas in 2016. He later held postdoctoral positions at the Institute for Advanced Study in Princeton and the Simons Institute for the Theory of Computing at UC Berkeley, two of the most prominent institutions in the field. Named after legendary logician Kurt Gödel, the Gödel Prize is jointly awarded by the ACM SIGACT and the European Association for Theoretical Computer Science. It honours papers that have made lasting contributions to the field of theoretical computer science. The research deals with randomness extraction- a fundamental concept in computer science and cryptography. It focuses on creating reliable randomness from two flawed or weak random sources, a challenge that has implications for everything from encryption systems to algorithm design. In simple terms, imagine flipping two unfair coins and still being able to extract fair, unpredictable results. That's the essence of what Chattopadhyay and Zuckerman achieved, turning weak inputs into strong, usable randomness. He told Cornell University that the recognition is an incredible honour. He shared that it feels 'surreal and gratifying' that the paper was placed in that category.
