## Some Technical Tidbits

*Tid-bit: delicacy, dainty, snack, nibble, appetizer, hors d’oeuvre, goody, dipper, finger food *

Adam Engst is the publisher of the site TidBITS. This is a site dedicated to technical insights about all aspects of Apple machines: from nano to servers.

Today I want to talk about mathematical tidbits not Apple devices, but look at the above site for information about Apple stuff of all kinds.

Read more…

## Doing Mod N Via Mod R

* Variations on Montgomery’s trick *

Peter Montgomery is a cryptographer at Microsoft. Just recently, Joppe Bos and Arjen Lenstra have edited a book titled *Topics in Computational Number Theory Inspired by Peter L. Montgomery*. The chapters range to Montgomery’s work on elliptic curves, factoring, evaluating polynomials, computing null-spaces of matrices over finite fields, and FFT extensions for algebraic groups. Bos and Lenstra say in their intro that most of this was “inspired by integer factorization, Peter’s main research interest since high school.” Factoring, always factoring…

Today we discuss one of Montgomery’s simpler but most influential ideas going back to a 1985 paper: how to compute mod when you can only do operations mod .

Read more…

## Progress on the Frontier

* An almost exponential improvement in bounds against ACC *

Source from previous paper |

Cody Murray is a PhD student of Ryan Williams at MIT. He and Ryan have a new paper that greatly improves Ryan’s separation of nonuniform circuits from uniform nondeterministic time classes. The previous best separation was from , that is, nondeterministic time . The new one is from , which is nondeterministic time . The ‘Q’ here means “quasi-polynomial,” not “quantum.”

Today we discuss the new ideas that led to this breakthrough on a previous breakthrough.

Read more…

## Timing Leaks Everything

* Facing the awful truth that computers are physical machines *

As moderator of RSA 2016 panel |

Paul Kocher is the lead author on the second of two papers detailing a longstanding class of security vulnerability that was recognized only recently. He is an author on the first paper. Both papers credit his CRYPTO 1996 paper as originating the broad kind of attack that exploits the vulnerability. That paper was titled, “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.” Last week, the world learned that timing attacks can jeopardize entire computing systems, smartphones, the Cloud, everything.

Today we give a high-level view of the Meltdown and Spectre security flaws described in these papers.

Read more…

## Predictions We Didn’t Make

* With wishes for a memorable New Year 2018 *

Muhammad Afzal Upal is Chair of the Computing and Information Science Department at Mercyhurst University. He works in machine learning and cognitive science, most specifically making inferences from textual data. In joint papers he has refined a quantitative approach to the idea of *postdiction* originally suggested by Walter Kintsch in the 1980s.

Today we review some postdictions from 2017 and wish everyone a Happy New Year 2018.

Read more…

## P=NP: Perhaps I Change My Mind

* An old result put a new way (in a now-fixed-up post) *

Albert Meyer knows circuit lower bounds. He co-authored a paper with the late Larry Stockmeyer that proves that small instances of the decision problem of a certain weak second-order logical theory require Boolean circuits with more gates than there are atoms in the observable universe. The instances almost fit into two Tweets using just the Roman typewriter keys.

Today Ken and I discuss a simple but perhaps underlooked connection between P=NP and circuit lower bounds.

Read more…