105 citations · 214 across the 30 of their papers we have counts for
39 papers
Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
In this paper, we continue the study of Maximally Recoverable (MR) Grid Codes initiated by Gopalan et al. [SODA 2017]. More precisely, we study codes over an grid topo…
On the Emergence of Thinking in LLMs I: Searching for the Right Intuition
Guanghao Ye, Khiem Duc Pham, Xinzhi Zhang +5
Recent AI advancements, such as OpenAI's new models, are transforming LLMs into LRMs (Large Reasoning Models) that perform reasoning during inference, taking extra time and compute…
DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory
Jerry Chee, Arturs Backurs, Rainie Heck +4
Quantizing the weights of a neural network has two steps: (1) Finding a good low bit-complexity representation for weights (which we call the quantization grid) and (2) Rounding th…
A Geometric Perspective on the Injective Norm of Sums of Random Tensors
Afonso S. Bandeira, Sivakanth Gopi, Haotian Jiang +2
Matrix concentration inequalities, intimately connected to the Non-Commutative Khintchine inequality, have been an important tool in both applied and pure mathematics. We study ten…
Ranking with Multiple Objectives
Nikhil R. Devanur, Sivakanth Gopi
In search and advertisement ranking, it is often required to simultaneously maximize multiple objectives. For example, the objectives can correspond to multiple intents of a search…
FuxiTranyu: A Multilingual Large Language Model Trained with Balanced Data
Haoran Sun, Renren Jin, Shaoyang Xu +10
Large language models (LLMs) have demonstrated prowess in a wide range of tasks. However, many LLMs exhibit significant performance discrepancies between high- and low-resource lan…
Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes
Joshua Brakensiek, Manik Dhar, Jiyang Gao +2
We establish a connection between problems studied in rigidity theory and matroids arising from linear algebraic constructions like tensor products and symmetric products. A specia…
Differentially Private Synthetic Data via Foundation Model APIs 2: Text
Chulin Xie, Zinan Lin, Arturs Backurs +9
Text data has become extremely valuable due to the emergence of machine learning algorithms that learn from it. A lot of high-quality text data generated in the real world is priva…
AG Codes Achieve List-decoding Capacity over Constant-sized Fields
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi +1
The recently-emerging field of higher order MDS codes has sought to unify a number of concepts in coding theory. Such areas captured by higher order MDS codes include maximally rec…
Generalized GM-MDS: Polynomial Codes are Higher Order MDS
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
The GM-MDS theorem, conjectured by Dau-Song-Dong-Yuen and proved by Lovett and Yildiz-Hassibi, shows that the generator matrices of Reed-Solomon codes can attain every possible con…
Privacy-Preserving In-Context Learning with Differentially Private Few-Shot Generation
Xinyu Tang, Richard Shin, Huseyin A. Inan +6
We study the problem of in-context learning (ICL) with large language models (LLMs) on private datasets. This scenario poses privacy risks, as LLMs may leak or regurgitate the priv…
Textbooks Are All You Need
Suriya Gunasekar, Yi Zhang, Jyoti Aneja +16
We introduce phi-1, a new large language model for code, with significantly smaller size than competing models: phi-1 is a Transformer-based model with 1.3B parameters, trained for…
Differentially Private Synthetic Data via Foundation Model APIs 1: Images
Zinan Lin, Sivakanth Gopi, Janardhan Kulkarni +2
Generating differentially private (DP) synthetic data that closely resembles the original private data is a scalable way to mitigate privacy concerns in the current data-driven wor…
Selective Pre-training for Private Fine-tuning
Da Yu, Sivakanth Gopi, Janardhan Kulkarni +5
Text prediction models, when used in applications like email clients or word processors, must protect user data privacy and adhere to model size constraints. These constraints are…
Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
The development of efficient sampling algorithms catering to non-Euclidean geometries has been a challenging endeavor, as discretization techniques which succeed in the Euclidean s…
A construction of Maximally Recoverable LRCs for small number of local groups
Manik Dhar, Sivakanth Gopi
Maximally Recoverable Local Reconstruction Codes (LRCs) are codes designed for distributed storage to provide maximum resilience to failures for a given amount of storage redundanc…
Improved Field Size Bounds for Higher Order MDS Codes
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Higher order MDS codes are an interesting generalization of MDS codes recently introduced by Brakensiek, Gopi and Makam (IEEE Trans. Inf. Theory 2022). In later works, they were sh…
Private Convex Optimization in General Norms
Sivakanth Gopi, Yin Tat Lee, Daogao Liu +2
We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm . Our algorithms are based on a regulariz…
Generic Reed-Solomon Codes Achieve List-decoding Capacity
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
In a recent paper, Brakensiek, Gopi and Makam introduced higher order MDS codes as a generalization of MDS codes. An order- MDS code, denoted by , h…
Private Convex Optimization via Exponential Mechanism
Sivakanth Gopi, Yin Tat Lee, Daogao Liu
In this paper, we study private optimization problems for non-smooth convex functions on . We show that modifying the exponential mechanism…
Differentially Private Fine-tuning of Language Models
Da Yu, Saurabh Naik, Arturs Backurs +9
We give simpler, sparser, and faster algorithms for differentially private fine-tuning of large-scale pre-trained language models, which achieve the state-of-the-art privacy versus…
Differentially Private n-gram Extraction
Kunho Kim, Sivakanth Gopi, Janardhan Kulkarni +1
We revisit the problem of -gram extraction in the differential privacy setting. In this problem, given a corpus of private text data, the goal is to release as many -grams as…
Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
An -tensor code consists of matrices whose columns satisfy `' parity checks and rows satisfy `' parity checks (i.e., a tensor code is the tensor produc…
Trellis BMA: Coded Trace Reconstruction on IDS Channels for DNA Storage
Sundara Rajan Srinivasavaradhan, Sivakanth Gopi, Henry D. Pfister +1
Sequencing a DNA strand, as part of the read process in DNA storage, produces multiple noisy copies which can be combined to produce better estimates of the original strand; this i…