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…
gabe schoenbach
@gabey.zip
541 followers 356 following 63 posts
phd student @UChicagoCS. interested in cryptography, algorithms, combinatorics. gabey.zip
![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.](https://cdn.bsky.app/img/feed_thumbnail/plain/did:plc:fwa55bujvdrwlwlwgqmmxmuf/bafkreigafent46vzvrklvt5ge5lyf3c2a2azz6qmwlqywrp3jzni2i5u3q)
