AI’s Next Leap: Agentic Intelligence
The evolution from simple LLM-powered assistants to systems with growing agentic capabilities marks a significant step towards more versatile and impactful AI.
Theory
Advertisement
GenDP: A Framework of Dynamic Programming Acceleration for Genome Sequencing Analysis
The proposed GenDP framework of dynamic programming acceleration for genome sequencing analysis supports multiple DP kernels.
Technical Perspective: Toward a Generalized Accelerator for Genome Sequence Analysis
GenDP offers an important step toward addressing the need for a universal accelerator.
Researchers have invested immeasurable time and effort into programs that run and never halt.
Finding Beauty and Meaning in Computational Complexity
Irit Dinur’s appointment as the first woman professor at the Institute for Advanced Study's School of Mathematics is at once historic and unremarkable.
New Spectral Algorithms for Refuting Smoothed k-SAT
Our methods yield new algorithms for smoothed k-SAT instances with guarantees that match those for the significantly simpler and well-studied model of random formulas.
Technical Perspective: The Surprising Power of Spectral Refutation
Could an algorithm that seems unrelated to SAT serve as a reliable refutation heuristic? Perhaps surprisingly, the answer is yes.
Negative-Weight Single-Source Shortest Paths in Near-Linear Time
The first combinatorial algorithm for negative-weight SSSP to break through the classic ˜O(m√n log W) bound.
Is It Math or CS? Or Is It Both?
Igor Markov's “Reevaluating Google’s Reinforcement Learning for IC Macro Placement” in the November 2024 Communications looks at two non-peer-reviewed papers and makes baseless allegations of scientific integrity issues, all already found to be without merit.
Integration of Music and Art in a Science and Engineering-Based University
How do technology researchers involved in music and art view its relationship with their science and engineering research?
Recent work has combined pseudorandom starting structures and random techniques that use the framework of finite geometry.
What Is Theoretical Computer Science?
As computer scientists, we should look for inspiration from physics rather than from mathematics.
What should you bet to maximize your probability of doubling your money in a scenario where you are willing to lose all your money?
A paper by Victor Reis and Thomas Rothvoss proved a new upper bound on the time required to solve for any integer program.
The most popular explainable AI (XAI) approaches offer no guarantees of rigor.
Solving Sparse Linear Systems Faster than Matrix Multiplication
In this paper, we present an algorithm that solves linear systems with sparse coefficient matrices asymptotically faster than matrix multiplication for any ω > 2.
Technical Perspective: Solve for x
Peng and Vempala have pushed through a barrier that has stood for decades. How far will their momentum carry us?
Maybe the formalization of the tech imperative fails because it's not really about the implications of propositional logic.
Wigderson Named Turing Awardee for Decisive Work on Randomness
His groundbreaking contributions to theoretical computer science demonstrate the power and limitations of randomness in computation.
Biocomputation: Moving Beyond Turing with Living Cellular Computers
The information processing link between computer science and molecular biology.
Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph Problems
The challenge of transforming polynomialtime algorithms to really efficient ones.
Indistinguishability Obfuscation from Well-Founded Assumptions
We examine a formalization of the “one-way compiler" concept with the notion of indistinguishability obfuscation.
Technical Perspective: Hiding Secrets in Programs
"Indistinguishability Obfuscation from Well-Founded Assumptions," by Aayush Jain et al., gives a new construction of indistinguishability obfuscation that is provably secure.
Shape the Future of Computing
ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.
Get InvolvedCommunications of the ACM (CACM) is now a fully Open Access publication.
By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.
Learn More