6 citations · 12 across the 10 of their papers we have counts for
11 papers
Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits
Nikolai Karpov, Qin Zhang
In this paper, we study the collaborative learning model, which concerns the tradeoff between parallelism and communication overhead in multi-agent multi-armed bandits. For regret…
Communication-Efficient Collaborative Best Arm Identification
Nikolai Karpov, Qin Zhang
We investigate top- arm identification, a basic problem in bandit theory, in a multi-agent learning model in which agents collaborate to learn an objective function. We are inte…
Parallel Best Arm Identification in Heterogeneous Environments
Nikolai Karpov, Qin Zhang
In this paper, we study the tradeoffs between the time and the number of communication rounds of the best arm identification problem in the heterogeneous collaborative learning mod…
Batched Thompson Sampling for Multi-Armed Bandits
Nikolai Karpov, Qin Zhang
We study Thompson Sampling algorithms for stochastic multi-armed bandits in the batched setting, in which we want to minimize the regret over a sequence of arm pulls using a small…
Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
Nikolai Karpov, Qin Zhang
Motivated by real-world applications such as fast fashion retailing and online advertising, the Multinomial Logit Bandit (MNL-bandit) is a popular model in online learning and oper…
Collaborative Top Distribution Identifications with Limited Interaction
Nikolai Karpov, Qin Zhang, Yuan Zhou
We consider the following problem in this paper: given a set of distributions, find the top- ones with the largest means. This problem is also called {\em top- arm identi…
Distributed and Streaming Linear Programming in Low Dimensions
Sepehr Assadi, Nikolai Karpov, Qin Zhang
We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of…
Parameterized Algorithms for Partitioning Graphs into Highly Connected Clusters
Ivan Bliznets, Nikolai Karpov
Clustering is a well-known and important problem with numerous applications. The graph-based model is one of the typical cluster models. In the graph model, clusters are generally…
An exponential lower bound for cut sparsifiers in planar graphs
Nikolai Karpov, Marcin Pilipczuk, Anna Zych-Pawlewicz
Given an edge-weighted graph with a set of terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the sizes of minimum cuts bet…
Parameterized Complexity of Superstring Problems
Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach +3
In the Shortest Superstring problem we are given a set of strings and integer and the question is to decide whether there is a superstring of le…
Parameterized Complexity of Secluded Connectivity Problems
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov +1
The Secluded Path problem models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of a…