1 citations · 1 across the 17 of their papers we have counts for
24 papers
The Komlós Problem in Matrix-Multiplication Time
Emile Anand, Peter Chen
We give a randomized algorithm that, for an matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below in expected $\widetilde O(…
Finite-Precision Gram-Schmidt Walks
Emile Anand, Jan van den Brand, Peter Chen
The Gram-Schmidt Walk is a randomized vector-balancing algorithm whose subgaussian guarantees support applications in discrepancy, experimental design, and data compression; howeve…
Hob-VL: A Benchmark for Visually Grounded Boolean Reasoning
Yuzhou Wang, Emile Anand, Ijay Narang
Reliable visual reasoning requires composing multiple visual observations and returning consistent answers to logically equivalent questions. We introduce Hob-VL, a benchmark for v…
Coloring 3-colorable graphs with colors via a Gaussian-cover recursion
Emile Anand
We give a randomized polynomial-time algorithm that colors any promised -colorable graph on vertices with colors, improving on t…
SMat-Attention: Structured Long-Context Sequence Modeling
Emile Anand, Abdullah Ateyeh, Archer Wang +1
Long-context sequence models face a fundamental tradeoff: softmax attention uses flexible token-level interactions at quadratic cost, whereas linear attention obtains linear-time t…
Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings
Emile Anand, Elia Gorokhovsky, Jennifer Hritz +1
Encoding quantum information with low circuit overhead is a fundamental challenge in fault-tolerant quantum computation. Random circuits provide a natural mechanism for rapidly spr…
Role Steering of Language Models for Social Simulations
Isaac Song, Mohammed Rehan Parwani, Glenn Matlin +8
Social simulations built from language-model agents need role-conditioned behavior that can be checked before agents are placed into a simulated population. We introduce an activat…
Continuous Latent Contexts Enable Efficient Online Learning in Transformers
Emile Anand, Abdullah Ateyeh, Xinyuan Cao +1
Large language models (LLMs) exhibit a strong capacity for in-context learning: Given labeled examples, they can generate good predictions without parameter updates. However, many…
Learning Approximate Nash Equilibria in Cooperative Multi-Agent Reinforcement Learning via Mean-Field Subsampling
Emile Anand, Ishani Karmarkar
Many large-scale platforms and networked control systems have a centralized decision maker interacting with a massive population of agents under strict observability constraints. M…
Graphon Mean-Field Subsampling for Cooperative Heterogeneous Multi-Agent Reinforcement Learning
Emile Anand, Richard Hoffmann, Sarah Liaw +1
Coordinating large populations of interacting agents is a central challenge in multi-agent reinforcement learning (MARL), where the size of the joint state-action space scales expo…
Unsupervised Decomposition and Recombination with Discriminator-Driven Diffusion Models
Archer Wang, Emile Anand, Yilun Du +1
Decomposing complex data into factorized representations can reveal reusable components and enable synthesizing new samples via component recombination. We investigate this in the…
Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
Emile Anand
We prove that every graph of rankwidth at least contains an induced subgraph whose minimum balanced cutrank is at least , which implies a vertex subset where every balance…
Global PIQA: Evaluating Commonsense Reasoning Across 100+ Languages and Cultures
Tyler A. Chang, Catherine Arnett, Abdelrahman Sadallah +377
To date, there exist almost no culturally-specific evaluation benchmarks for large language models (LLMs) that cover a large number of languages and cultures. In this paper, we pre…
Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown
Emile Anand, Sarah Liaw
Thompson Sampling (TS) is widely used to address the exploration/exploitation tradeoff in contextual bandits, yet recent theory shows that it does not explore aggressively enough i…
The Structural Complexity of Matrix-Vector Multiplication
Emile Anand, Jan van den Brand, Rose McCarty
We consider the problem of preprocessing an matrix , and supporting queries that, for any vector , returns the matrix-vector product . This…
Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits
Emile Anand
Expander graphs are among the most useful combinatorial objects in theoretical computer science. A line of work studies random walks on expander graphs for their pseudorandomness a…
Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning
Emile Anand, Ishani Karmarkar, Guannan Qu
Designing efficient algorithms for multi-agent reinforcement learning (MARL) is fundamentally challenging because the size of the joint state and action spaces grows exponentially…
Peer-to-Peer Learning Dynamics of Wide Neural Networks
Shreyas Chaudhari, Srinivasa Pranav, Emile Anand +1
Peer-to-peer learning is an increasingly popular framework that enables beyond-5G distributed edge devices to collaboratively train deep neural networks in a privacy-preserving man…
Online Policy Optimization in Unknown Nonlinear Systems
Yiheng Lin, James A. Preiss, Fengze Xie +4
We study online policy optimization in nonlinear time-varying dynamical systems where the true dynamical models are unknown to the controller. This problem is challenging because,…
Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale
Emile Anand, Guannan Qu
We study reinforcement learning for global decision-making in the presence of local agents, where the global decision-maker makes decisions affecting all local agents, and the obje…
The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
Emile Anand, Jan van den Brand, Mehrdad Ghadiri +1
Many iterative algorithms in optimization, computational geometry, computer algebra, and other areas of computer science require repeated computation of some algebraic expression w…
Pseudorandomness of the Sticky Random Walk
Emile Anand, Chris Umans
We extend the pseudorandomness of random walks on expander graphs using the sticky random walk. Building on prior works, it was recently shown that expander random walks can fool a…
Identifying Chemicals Through Dimensionality Reduction
Emile Anand, Charles Steinhardt, Martin Hansen
Civilizations have tried to make drinking water safe to consume for thousands of years. The process of determining water contaminants has evolved with the complexity of the contami…
Online Adaptive Policy Selection in Time-Varying Systems: No-Regret via Contractive Perturbations
Yiheng Lin, James A. Preiss, Emile Anand +3
We study online adaptive policy selection in systems with time-varying costs and dynamics. We develop the Gradient-based Adaptive Policy Selection (GAPS) algorithm together with a…