Research

Sample Complexity of Multicalibration for Multilevel Properties

With J. Lu, K. Balasubramanian, and A. Podkopaev

A Quantitative Characterization of Forgetting in Post-Training

With K. Balasubramanian

FoundCause: Causal Discovery with Latent Confounders from Observational Data

With P. Bloebaum and K. Balasubramanian

Debiasing Reward Models via Identifiable Causal Representations

With I. Ng, P. Bloebaum, S. Bhandari, and K. Zhang

Optimal Transportation and Alignment Between Gaussian Measures

With S. Dandapanthula, A. Podkopaev, A. Ramdas, and Z. Goldfeld

Foundations of Global Consistency Checking with Noisy LLM Oracles

With P. He and E. Kirschbaum

Measuring Semantic Progress in Multi-turn Dialogue via Information Gain

With P. He and D. Janzing

What Causes Postoperative Aspiration?

With S. Nagesh, K, Covarrubias, R. El-Kareh, and N. Mishra

A Classical View on Benign Overfitting: The Role of Sample Size

With J. Park and P. Bloebaum

Anytime-Valid Inference for Double/Debiased Machine Learning of Causal Parameters

With A. Dalal, P. Bloebaum, and A. Ramdas

Global Consistency Repair for Natural-Language Claim Sets

With P. He and E. Kirschbaum

Group Adaptive Clipping Policy Optimization

With S. Jia, X. Wang, and R. Houthooft

Dependence-Aware Label Aggregation for LLM-as-a-Judge via Ising Models

With K. Balasubramanian and A. Podkopaev

Training Large Language Models to Reason in Parallel with Global Forking Tokens

With S. Jia and X. Wang

Learning to Answer from Correct Demonstrations

With N. Joshi, G. Li, S. Bhandari, C. Ma, and N. Srebro

From Guess2Graph: When and How Can Unreliable Experts Safely Boost Causal Discovery in Finite Samples?

With S. Hiremath, D. Janzing, P. Faller, P. Blobaum, E. Kirschbaum, and K. Gan

QA-Calibration of Language Model Confidence Scores

With P. Manggala, A. Mastakouri, E. Kirschbaum, and A. Ramdas

Modeling Causal Mechanisms with Diffusion Models for Interventional and Counterfactual Queries

With P. Chao, P. Bloebaum, and S. Patel

In Transactions on Machine Learning Research 2024

Preliminary version in ICML Workshop: Could it have been different? Counterfactuals in Minds and Machines, 2023

Differentially Private Conditional Independence Testing

With I. Kalemaj and A. Ramdas

The PetShop Dataset — Finding Causes of Performance Issues across Microservices

With M. Hardt, W. Orchard, P. Bloebaum, and E. Kirschbaum

Debiasing Conditional Stochastic Optimization

With L. He

Thompson Sampling with Diffusion Generative Prior

With Y. Hsieh, B. Kveton, and P. Bloebaum

Sequential Kernelized Independence Testing

With A. Podkopaev, P. Bloebaum, and A. Ramdas

Uplifting Bandits

With Y. Hsieh and B. Kveton

On Measuring Causal Contributions via do-interventions

With Y. Jung, J. Tian, D. Janzing, P. Bloebaum, and E. Bareinboim

Balancing Utility and Scalability in Metric Differential Privacy

With J. Imola, S. White, A. Aggarwal, and N. Teissier

Reconstructing Test Labels from Noisy Loss Functions

With A. Aggarwal, Z. Xu, O. Feyisetan, and N. Teissier

Collaborative Causal Discovery with Atomic Interventions

With R. Addanki

Label Inference Attacks from Log-loss Scores

With A. Aggarwal, Z. Xu, O. Feyisetan, and N. Teissier

Selected for long oral presentation

Federated Learning under Arbitrary Communication Patterns

With Dmitrii Avdyukhin

SGD with Low-Dimensional Gradients with Applications to Private and Distributed Learning

Private Release of Text Embedding Vectors

With O. Feyisetan

Restricted Isometry Property under High Correlations

With M. Rudelson

Efficient Intervention Design for Causal Discovery with Latents

With R. Addanki, A. McGregor, and C. Musco

Contextual Online False Discovery Rate Control

With S. Chen

Subsampled Renyi Differential Privacy and Analytical Moments Accountant

With Y. Wang and B. Balle

AISTATS 2019 version selected for oral presentation

Winner of Notable Paper Award at AISTATS 2019

Full version, In Journal of Privacy and Confidentiality, 2020

Preliminary versions in PPML 2018 and TPDP 2018 - Theory and Practice of Differential Privacy

Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression

With M. Rudelson

Semi-Supervised Learning on Data Streams via Temporal Label Propagation

With T. Wagner, S. Guha, and N. Mishra

Network Approximation using Tensor Sketching

With N. Narodytska and H. Jin

Preliminary version in NIPS 2016 Workshop on Deep Learning: Bridging Theory and Practice

Full version of this paper can be found here

Verifying Properties of Binarized Deep Neural Networks

With N. Narodytska, L. Ryzhyk, M. Sagiv, and T. Walsh

Simple Black-Box Adversarial Attacks on Deep Neural Networks

With N. Narodytska

Preliminary version appeared at the NIPS 2016 Workshop on Adversarial Training

Private Incremental Regression

