Publications (43)
Enumeration of Preferred Extensions in Almost Oriented Digraphs
Serge Gaspers, Ray Li
In this paper, we present enumeration algorithms to list all preferred extensions of an argumentation framework. This task is equivalent to enumerating all maximal semikernels of a…
Locality vs Quantum Codes
Samuel Dai, Ray Li
This paper proves optimal tradeoffs between the locality and parameters of quantum error-correcting codes. Quantum codes give a promising avenue towards quantum fault tolerance, bu…
Max-Cut in Degenerate -Free Graphs
Ray Li, Nitya Mani
We obtain several lower bounds on the of -degenerate -free graphs. Let denote the smallest of an -free -degenerate grap…
Expected Length of the Longest Common Subsequence of Multiple Strings
Ray Li, William Ren, Yiran Wen
We study the generalized Chvátal-Sankoff constant , which represents the normalized expected length of the longest common subsequence (LCS) of independent uniformly…
Optimal Locality and Parameter Tradeoffs for Subsystem Codes
Samuel Dai, Ray Li, Eugene Tang
We study the tradeoffs between the locality and parameters of subsystem codes. We prove lower bounds on both the number and lengths of interactions in any -dimensional embedding…
Wedge-Lifted Codes
Jabari Hastings, Amy Kanne, Ray Li +1
We define wedge-lifted codes, a variant of lifted codes, and we study their locality properties. We show that (taking the trace of) wedge-lifted codes yields binary codes with the…
Pharmacokinetic Measurements in Dose Finding Model Guided by Escalation with Overdose Control
Arnab Kumar Maity, Satrajit Roy Chowdhury, Ray Li +2
Oncology drug development starts with a dose escalation phase to find the maximal tolerable dose (MTD). Dose limiting toxicity (DLT) is the primary endpoint for dose escalation pha…
Approximating binary longest common subsequence in almost-linear time
Xiaoyu He, Ray Li
The Longest Common Subsequence (LCS) is a fundamental string similarity measure, and computing the LCS of two strings is a classic algorithms question. A textbook dynamic programmi…
The zero-rate threshold for adversarial bit-deletions is less than 1/2
Venkatesan Guruswami, Xiaoyu He, Ray Li
We prove that there exists an absolute constant such any binary code tolerating adversarial deletions must satisfy $|C|\le 2^{\text{poly}\log…
Improved rate-distance trade-offs for quantum codes with restricted connectivity
Nouédyn Baspin, Venkatesan Guruswami, Anirudh Krishna +1
For quantum error-correcting codes to be realizable, it is important that the qubits subject to the code constraints exhibit some form of limited connectivity. The works of Bravyi…
CopyCat2: A Single Model for Multi-Speaker TTS and Many-to-Many Fine-Grained Prosody Transfer
Sri Karlapati, Penny Karanasou, Mateusz Lajszczak +7
In this paper, we present CopyCat2 (CC2), a novel model capable of: a) synthesizing speech with different speaker identities, b) generating speech with expressive and contextually…
An Elementary Proof of the Cayley Formula Using Random Maps
Steven Hao, Andrew He, Ray Li +1
Cayley's formula states that the number of labelled trees on vertices is , and many of the current proofs involve complex structures or rigorous computation. We presen…
Improved list-decodability of random linear binary codes
Ray Li, Mary Wootters
There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate $1…
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets
Omar Alrabiah, Venkatesan Guruswami, Ray Li
A simple, recently observed generalization of the classical Singleton bound to list-decoding asserts that rate codes are not list-decodable using list-size beyond an error…
Efficient Near-Optimal Codes for General Repeat Channels
Francisco Pernice, Ray Li, Mary Wootters
Given a probability distribution over the non-negative integers, a -repeat channel acts on an input symbol by repeating it a number of times distributed…
Improved batch code lower bounds
Ray Li, Mary Wootters
Batch codes are a useful notion of locality for error correcting codes, originally introduced in the context of distributed storage and cryptography. Many constructions of batch co…
Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
Ray Li, Steven J. Miller
Zeckendorf proved that every integer can be written uniquely as a sum of non-adjacent Fibonacci numbers . This has been extended to many other recurrence relatio…
Near-Optimal List-Recovery of Linear Code Families
Ray Li, Nikhil Shagrithaya
We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independe…
Hat Guessing Numbers of Degenerate Graphs
Xiaoyu He, Ray Li
Recently, Farnik asked whether the hat guessing number of a graph could be bounded as a function of its degeneracy , and Bosek, Dudek, Farnik, Grytczuk and Ma…
Coding against deletions in oblivious and online models
Venkatesan Guruswami, Ray Li
We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining , the zero-rate threshold of adversaria…
On edge-ordered Ramsey numbers
Jacob Fox, Ray Li
An edge-ordered graph is a graph with a linear ordering of its edges. Two edge-ordered graphs are equivalent if their is an isomorphism between them preserving the ordering of the…
Check-weight-constrained quantum codes: Bounds and examples
Lily Wang, Andy Zeyi Liu, Ray Li +2
Quantum low-density parity-check (qLDPC) codes can be implemented by measuring only low-weight checks, making them compatible with noisy quantum hardware and central to the quest t…
Lifted multiplicity codes and the disjoint repair group property
Ray Li, Mary Wootters
Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction…
Lower bounds for Max-Cut in -free graphs via semidefinite programming
Charles Carlson, Alexandra Kolla, Ray Li +3
For a graph , let denote the size of the maximum cut in . The problem of estimating as a function of the number of vertices and edges of has a long history…
A Simple Proof of the Cayley Formula using Random Graphs
Scott Wu, Ray Li, Andrew He +1
We present a nice result on the probability of a cycle occurring in a randomly generated graph. We then provide some extensions and applications, including the proof of the famous…
Bounds for list-decoding and list-recovery of random linear codes
Venkatesan Guruswami, Ray Li, Jonathan Mosheiff +3
A family of error-correcting codes is list-decodable from error fraction if, for every code in the family, the number of codewords in any Hamming ball of fractional radius …
Non-admissibility of some universal supersingular representations
Zachary Feng, Heejong Lee, Ray Li +2
Let be an unramified extension of degree with residue field . Let be an irreducible representation of over …
Oblivious Deletion Codes
Roni Con, Ray Li
We construct deletion error-correcting codes in the oblivious model, where errors are adversarial but oblivious to the encoder's randomness. Oblivious errors bridge the gap between…
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
Ray Li
We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any , assuming the Strong Exponenti…
A Debate-Driven Experiment on LLM Hallucinations and Accuracy
Ray Li, Tanishka Bagade, Kevin Martinez +4
Large language models (LLMs) have achieved a degree of success in generating coherent and contextually relevant text, yet they remain prone to a significant challenge known as hall…
Improved List-Decodability of Reed--Solomon Codes via Tree Packings
Zeyu Guo, Ray Li, Chong Shangguan +2
This paper shows that there exist Reed--Solomon (RS) codes, over \black{exponentially} large finite fields \black{in the code length}, that are combinatorially list-decodable well…
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Ray Li, Percy Liang, Stephen Mussmann
Decision Tree is a classic formulation of active learning: given hypotheses with nonnegative weights summing to 1 and a set of tests that each partition the hypotheses, output…
Hardness of Approximate Diameter: Now for Undirected Graphs
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time…
Polynomial time decodable codes for the binary deletion channel
Venkatesan Guruswami, Ray Li
In the random deletion channel, each bit is deleted independently with probability . For the random deletion channel, the existence of codes of rate , and thus bounded…
Effective bounds on multiplicatively dependent orbits of integer polynomials modulo S-integers
Ray Li, Igor E. Shparlinski
We obtain effective bounds on the heights of algebraic integers whose orbits contain multiplicatively dependent values modulo S-integers. Our method is based on a new upper bound o…
Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes
Venkatesan Guruswami, Ray Li
This work constructs codes that are efficiently decodable from a constant fraction of \emph{worst-case} insertion and deletion errors in three parameter settings: (i) Binary codes…
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
On the Scaling of PEFT: Towards Million Personal Models of Trillion Parameters
Mind Lab, :, Vin Bo +64
Parameter-efficient fine-tuning (PEFT) is usually treated as a cheaper alternative to full fine-tuning. We study a broader role: small trainable adapters as persistent local state…
Coded trace reconstruction in a constant number of traces
Joshua Brakensiek, Ray Li, Bruce Spang
The coded trace reconstruction problem asks to construct a code such that any is recoverable from independent outputs ("traces") of from a binary…
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets
Roni Con, Zeyu Guo, Ray Li +1
In this paper, we prove that with high probability, random Reed-Solomon codes approach the half-Singleton bound - the optimal rate versus error tradeoff for linear insdel codes - w…
Random Reed-Solomon Codes Achieve List-Decoding Capacity With Linear-Sized Alphabets
Omar Alrabiah, Zeyu Guo, Venkatesan Guruswami +2
Reed-Solomon codes are a classic family of error-correcting codes consisting of evaluations of low-degree polynomials over a finite field on some sequence of distinct field element…
On Ramsey numbers of hedgehogs
Jacob Fox, Ray Li
The hedgehog is a 3-uniform hypergraph on vertices such that, for any pair with , there exists a unique vertex such that…
MinT: Managed Infrastructure for Training and Serving Millions of LLMs
Mind Lab, :, Song Cao +60
We present MindLab Toolkit (MinT), a managed infrastructure system for Low-Rank Adaptation (LoRA) post-training and online serving. MinT targets a setting where many trained polici…