54 citations · 150 across the 11 of their papers we have counts for
15 papers
Highway: Efficient Consensus with Flexible Finality
Daniel Kane, Andreas Fackler, Adam Gągol +1
There has been recently a lot of progress in designing efficient partially synchronous BFT consensus protocols that are meant to serve as core consensus engines for Proof of Stake…
Aleph: Efficient Atomic Broadcast in Asynchronous Networks with Byzantine Nodes
Adam Gągol, Damian Leśniak, Damian Straszak +1
The spectacular success of Bitcoin and Blockchain Technology in recent years has provided enough evidence that a widespread adoption of a common cryptocurrency system is not merely…
Fair and Diverse DPP-based Data Summarization
L. Elisa Celis, Vijay Keswani, Damian Straszak +3
Sampling methods that choose a subset of the data proportional to its diversity in the feature space are popular for data summarization. However, recent studies have noted the occu…
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…
Belief Propagation, Bethe Approximation and Polynomials
Damian Straszak, Nisheeth K. Vishnoi
Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems…
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…
Strong inapproximability of the shortest reset word
Pawel Gawrychowski, Damian Straszak
The Černý conjecture states that every -state synchronizing automaton has a reset word of length at most . We study the hardness of finding short reset words. It is kno…
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…