research
∙
11/17/2022
Data-Centric Debugging: mitigating model failures via targeted data collection
Deep neural networks can be unreliable in the real world when the traini...
share
research
∙
11/15/2022
Improved techniques for deterministic l2 robustness
Training convolutional neural networks (CNNs) with a strict 1-Lipschitz ...
research
∙
10/25/2022
Online and Bandit Algorithms Beyond ℓ_p Norms
Vector norms play a fundamental role in computer science and optimizatio...
research
∙
07/11/2022
Submodular Dominance and Applications
In submodular optimization we often deal with the expected value of a su...
research
∙
04/25/2022
Smoothed Analysis of the Komlós Conjecture
The well-known Komlós conjecture states that given n vectors in ℝ^d with...
research
∙
03/28/2022
Core Risk Minimization using Salient ImageNet
Deep neural networks can be unreliable in the real world especially when...
research
∙
12/24/2021
Robust Secretary and Prophet Algorithms for Packing Integer Programs
We study the problem of solving Packing Integer Programs (PIPs) in the o...
research
∙
11/13/2021
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
A well-known result of Banaszczyk in discrepancy theory concerns the pre...
research
∙
11/11/2021
Online Discrepancy with Recourse for Vectors and Graphs
The vector-balancing problem is a fundamental problem in discrepancy the...
research
∙
11/07/2021
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
Babaioff et al. [BIK2007] introduced the matroid secretary problem in 20...
research
∙
10/08/2021
Causal ImageNet: How to discover spurious features in Deep Learning?
A key reason for the lack of reliability of deep neural networks in the ...
research
∙
08/05/2021
Householder Activations for Provable Robustness against Adversarial Attacks
Training convolutional neural networks (CNNs) with a strict Lipschitz co...
research
∙
07/13/2021
Bag-of-Tasks Scheduling on Related Machines
We consider online scheduling to minimize weighted completion time on re...
research
∙
05/24/2021
Skew Orthogonal Convolutions
Training convolutional neural networks with a Lipschitz constraint under...
research
∙
02/15/2021
Low Curvature Activations Reduce Overfitting in Adversarial Training
Adversarial training is one of the most effective defenses against adver...
research
∙
10/14/2020
Online Learning with Vector Costs and Bandits with Knapsacks
We introduce online learning with vector costs () where in each time ste...
research
∙
10/03/2020
Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
We present a computationally-efficient truthful mechanism for combinator...
research
∙
07/26/2020
Efficient Approximation Schemes for Stochastic Probing and Prophet Problems
Our main contribution is a general framework to design efficient polynom...
research
∙
07/21/2020
Online Discrepancy Minimization for Stochastic Arrivals
In the stochastic online vector balancing problem, vectors v_1,v_2,…,v_T...
research
∙
07/21/2020
Online Carpooling using Expander Decompositions
We consider the online carpooling problem: given n vertices, a sequence ...
research
∙
06/22/2020
Perceptual Adversarial Robustness: Defense Against Unseen Threat Models
We present adversarial attacks and defenses for the perceptual adversari...
research
∙
06/17/2020
Fairness Through Robustness: Investigating Robustness Disparity in Deep Learning
Deep neural networks are being increasingly used in real world applicati...
research
∙
06/01/2020
Second-Order Provable Defenses against Adversarial Attacks
A robustness certificate is the minimum distance of a given input to the...
research
∙
02/25/2020
Random-Order Models
This chapter introduces the random-order model in online algorithms. In ...
research
∙
01/28/2020
Prophet Inequalities with Linear Correlations and Augmentations
In a classical online decision problem, a decision-maker who is trying t...
research
∙
12/06/2019
Online Vector Balancing and Geometric Discrepancy
We consider an online vector balancing question where T vectors, chosen ...
research
∙
11/25/2019
Faster Matroid Intersection
In this paper we consider the classic matroid intersection problem: give...
research
∙
11/22/2019
Bounding Singular Values of Convolution Layers
In deep neural networks, the spectral norm of the Jacobian of a layer bo...
research
∙
11/17/2019
Robust Algorithms for the Secretary Problem
In classical secretary problems, a sequence of n elements arrive in a un...
research
∙
11/07/2019
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
A longstanding open problem in Algorithmic Mechanism Design is to design...
research
∙
11/06/2019
Algorithms and Adaptivity Gaps for Stochastic k-TSP
Given a metric (V,d) and a root∈ V, the classic k-TSP problem is to find...
research
∙
10/02/2019
Online Geometric Discrepancy for Stochastic Arrivals with Applications to Envy Minimization
Consider a unit interval [0,1] in which n points arrive one-by-one indep...
research
∙
05/28/2019
Certifiably Robust Interpretation in Deep Learning
Although gradient-based saliency maps are popular methods for deep learn...
research
∙
05/13/2019
Approximation Schemes for a Buyer with Independent Items via Symmetries
We consider a revenue-maximizing seller with n items facing a single buy...
research
∙
05/06/2019
Non-clairvoyant Precedence Constrained Scheduling
We consider the online problem of scheduling jobs on identical machines,...
research
∙
02/21/2019
The Markovian Price of Information
Suppose there are n Markov chains and we need to pay a per-step price to...
research
∙
02/04/2019
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Consider a kidney-exchange application where we want to find a max-match...
research
∙
02/01/2019
Understanding Impacts of High-Order Loss Approximations and Features in Deep Learning Interpretation
Current methods to interpret deep learning models by generating saliency...
research
∙
02/01/2019
Robustness Certificates Against Adversarial Examples for ReLU Networks
While neural networks have achieved high performance in different learni...
research
∙
11/28/2018
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
In this paper we study how to optimally balance cheap inflexible resourc...
research
∙
06/25/2018
Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities
Online contention resolution schemes (OCRSs) were proposed by Feldman, S...
research
∙
11/01/2017
The Price of Information in Combinatorial Optimization
Consider a network design application where we wish to lay down a minimu...
research
∙
10/30/2017