Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Sepehr Assadi"'
Publikováno v:
TheoretiCS, Vol Volume 2 (2023)
Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never
Externí odkaz:
https://doaj.org/article/ffab2e0c5c474015b5e4200cc0f3663c
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_________::3ff4325ebb85effcf820f9de9ca5ddd9
https://doi.org/10.1137/1.9781611977554.ch20
https://doi.org/10.1137/1.9781611977554.ch20
Autor:
Sepehr Assadi, Vihan Shah
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3963c1050be219ecfc19e0d93486756b
https://doi.org/10.1137/1.9781611977585.ch20
https://doi.org/10.1137/1.9781611977585.ch20
Publikováno v:
Proceedings of the 2022 International Conference on Management of Data.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::07a54364b0874a9fab67da941fb28930
https://doi.org/10.1145/3514221.3517908
https://doi.org/10.1145/3514221.3517908
Publikováno v:
ACM Transactions on Algorithms. 18:1-2
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8469aaed9eb04b91f57792dd7b0b9de6
https://doi.org/10.1145/3561912
https://doi.org/10.1145/3561912
Autor:
Sepehr Assadi
Publikováno v:
EC
We study the necessity of interaction for obtaining efficient allocations in combinatorial auctions with subadditive bidders . This problem was originally introduced by Dobzinski, Nisan, and Oren (STOC’14) as the following simple market scenario: m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::91695d2f0a9a4b6c6c7b662644e78c7d
https://doi.org/10.1145/3381521
https://doi.org/10.1145/3381521
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are $n$ players corresponding to vertices of an undirected graph, and each player sees the edges inc
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::120bbac0a3f725976587a8fde1890479
Graph Streaming Lower Bounds for Parameter Estimation and Property Testing via a Streaming XOR Lemma
Autor:
Vishvajeet N, Sepehr Assadi
Publikováno v:
STOC
We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c396f5eb11274558ba3a4e9e6211919