-
Statistical and computational thresholds for the planted k-densest sub-hypergraph problem
Recovery a planted signal perturbed by noise is a fundamental problem in...
11/23/2020 ∙ by Luca Corinzia, et al. ∙
9
∙
share
read it
-
A Robust Framework for Analyzing Gradient-Based Dynamics in Bilinear Games
In this work, we establish a frequency-domain framework for analyzing gr...
10/07/2020 ∙ by Ioannis Anagnostides, et al. ∙
0
∙
share
read it
-
Solving Zero-Sum Games through Alternating Projections
In this work, we establish near-linear and strong convergence for a natu...
09/30/2020 ∙ by Ioannis Anagnostides, et al. ∙
0
∙
share
read it
-
Two-way Greedy: Algorithms for Imperfect Rationality
The realization that selfish interests need to be accounted for in the d...
07/23/2020 ∙ by Diodato Ferraioli, et al. ∙
0
∙
share
read it
-
Exact Recovery for a Family of Community-Detection Generative Models
Generative models for networks with communities have been studied extens...
01/21/2019 ∙ by Luca Corinzia, et al. ∙
0
∙
share
read it
-
Online scheduling of jobs with favorite machines
This work introduces a natural variant of the online machine scheduling ...
12/04/2018 ∙ by Cong Chen, et al. ∙
0
∙
share
read it
-
On the approximation guarantee of obviously strategyproof mechanisms
The concept of obviously strategyproof (OSP) mechanisms has the merit to...
05/10/2018 ∙ by Diodato Ferraioli, et al. ∙
0
∙
share
read it
-
Optimal Sorting with Persistent Comparison Errors
We consider the problem of sorting n elements in the case of persistent ...
04/20/2018 ∙ by Barbara Geissmann, et al. ∙
0
∙
share
read it
-
No truthful mechanism can be better than n approximate for two natural problems
This work gives the first natural non-utilitarian problems for which the...
12/18/2017 ∙ by Stefano Leucci, et al. ∙
0
∙
share
read it
-
Selfish Jobs with Favorite Machines: Price of Anarchy vs Strong Price of Anarchy
We consider the well-studied game-theoretic version of machine schedulin...
09/19/2017 ∙ by Cong Chen, et al. ∙
0
∙
share
read it
