11 citations · 30 across the 12 of their papers we have counts for
13 papers
Unforgeable Watermarks for Language Models via Robust Signatures
Huijia Lin, Kameron Shahabi, Min Jae Song
Language models now routinely produce text that is difficult to distinguish from human writing, raising the need for robust tools to verify content provenance. Watermarking has eme…
Ideal Attribution and Faithful Watermarks for Language Models
Min Jae Song, Kameron Shahabi
We introduce ideal attribution mechanisms, a formal abstraction for reasoning about attribution decisions over strings. At the core of this abstraction lies the ledger, an append-o…
Cryptographic Hardness of Score Estimation
Min Jae Song
We show that -accurate score estimation, in the absence of strong assumptions on the data distribution, is computationally hard even when sample complexity is polynomial in th…
Topic Segmentation Model Focusing on Local Context
Jeonghwan Lee, Jiyeong Han, Sunghoon Baek +1
Topic segmentation is important in understanding scientific documents since it can not only provide better readability but also facilitate downstream tasks such as information retr…
Learning Single-Index Models with Shallow Neural Networks
Alberto Bietti, Joan Bruna, Clayton Sanford +1
Single-index models are a class of functions given by an unknown univariate ``link'' function applied to an unknown one-dimensional projection of the input. These models are partic…
Lattice-Based Methods Surpass Sum-of-Squares in Clustering
Ilias Zadik, Min Jae Song, Alexander S. Wein +1
Clustering is a fundamental primitive in unsupervised learning which gives rise to a rich class of computationally-challenging inference tasks. In this work, we focus on the canoni…
On the Cryptographic Hardness of Learning Single Periodic Neurons
Min Jae Song, Ilias Zadik, Joan Bruna
We show a simple reduction which demonstrates the cryptographic hardness of learning a single periodic neuron over isotropic Gaussian distributions in the presence of noise. More p…
Self-Supervised Motion Retargeting with Safety Guarantee
Sungjoon Choi, Min Jae Song, Hyemin Ahn +1
In this paper, we present self-supervised shared latent embedding (S3LE), a data-driven motion retargeting method that enables the generation of natural motions in humanoid robots…
Hardness of Approximate Nearest Neighbor Search under L-infinity
Young Kun Ko, Min Jae Song
We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the norm with two simple reductions. Our first reduction shows that hardness of a spec…
Evaluating representations by the complexity of learning low-loss predictors
William F. Whitney, Min Jae Song, David Brandfonbrener +2
We consider the problem of evaluating representations of data for use in solving a downstream task. We propose to measure the quality of a representation by the complexity of learn…
Rapid Structural Pruning of Neural Networks with Set-based Task-Adaptive Meta-Pruning
Minyoung Song, Jaehong Yoon, Eunho Yang +1
As deep neural networks are growing in size and being increasingly deployed to more resource-limited devices, there has been a recent surge of interest in network pruning methods,…
Continuous LWE
Joan Bruna, Oded Regev, Min Jae Song +1
We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CL…
On the Sensitivity of k-Uniform Hypergraph Properties
Stella Biderman, Kevin Cuddy, Ang Li +1
In this paper we present a graph property with sensitivity , where is the number of variables, and generalize it to a -uniform hypergraph property w…