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.
Theory
Advertisement
Biocomputation: Moving Beyond Turing with Living Cellular Computers
The information processing link between computer science and molecular biology.
Exploring the Theory of Computing
2023 ACM A.M. Turing Award laureate Avi Wigderson discusses his work in an interview originally published in January 2020.
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…
A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in Databases
Deploying possible world semantics and the challenge of computing the certain answers to queries.
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
In this paper, we prove the first superpolynomial lower bounds against algebraic circuits of all constant depths over all fields of characteristic 0.
Technical Perspective: How Easy Is It to Describe Hard Polynomials?
"Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits," by Nutan Limaye et al., achieves a landmark in the larger quest of understanding hardness, dentity…
What Should We Do when Our Ideas of Fairness Conflict?
Standards for fair decision making could help us develop algorithms that comport with our consensus views; however, algorithmic fairness has its limits.
Theoretical Analysis of Edit Distance Algorithms
To what extent have the techniques for theoretical analysis of edit distance algorithms achieved their goals?
Emulating the behavior of exotic quantum states may give quantum computing a better way of squeezing out troublesome noise and errors.
Cook-Levin: The Ugly Underbelly is Good for Us
Don't just tell your students that SAT is NP-Complete; show why.
Boosting Fuzzer Efficiency: An Information Theoretic Perspective
In this paper, we take the fundamental perspective of fuzzing as a learning process.
Technical Perspective: What’s All the Fuss about Fuzzing?
"Boosting Fuzzer Efficiency: An Information Theoretic Perspective," by Marcel Böhme, Valentin J.M. Manès, and Sang Kil Cha, presents a novel twist…
The barriers to information generation and sharing have plummeted; information consumers can choose among billions of potential sources. This is information at scale.
Generative AI as a New Innovation Platform
Considering the stability and longevity of a potential new foundational technology.
Generating and Exploiting Automated Reasoning Proof Certificates
Moving toward a full suite of proof-producing automated reasoning tools with SMT solvers that can produce full, independently checkable proofs for real-world problems.
Historic Algorithms Help Unlock Shortest-Path Problem Breakthrough
By revisiting key algorithms from computing, a team unlocked hidden efficiency in a long-standing computer science problem.
The Smallness of Large Language Models
There is so much more to language and human beings than large language models can possibly master.
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