Zobrazeno 1 - 10
of 236
pro vyhledávání: '"Lane A. Hemaspaandra"'
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 297, Iss Proc. TARK 2019, Pp 233-251 (2019)
Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all voters' votes. But neither of those assumptions always holds. In many real-world settings, votes come in sequential
Externí odkaz:
https://doaj.org/article/a50352c789bd487d9ff4444566ec13ed
Autor:
Lane A. Hemaspaandra
Publikováno v:
ACM SIGACT News. 54:82-89
It has been a tremendous treat being the SIGACT News Complexity Theory Column editor for these past thirty years. I thought about what to say here, and realized it is pretty simple: Thank you.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::490035f87de4cf272f564e39722bc8f9
https://doi.org/10.1145/3586165.3586176
https://doi.org/10.1145/3586165.3586176
Autor:
Lane A. Hemaspaandra
Publikováno v:
ACM SIGACT News. 53:35-40
Juris Hartmanis was so preternaturally wise and brilliant that in time people may find it hard to believe that someone so extraordinary existed in this world. Yet as I write this, three months to the day after Juris passed away, it still seems imposs
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8ef4f532d6014e064887a47374f3a81a
https://doi.org/10.1145/3577971.3577977
https://doi.org/10.1145/3577971.3577977
Publikováno v:
Journal of Computer and System Sciences. 127:66-90
Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all votes. However, in many real-world settings votes come in sequentially, and the briber may have a use-it-or-lose-it
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2d023e875a525ae1842cc79d27a0ec23
https://doi.org/10.1016/j.jcss.2022.01.006
https://doi.org/10.1016/j.jcss.2022.01.006
Publikováno v:
Journal of Computer and System Sciences. 120:162-176
The rankable and the compressible sets have been studied for more than a quarter of a century. We ask whether these classes are closed under the most important boolean and other operations. We study this question for both polynomial-time and recursio
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d469109fa1e0b61f6c0ef09508337ec5
https://doi.org/10.1016/j.jcss.2021.02.004
https://doi.org/10.1016/j.jcss.2021.02.004
Autor:
Lane A. Hemaspaandra
Publikováno v:
ACM SIGACT News. 52:41-46
Warmest thanks to Rafael Pass and Muthu Venkitasubramaniam for this issue's guest column, "Average-Case Complexity Through the Lens of Interactive Puzzles." When I mentioned to them that my introduction would have a section on Alan Selman's passing,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e5185e3af1885977e7fb593655b47eb6
https://doi.org/10.1145/3457588.3457597
https://doi.org/10.1145/3457588.3457597
Autor:
Lane A. Hemaspaandra
Publikováno v:
ACM SIGACT News. 51:55-58
As I write this in July 2020, I have no idea what the COVID-19 situation will be like when this September 2020 issue reaches your mailbox or your previewer. My typical advice is to prove exciting theorems. But in these times, all I can share are my h
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e83d238b0196e54475b777b33fd6545d
https://doi.org/10.1145/3427361.3427371
https://doi.org/10.1145/3427361.3427371
Publikováno v:
computational complexity. 29
We show that the counting class LWPP remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial numbe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ed73391f96cab2a19e34a3ed95e29a58
https://doi.org/10.1007/s00037-020-00197-5
https://doi.org/10.1007/s00037-020-00197-5
Publikováno v:
Autonomous Agents and Multi-Agent Systems. 34
Unfortunately, a post-galley copyediting error altered the contents of cells in the Condorcet Elections columns of the table in Footnote 7.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b059673f0d2f6d4151862250e5216e10
https://doi.org/10.1007/s10458-020-09482-7
https://doi.org/10.1007/s10458-020-09482-7
Autor:
Lane A. Hemaspaandra
Publikováno v:
Complexity and Approximation ISBN: 9783030416713
Complexity and Approximation
Complexity and Approximation
This chapter provides a hands-on tutorial on the important technique known as self-reducibility. Through a series of “Challenge Problems” that are theorems that the reader will—after being given definitions and tools—try to prove, the tutoria
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3c873af1419f736eccd33f09bdc2725e
https://doi.org/10.1007/978-3-030-41672-0_3
https://doi.org/10.1007/978-3-030-41672-0_3
