gabe schoenbach

ok yeah this is crazy!! lmao

apple notes using LLMs (i assume) to auto-complete math expressions fundamentally misunderstands the point of the notes app. i’m using this to take notes, not to make calculations.

OTOH i would LOVE it if they added LaTeX support…

Abstract. The study of fine-grained cryptography has proliferated in recent years due to its allure of potentially relying on weaker assumptions compared to standard cryptography. As fine-grained cryptography only requires polynomial gaps between the adversary and honest parties, it seems plausible to build primitives relying upon popular hardness assumptions about problems in P such as k-SUM or Zero-k-Clique. The ultimate hope is that fine-grained cryptography could still be viable even if all current cryptographic assumptions are false, such as if P = NP or if we live in Pessiland where one-way functions do not exist. In our work, we consider whether this approach is viable by studying fine-grained complexity when all standard cryptographic assumptions are false. As our main result, we show that many popular fine-grained complexity problems are easy to solve in the average-case when one-way functions do not exist. In other words, many candidate hardness assumptions for building fine-grained cryptography are no longer options in Pessiland. As an example, we prove that the average-case k-SUM and Zero-k-Clique conjectures are false for sufficiently large constant k when no one-way functions exist. The average-case Zero-k-Clique assumption was used to build fine-grained key-exchange by Lavigne et al. [CRYPTO’19]. We also show that barriers for reductions in fine-grained complexity may be explained by problems in cryptography. First, we show that finding faster algorithms for computing discrete logarithms is equivalent to designing average-case equivalence between k-SUM and k-CYC (an extension of k-SUM to cyclic groups). In particular, finding such a reduction from k-CYC to k-SUM could potentially lead to breakthrough algorithms for the discrete logarithm, factoring, RSA and quadratic residuosity problems. Finally, we show that discrete logarithms with preprocessing may be reduced to the k-CYC-Index problem, and we present faster algorithms for average-case k-SUM-Index and k-CYC-Index.

Image showing part 2 of abstract.

Fine-Grained Complexity in a World without Cryptography (Josh Alman, Yizhi Huang, Kevin Yeo) ia.cr/2025/324

New paper: Simulating Time With Square-Root Space

people.csail.mit.edu/rrw/time-vs-...

It's still hard for me to believe it myself, but I seem to have shown that TIME[t] is contained in SPACE[sqrt{t log t}].

To appear in STOC. Comments are very welcome!

Honest-but-curious Abe

Heterogeneity in Sectoral Production and the Macro Effect of Sectoral Shocks The effect of a negative sectoral shock on GDP depends on how important the shocked sector is as a direct and indirect supplier and how easily sectors can substitute inputs. Past estimates of the para...

First WP is up! Looks at classic micro-to-macro question: What happens to GDP when an individual sector is negatively shocked? Presents novel estimation of sector-yr parameters governing propagation, for 66 ind. from 97-23. Finds sectoral/temporal heterogeneity which changes answer(1/11)
#EconSky

is there something in between a theorem and a lemma

and each of them is right!

panel of three profs giving advice to phd students.

prof A: you should focus solely on a particular subfield; become an expert.

prof B: you’ll never have this much time. take advantage and explore broadly!

prof C: everyone takes their own path; don’t overindex on any one piece of advice :)

it may sound fun but it’s basically never worth it to make prosciutto-wrapped asparagus. even if you fill them with garlicky whipped cream cheese and roast at 350 for a few minutes.

neat, will check this out!

i used to be scared of polynomials but i’m becoming much more comfortable with them lately

not sure about best, but it’s fantastic to see his (always helpful) comments pop up all over mathoverflow

it’s pretty cool to live in the same time that terry tao is doing mathematics

is it possible to put gifs in pdfs?

Abstract. The Fiat-Shamir (FS) transform is a prolific and powerful technique for compiling public-coin interactive protocols into non-interactive ones. Roughly speaking, the idea is to replace the random coins of the verifier with the evaluations of a complex hash function. The FS transform is known to be sound in the random oracle model (i.e., when the hash function is modeled as a totally random function). However, when instantiating the random oracle using a concrete hash function, there are examples of protocols in which the transformation is not sound. So far all of these examples have been contrived protocols that were specifically designed to fail. In this work we show such an attack for a standard and popular interactive succinct argument, based on the GKR protocol, for verifying the correctness of a non-determinstic bounded-depth computation. For every choice of FS hash function, we show that a corresponding instantiation of this protocol, which was been widely studied in the literature and used also in practice, is not (adaptively) sound when compiled with the FS transform. Specifically, we construct an explicit circuit for which we can generate an accepting proof for a false statement. We further extend our attack and show that for every circuit C and desired output y, we can construct a functionally equivalent circuit C^(*), for which we can produce an accepting proof that C^(*) outputs y (regardless of whether or not this statement is true). This demonstrates that any security guarantee (if such exists) would have to depend on the specific implementation of the circuit C, rather than just its functionality. Lastly, we also demonstrate versions of the attack that violate non-adaptive soundness of the protocol – that is, we generate an attacking circuit that is independent of the underlying cryptographic objects. However, these versions are either less practical (as the attacking circuit has very large depth) or make some additional (reasonable) assumptions on the underlying cryptographic primitives.

Image showing part 2 of abstract.

How to Prove False Statements: Practical Attacks on Fiat-Shamir (Dmitry Khovratovich, Ron D. Rothblum, Lev Soukhanov) ia.cr/2025/118

in a crazy twist of fate just had dinner with peter sagal

okay i did meet someone and that someone is the vaunted NPR radio show Wait Wait Don’t Tell Me. premiered jan 3 1998 babyyy

this is such a great article.....

Georg Cantor died 107 years ago, today

but i want the readers to truly believe it is trivial! show don’t tell vibes

when do we think the last basketball scorigami was?

i want to write a math paper that’s sooo clearly explained that every result sounds obvious

i’m obsessed with making conjectures

my new year’s resolution is to love both of my cats equally

last one truly terrifying

A black and white photo of a group of people standing around a table, with a yellow arrow pointing out someone in the background

A group of people dancing at a wedding, with a red circle around one man in the background

People dancing at a wedding, with a bright yellow circle around one man

A group of people playing beer pong and celebrating, with a red circle around one man in the background

Having the time of life editing pics of my friend @jaketg.bsky.social, who radiates an uncanny “photo of a serial killer in the background of an event in a Netflix documentary” vibe.

much like andrew wiles, i have been spending a long time attempting a proof by induction

i think it’s weird that it hasn’t yet happened (in 27 years)

i would like to meet someone born on my exact birthday