With K. Nissim and H. Jin

Efficient Private Empirical Risk Minimization for High-dimensional Learning

With H. Jin

Streaming Anomaly Detection Using Randomized Matrix Sketching

With H. Huang

Streaming Spectral Clustering

With S. Yoo and H. Huang

Private Spatial Data Aggregation in the Local Setting

With R. Chen, H. Li, A.K. Win, and H. Jin

Invited to IEEE Transactions on Knowledge and Data Engineering (special issue)

Spectral Norm of Random Kernel Matrices with Applications to Privacy

With M. Rudelson

Unsupervised Feature Selection on Data Streams

With H. Huang and S. Yoo

Online Dictionary Learning on Symmetric Positive Definite Manifolds with Vision Applications

With S. Zhang, P. Yuen, and M. Harandi

Associated code can be found here: here

On the Semantics of Differential Privacy: A 'Bayesian' Formulation

With A. Smith

In Journal of Privacy and Confidentiality, 2014

Earlier version: A Note on Differential Privacy: Defining Resistance to Arbitrary Side Information

Bounds on the Sample Complexity for Private Learning and Private Data Release

With A. Beimel, H. Brenner, and K. Nissim

In Machine Learning Journal, 2014

Earlier version appeared in proceedings of TCC 2010

The Power of Linear Reconstruction Attacks

With M. Rudelson and A. Smith

Analyzing Graphs with Node Differential Privacy

With K. Nissim, S. Raskhodnikova, and A. Smith

Full version of this paper can be found here

Fast Online L1-Dictionary Learning Algorithms For Novel Document Detection

Invited presentation

Special session on Sparse Signal Techniques for Web Information Processing

Novel Document Detection on Massive Data Streams using Distributed Dictionary Learning

With G. Cong, P. Melville, and R. Lawrence

In IBM Journal of Research and Development, 2013

Approximately Counting Embeddings into Random Graphs

With M. Furer

In Combinatorics, Probability & Computing, 2014 (special issue on Analysis of Algorithms)

Earlier version appeared in proceedings of RANDOM 2008

An Exponential Time 2-Approximation Algorithm for Bandwidth

With M. Furer and S. Gaspers

In Theoretical Computer Science, 2013 (special issue on Exact & Parameterized Computation)

Earlier version appeared in proceedings of IWPEC 2009

Online L1-Dictionary Learning with Application to Novel Document Detection

With H. Wang, A. Banerjee, and P. Melville

Full version of this paper can be found here

Preliminary version appeared at the KDD SOMA Workshop 2012

Efficient and Practical Stochastic Subgradient Descent for Nuclear Norm Regularization

With H. Avron, S. Kale, and V. Sindhwani

Emerging Topic Detection Using Dictionary Learning

With P. Melville, A. Banerjee, and V. Sindhwani

Full version of this paper can be found here

Geography-Based Analysis of the Internet Infrastructure

With S. Eidenbenz and G. Yan

Full version of this paper can be found here

The Rigidity Transition for Random Graphs

With C. Moore and L. Theran

Efficient Placement of Directional Antennas in Infrastructure-based Wireless Networks

With F. Pan

What Can We Learn Privately?

With H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith

In SIAM Journal on Computing, 2011 (special issue for selected papers from FOCS 2008)

Earlier version appeared in proceedings of FOCS 2008

The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows

With M. Rudelson, A. Smith, and J. Ullman

Full version of this paper can be found here

Matrix Interdiction Problem

With F. Pan

Spatial Scattering for Load Balancing in Conservatively Synchronized Parallel Discrete-Event Simulations

With S. Thulasidasan, S. Eidenbenz, and P. Romero

Bandwidth Provisioning in Infrastructure based Wireless Networks Employing Directional Antennas

With B. Zhao, B. Urgaonkar, and S. Vasudevan

In Pervasive and Mobile Computing, 2011 (special issue for selected papers from ICDCN 2010)

Earlier version appeared in proceedings of ICDCN 2010

Designing Systems for Large-Scale, Discrete-Event Simulations: Experiences with the FastTrans Microsimulator

With S. Thulasidasan, S. Eidenbenz, E. Galli, S. Mniszewski, and P. Romero

Composition Attacks and Auxiliary Information in Data Privacy

With S. R. Ganta and A. Smith

Approximation Algorithms for Graph Problems (please email me for a copy)

Ph.D. Thesis, Penn State University, 2008

Packing to Angles and Sectors

With P. Berman, J. Jeong, and B. Urgaonkar

Spanners for Geometric Intersection Graphs with Applications

With M. Furer

In Journal of Computational Geometry, 2012

Earlier version appeared in proceedings of WADS 2007

Faster Approximation of Distances in Graphs

With P. Berman

Exact Max 2-SAT: Easier and Faster

With M. Furer

Winner of best paper award

Approximate Distance Queries in Disk Graphs

With M. Furer

Combinatorics of TCP Reordering

With A. Hansson and G. Istrate

In Journal of Combinatorial Optimization, 2006

Approximately Counting Perfect Matchings in General Graphs

With M. Furer

Algorithms for Counting 2-SAT Solutions and Colorings with Applications

With M. Furer

Full version appeared as ECCC report TR05-033, 2005

An Almost Linear Time Approximation Algorithm for the Permanent of Random (0-1) Matrix

With M. Furer