54 citations · 150 across the 11 of their papers we have counts for
10 papers · 1 filter
Maximum Entropy Distributions: Bit Complexity and Stability
Damian Straszak, Nisheeth K. Vishnoi
Maximum entropy distributions with discrete support in dimensions arise in machine learning, statistics, information theory, and theoretical computer science. While structural…
Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi
Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors and a constraint family ${\cal…
Ranking with Fairness Constraints
L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi
Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown t…
On Convex Programming Relaxations for the Permanent
Damian Straszak, Nisheeth K. Vishnoi
In recent years, several convex programming relaxations have been proposed to estimate the permanent of a non-negative matrix, notably in the works of Gurvits and Samorodnitsky. Ho…
Real Stable Polynomials and Matroids: Optimization and Counting
Damian Straszak, Nisheeth K. Vishnoi
A great variety of fundamental optimization and counting problems arising in computer science, mathematics and physics can be reduced to one of the following computational tasks in…
On the Complexity of Constrained Determinantal Point Processes
L. Elisa Celis, Amit Deshpande, Tarun Kathuria +2
Determinantal Point Processes (DPPs) are probabilistic models that arise in quantum physics and random matrix theory and have recently found numerous applications in computer scien…
IRLS and Slime Mold: Equivalence and Convergence
Damian Straszak, Nisheeth K. Vishnoi
In this paper we present a connection between two dynamical systems arising in entirely different contexts: one in signal processing and the other in biology. The first is the famo…
On a Natural Dynamics for Linear Programming
Damian Straszak, Nisheeth K. Vishnoi
In this paper we study dynamics inspired by Physarum polycephalum (a slime mold) for solving linear programs [NTY00, IJNT11, JZ12]. These dynamics are arrived at by a local and mec…
Fast Generation of Random Spanning Trees and the Effective Resistance Metric
Aleksander Madry, Damian Straszak, Jakub Tarnawski
We present a new algorithm for generating a uniformly random spanning tree in an undirected graph. Our algorithm samples such a tree in expected time. This imp…
Beating O(nm) in approximate LZW-compressed pattern matching
Pawel Gawrychowski, Damian Straszak
Given an LZW/LZ78 compressed text, we want to find an approximate occurrence of a given pattern of length m. The goal is to achieve time complexity depending on the size n of the c…