1 citations · 1 across the 10 of their papers we have counts for
13 papers
Quiet Planting for -SAT, Multiple Solutions of Arbitrary Geometry
Ali Ahmadi, Kiarash Banihashem, Iman Gholami +2
Recent work on "quiet planting" in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distributio…
Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
Dariusz R. Kowalski, Jan Olkowski
Load balancing is among the basic primitives in distributed computing. In this paper, we consider this problem when executed locally on a network with nodes prone to failures. We s…
Beating Competitive Ratio 4 for Graphic Matroid Secretary
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +3
One of the classic problems in online decision-making is the *secretary problem* where to goal is to maximize the probability of choosing the largest number from a randomly ordered…
Dynamic Metric Embedding into Space
Kiarash Banihashem, MohammadTaghi Hajiaghayi, Dariusz R. Kowalski +2
We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph into space. Given a weighted graph undergoing a sequence of edge weight…
Nearly-Optimal Consensus Tolerating Adaptive Omissions: Why is a Lot of Randomness Needed?
Mohammad T. Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski
We study the problem of reaching agreement in a synchronous distributed system by autonomous parties, when the communication links from/to faulty parties can omit messages. The…
Trading Prophets
José Correa, Andrés Cristi, Paul Dütting +3
In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm…
Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
Bogdan S. Chlebus, Dariusz R. Kowalski, Jan Olkowski
We develop deterministic algorithms for the problems of consensus, gossiping and checkpointing with nodes prone to failing. Distributed systems are modeled as synchronous complete…
Fault-Tolerant Consensus in Quantum Networks
MohammadTaghi Hajiaghayi, Dariusz R. Kowalski, Jan Olkowski
Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communica…
Optimal Algorithms for Free Order Multiple-Choice Secretary
Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta +1
Suppose we are given integer and boxes labeled by an adversary, each containing a number chosen from an unknown distribution. We have to choose an orde…
Adaptive Massively Parallel Algorithms for Cut Problems
MohammadTaghi Hajiaghayi, Marina Knittel, Jan Olkowski +1
We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. In 2019, Behnezhad et al. [3] introduced the AMPC model as an extension of the Ma…
Improved Communication Complexity of Fault-Tolerant Consensus
MohammadTaghi HajiAghayi, Dariusz R. Kowalski, Jan Olkowski
Consensus is one of the most thoroughly studied problems in distributed computing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the…
Online Sampling and Decision Making with Low Entropy
Mohammad Taghi Hajiaghayi, Dariusz R. Kowalski, Piotr Krysta +1
Consider the problem: we are given boxes, labeled by an adversary, each containing a single number chosen from an unknown distribution; these distributi…
Disconnected Agreement in Networks Prone to Link Failures
Bogdan S. Chlebus, Dariusz R. Kowalski, Jan Olkowski +1
We consider deterministic distributed algorithms for reaching agreement in synchronous networks of arbitrary topologies. Links are bi-directional and prone to failures while nodes…