Search results
- 1.0525399 - MÚ 2021 RIV US eng C - Conference Paper (international conference)
Gavinsky, Dmitry
Bare quantum simultaneity versus classical interactivity in communication complexity.
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. New York: Association for Computing Machinery, 2020 - (Makarychev, K.; Makarychev, Y.; Tulsiani, M.; Kamath, G.; Chuzhoy, J.), s. 401-411. ISBN 978-1-4503-6979-4.
[52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020). Chicago (US), 22.06.2020-26.06.2020]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : quantum communication complexity * communication complexity models
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
https://doi.org/10.1145/3357713.3384243
Permanent Link: http://hdl.handle.net/11104/0309548File Download Size Commentary Version Access Gavinsky.pdf 2 902.8 KB Publisher’s postprint open-access - 2.0507748 - MÚ 2020 RIV DE eng C - Conference Paper (international conference)
Gavinsky, Dmitry - Lee, T. - Santha, M. - Sanyal, S.
A composition theorem for randomized query complexity via Max-conflict complexity.
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019 - (Baier, C.; Chatzigiannakis, I.; Flocchini, P.; Leonardi, S.), č. článku 64. Leibniz International Proceedings in Informatics (LIPIcs), 132. ISBN 978-3-95977-109-2. ISSN 1868-8969.
[46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Patras (GR), 08.07.2019-12.07.2019]
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : query complexity * lower bounds
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/volltexte/2019/10640/
Permanent Link: http://hdl.handle.net/11104/0298723File Download Size Commentary Version Access Gavinsky.pdf 1 616.2 KB Publisher’s postprint require - 3.0487435 - MÚ 2018 RIV DE eng C - Conference Paper (international conference)
Anshu, A. - Gavinsky, Dmitry - Jain, R. - Kundu, S. - Lee, T. - Mukhopadhyay, P. - Santha, M. - Sanyal, S.
A composition theorem for randomized query complexity.
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2018 - (Lokam, S.; Ramanujam, R.), s. 1-13, č. článku 10. Leibniz International Proceedings in Informatics, 93. ISBN 978-3-95977-055-2. ISSN 1868-8969.
[37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Kanpur (IN), 11.12.2017-15.12.2017]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : query algorithms and complexity * decision trees * composition theorem
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/volltexte/2018/8396/
Permanent Link: http://hdl.handle.net/11104/0282096File Download Size Commentary Version Access Gavinsky.pdf 0 554.5 KB Publisher’s postprint require - 4.0463615 - MÚ 2017 RIV US eng C - Conference Paper (international conference)
Gavinsky, Dmitry
Entangled simultaneity versus classical interactivity in communication complexity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016). New York: ACM, 2016, s. 877-884. ISBN 978-1-4503-4132-5.
[STOC 2016. Symposium on Theory of Computing /48./. Cambridge (US), 19.06.2016-21.06.2016]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : quantum communication complexity * model separation
OECD category: Pure mathematics
http://dl.acm.org/citation.cfm?doid=2897518.2897545
Permanent Link: http://hdl.handle.net/11104/0262757File Download Size Commentary Version Access Gavinsky1.pdf 6 386.7 KB Publisher’s postprint require - 5.0448831 - MÚ 2016 RIV DE eng C - Conference Paper (international conference)
Bottesch, R. - Gavinsky, Dmitry - Klauck, H.
Correlation in hard distributions in communication complexity.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2015 - (Garg, N.; Jansen, K.; Rao, A.; Rolim, J.), s. 544-572. Leibniz International Proceedings in Informatics, 40. ISBN 978-3-939897-89-7. ISSN 1868-8969.
[Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Princeton (US), 24.08.2015-26.08.2015]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : communication complexity * information theory
Subject RIV: BA - General Mathematics
http://drops.dagstuhl.de/opus/volltexte/2015/5323/
Permanent Link: http://hdl.handle.net/11104/0250446File Download Size Commentary Version Access Gavinsky2.pdf 1 636.4 KB Publisher’s postprint require - 6.0447630 - MÚ 2016 RIV DE eng C - Conference Paper (international conference)
Bottesch, R. - Gavinsky, Dmitry - Klauck, H.
Equality, Revisited.
Mathematical Foundations of Computer Science 2015. Berlin: Springer, 2015 - (Italiano, G.; Pighizzini, G.; Sannella, D.), s. 127-138. Lecture Notes in Computer Science, vol. 9235. ISBN 978-3-662-48053-3.
[International Symposium of Mathematical Foundations of Computer Science 2015, MFCS 2015. Milan (IT), 28.08.2015-28.08.2015]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : equality * complexity * algorithm analysis
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007/978-3-662-48054-0_11
Permanent Link: http://hdl.handle.net/11104/0249435File Download Size Commentary Version Access Gavinsky1.pdf 1 222 KB Publisher’s postprint require - 7.0434518 - MÚ 2015 RIV DE eng C - Conference Paper (international conference)
Gavinsky, Dmitry - Pudlák, Pavel
Partition expanders.
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2014 - (Mayr, E.; Portier, N.), s. 325-336. Leibniz International Proceedings in Informatics, 25. ISBN 978-3-939897-65-1. ISSN 1868-8969.
[International Symposium on Theoretical Aspects of Computer Science (STACS 2014), /31./. Lyon (FR), 05.03.2014-08.03.2014]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : partitions * expanders * random graphs
Subject RIV: BA - General Mathematics
http://drops.dagstuhl.de/opus/volltexte/2014/4468/
Permanent Link: http://hdl.handle.net/11104/0238547File Download Size Commentary Version Access Gavinsky3.pdf 1 675.2 KB Publisher’s postprint open-access - 8.0434460 - MÚ 2015 RIV US eng C - Conference Paper (international conference)
Gavinsky, Dmitry - Meir, O. - Weinstein, O. - Wigderson, A.
Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture.
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014). New York: ACM, 2014 - (Shmoys, D.), s. 213-222. ISBN 978-1-4503-2710-7.
[STOC 2014. Symposium on Theory of Computing /46./. New York (US), 31.05.2014-03.06.2014]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : formula lower bounds * information complexity * composition conjecture
Subject RIV: BA - General Mathematics
http://dl.acm.org/citation.cfm?id=2591856&dl=ACM&coll=DL&CFID=454065209&CFTOKEN=54114198
Permanent Link: http://hdl.handle.net/11104/0238543File Download Size Commentary Version Access Gavinsky2.pdf 9 415.2 KB Publisher’s postprint require - 9.0434135 - MÚ 2015 RIV DE eng C - Conference Paper (international conference)
Gavinsky, Dmitry - Lovett, S.
En route to the log-rank conjecture: new reductions and equivalent formulations.
Automata, Languages, and Programming. Berlin: Springer, 2014 - (Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E.), s. 514-524. Lecture Notes in Computer Science, 8572. ISBN 978-3-662-43947-0.
[41st International Colloquium, ICALP 2014. Copenhagen (DK), 08.07.2014-11.07.2014]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : automata theory * matrix algebra * associated matrices * communication complexity
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-662-43948-7_43
Permanent Link: http://hdl.handle.net/11104/0238256File Download Size Commentary Version Access Gavinsky1.pdf 1 213.8 KB Publisher’s postprint require - 10.0434098 - MÚ 2015 RIV DE eng C - Conference Paper (international conference)
Bavarian, M. - Gavinsky, Dmitry - Ito, T.
On the role of shared randomness in simultaneous communication.
Automata, Languages, and Programming. Berlin: Springer, 2014 - (Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E.), s. 150-162. Lecture Notes in Computer Science, 8572. ISBN 978-3-662-43947-0.
[41st International Colloquium, ICALP 2014. Copenhagen (DK), 08.07.2014-11.07.2014]
R&D Projects: GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : automata theory * communication complexity * computational problem
Subject RIV: BA - General Mathematics
http://link.springer.com/chapter/10.1007%2F978-3-662-43948-7_13
Permanent Link: http://hdl.handle.net/11104/0238238File Download Size Commentary Version Access Gavinsky.pdf 1 242.1 KB Publisher’s postprint require