What should you bet to maximize your probability of doubling your money in a scenario where you are willing to lose all your money?
Theory
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?
Wigderson Named Turing Awardee for Decisive Work on Randomness
Biocomputation: Moving Beyond Turing with Living Cellular Computers
Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph Problems
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.
A Unifying Framework for Incompleteness, Inconsistency, and Uncertainty in Databases
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 testing, and reconstruction.
What Should We Do when Our Ideas of Fairness Conflict?
Theoretical Analysis of Edit Distance Algorithms
Cook-Levin: The Ugly Underbelly is Good for Us
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 to fuzzing that is shown to increase the central metric of the number of bugs found.
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