Zobrazeno 1 - 10
of 47
pro vyhledávání: '"Pasin Manurangsi"'
Publikováno v:
Algorithms, Vol 13, Iss 6, p 146 (2020)
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We survey developments in the area both from the algorithmic and hardness pers
Externí odkaz:
https://doaj.org/article/a0a16c20302d47f7ad8b8fcbef00cee5
Autor:
Pasin Manurangsi
Publikováno v:
Algorithms, Vol 11, Iss 1, p 10 (2018)
The Small Set Expansion Hypothesis is a conjecture which roughly states that it is NP-hard to distinguish between a graph with a small subset of vertices whose (edge) expansion is almost zero and one in which all small subsets of vertices have expans
Externí odkaz:
https://doaj.org/article/f6c9bd85f04e4b5f8b4eb70f332de106
Publikováno v:
Proceedings on Privacy Enhancing Technologies. 2022:626-644
In this paper, we study the task of aggregating user-generated trajectories in a differentially private manner. We present a new algorithm for this problem and demonstrate its effectiveness and practicality through detailed experiments on real-world
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6e0da94a4abd631e5a09791314228cdb
https://doi.org/10.56553/popets-2022-0125
https://doi.org/10.56553/popets-2022-0125
Autor:
Edith Elkind, Piotr Faliszewski, Ayumi Igarashi, Pasin Manurangsi, Ulrike Schmidt-Kraepelin, Warut Suksompong
Publikováno v:
AAAI Conference on Artificial Intelligence
In multiwinner approval voting, the goal is to select $k$-member committees based on voters' approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::58b7812924766fbcf859a9e80ba795a3
https://doi.org/10.1609/aaai.v36i5.20429
https://doi.org/10.1609/aaai.v36i5.20429
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1e22380019e993ba754a70067183dd84
https://doi.org/10.1137/1.9781611977585.ch14
https://doi.org/10.1137/1.9781611977585.ch14
Autor:
Justin Y. Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Shyam Narayanan, Jelani Nelson, Yinzhan Xu
Publikováno v:
Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ISBN: 9781611977554
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::1ce403e6acb45299895dfc4a1d6fa2c7
https://doi.org/10.1137/1.9781611977554.ch184
https://doi.org/10.1137/1.9781611977554.ch184
Autor:
Ravi Kumar, Jiayu Peng, Ben Kreuter, Pasin Manurangsi, Craig William Wright, Evgeny Skvortsov, Yao Wang, Badih Ghazi
Publikováno v:
Proceedings on Privacy Enhancing Technologies, Vol 2022, Iss 1, Pp 373-395 (2022)
Consider the setting where multiple parties each hold a multiset of users and the task is to estimate thereach(i.e., the number of distinct users appearing across all parties) and thefrequency histogram(i.e., fraction of users appearing a given numbe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::08f58729557da9a55862bb2d7e41b41b
https://doi.org/10.2478/popets-2022-0019
https://doi.org/10.2478/popets-2022-0019
Autor:
James Bell, Adrià Gascón, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, Phillipp Schoppmann
Publikováno v:
Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::76e4ad8cf95f565b971a335d788fe5be
https://doi.org/10.1145/3548606.3559383
https://doi.org/10.1145/3548606.3559383
The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD-based accounting allows for tighter $(\varepsilon, \delta)$-DP guaran
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::83cc1f57e75ce4b329c3c7e765354269
http://arxiv.org/abs/2207.04380
http://arxiv.org/abs/2207.04380
Autor:
Pasin Manurangsi, Warut Suksompong
Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of play
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::52724ffeadc556c63285c6d85acb3a83