Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Arturs Backurs
@article{DBLP:journals/corr/abs-2403-01749,
author = {Chulin Xie and
Zinan Lin and
Arturs Backurs and
Sivakanth Gopi and
Da Yu and
Huseyin A. Inan and
Harsha Nori and
Haotian Jiang and
Huishuai Zhang and
Yin Tat Lee and
Bo Li and
Sergey Yekhanin},
title = {Differentially Private Synthetic Data via Foundation Model APIs 2:
Text},
journal = {CoRR},
volume = {abs/2403.01749},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2403.01749},
doi = {10.48550/ARXIV.2403.01749},
eprinttype = {arXiv},
eprint = {2403.01749},
timestamp = {Tue, 02 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2403-01749.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2403-08917,
author = {Arturs Backurs and
Zinan Lin and
Sepideh Mahabadi and
Sandeep Silwal and
Jakub Tarnawski},
title = {Efficiently Computing Similarities to Private Datasets},
journal = {CoRR},
volume = {abs/2403.08917},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2403.08917},
doi = {10.48550/ARXIV.2403.08917},
eprinttype = {arXiv},
eprint = {2403.08917},
timestamp = {Fri, 05 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2403-08917.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/iclr/HeLYZKLBY023,
author = {Jiyan He and
Xuechen Li and
Da Yu and
Huishuai Zhang and
Janardhan Kulkarni and
Yin Tat Lee and
Arturs Backurs and
Nenghai Yu and
Jiang Bian},
title = {Exploring the Limits of Differentially Private Deep Learning with
Group-wise Clipping},
booktitle = {The Eleventh International Conference on Learning Representations,
{ICLR} 2023, Kigali, Rwanda, May 1-5, 2023},
publisher = {OpenReview.net},
year = {2023},
url = {https://openreview.net/pdf?id=oze0clVGPeX},
timestamp = {Fri, 30 Jun 2023 14:38:38 +0200},
biburl = {https://dblp.org/rec/conf/iclr/HeLYZKLBY023.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2310-16960,
author = {Fan Wu and
Huseyin A. Inan and
Arturs Backurs and
Varun Chandrasekaran and
Janardhan Kulkarni and
Robert Sim},
title = {Privately Aligning Language Models with Reinforcement Learning},
journal = {CoRR},
volume = {abs/2310.16960},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2310.16960},
doi = {10.48550/ARXIV.2310.16960},
eprinttype = {arXiv},
eprint = {2310.16960},
timestamp = {Tue, 31 Oct 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2310-16960.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/iclr/YuNBGI0KLMWYZ22,
author = {Da Yu and
Saurabh Naik and
Arturs Backurs and
Sivakanth Gopi and
Huseyin A. Inan and
Gautam Kamath and
Janardhan Kulkarni and
Yin Tat Lee and
Andre Manoel and
Lukas Wutschitz and
Sergey Yekhanin and
Huishuai Zhang},
title = {Differentially Private Fine-tuning of Language Models},
booktitle = {The Tenth International Conference on Learning Representations, {ICLR}
2022, Virtual Event, April 25-29, 2022},
publisher = {OpenReview.net},
year = {2022},
url = {https://openreview.net/forum?id=Q42f0dfjECO},
timestamp = {Sat, 20 Aug 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/iclr/YuNBGI0KLMWYZ22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/MireshghallahBI22,
author = {Fatemehsadat Mireshghallah and
Arturs Backurs and
Huseyin A. Inan and
Lukas Wutschitz and
Janardhan Kulkarni},
editor = {Sanmi Koyejo and
S. Mohamed and
A. Agarwal and
Danielle Belgrave and
K. Cho and
A. Oh},
title = {Differentially Private Model Compression},
booktitle = {Advances in Neural Information Processing Systems 35: Annual Conference
on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans,
LA, USA, November 28 - December 9, 2022},
year = {2022},
url = {http://papers.nips.cc/paper\_files/paper/2022/hash/bd6bb13e78da078d8adcabbe6d9ca737-Abstract-Conference.html},
timestamp = {Mon, 08 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/MireshghallahBI22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-01838,
author = {Fatemehsadat Mireshghallah and
Arturs Backurs and
Huseyin A. Inan and
Lukas Wutschitz and
Janardhan Kulkarni},
title = {Differentially Private Model Compression},
journal = {CoRR},
volume = {abs/2206.01838},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.01838},
doi = {10.48550/ARXIV.2206.01838},
eprinttype = {arXiv},
eprint = {2206.01838},
timestamp = {Mon, 13 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-01838.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-04301,
author = {Yi Zhang and
Arturs Backurs and
S{\'{e}}bastien Bubeck and
Ronen Eldan and
Suriya Gunasekar and
Tal Wagner},
title = {Unveiling Transformers with {LEGO:} a synthetic reasoning task},
journal = {CoRR},
volume = {abs/2206.04301},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.04301},
doi = {10.48550/ARXIV.2206.04301},
eprinttype = {arXiv},
eprint = {2206.04301},
timestamp = {Tue, 14 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-04301.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2212-01539,
author = {Jiyan He and
Xuechen Li and
Da Yu and
Huishuai Zhang and
Janardhan Kulkarni and
Yin Tat Lee and
Arturs Backurs and
Nenghai Yu and
Jiang Bian},
title = {Exploring the Limits of Differentially Private Deep Learning with
Group-wise Clipping},
journal = {CoRR},
volume = {abs/2212.01539},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2212.01539},
doi = {10.48550/ARXIV.2212.01539},
eprinttype = {arXiv},
eprint = {2212.01539},
timestamp = {Thu, 08 Dec 2022 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2212-01539.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BackursRSWW21,
author = {Arturs Backurs and
Liam Roditty and
Gilad Segal and
Virginia Vassilevska Williams and
Nicole Wein},
title = {Toward Tight Approximation Bounds for Graph Diameter and Eccentricities},
journal = {{SIAM} J. Comput.},
volume = {50},
number = {4},
pages = {1155--1199},
year = {2021},
url = {https://doi.org/10.1137/18M1226737},
doi = {10.1137/18M1226737},
timestamp = {Mon, 20 Sep 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BackursRSWW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/compgeom/BackursMMM21,
author = {Arturs Backurs and
Sepideh Mahabadi and
Konstantin Makarychev and
Yury Makarychev},
editor = {Kevin Buchin and
{\'{E}}ric Colin de Verdi{\`{e}}re},
title = {Two-Sided Kirszbraun Theorem},
booktitle = {37th International Symposium on Computational Geometry, SoCG 2021,
June 7-11, 2021, Buffalo, NY, {USA} (Virtual Conference)},
series = {LIPIcs},
volume = {189},
pages = {13:1--13:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021},
url = {https://doi.org/10.4230/LIPIcs.SoCG.2021.13},
doi = {10.4230/LIPICS.SOCG.2021.13},
timestamp = {Fri, 04 Jun 2021 14:36:21 +0200},
biburl = {https://dblp.org/rec/conf/compgeom/BackursMMM21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/emnlp/WisemanBS21,
author = {Sam Wiseman and
Arturs Backurs and
Karl Stratos},
editor = {Marie{-}Francine Moens and
Xuanjing Huang and
Lucia Specia and
Scott Wen{-}tau Yih},
title = {Data-to-text Generation by Splicing Together Nearest Neighbors},
booktitle = {Proceedings of the 2021 Conference on Empirical Methods in Natural
Language Processing, {EMNLP} 2021, Virtual Event / Punta Cana, Dominican
Republic, 7-11 November, 2021},
pages = {4283--4299},
publisher = {Association for Computational Linguistics},
year = {2021},
url = {https://doi.org/10.18653/v1/2021.emnlp-main.352},
doi = {10.18653/V1/2021.EMNLP-MAIN.352},
timestamp = {Fri, 16 Feb 2024 08:27:36 +0100},
biburl = {https://dblp.org/rec/conf/emnlp/WisemanBS21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/BackursIMW21,
author = {Arturs Backurs and
Piotr Indyk and
Cameron Musco and
Tal Wagner},
editor = {Marina Meila and
Tong Zhang},
title = {Faster Kernel Matrix Algebra via Density Estimation},
booktitle = {Proceedings of the 38th International Conference on Machine Learning,
{ICML} 2021, 18-24 July 2021, Virtual Event},
series = {Proceedings of Machine Learning Research},
volume = {139},
pages = {500--510},
publisher = {{PMLR}},
year = {2021},
url = {http://proceedings.mlr.press/v139/backurs21a.html},
timestamp = {Wed, 25 Aug 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icml/BackursIMW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sosa/AxiotisBBJNTW21,
author = {Kyriakos Axiotis and
Arturs Backurs and
Karl Bringmann and
Ce Jin and
Vasileios Nakos and
Christos Tzamos and
Hongxun Wu},
editor = {Hung Viet Le and
Valerie King},
title = {Fast and Simple Modular Subset Sum},
booktitle = {4th Symposium on Simplicity in Algorithms, {SOSA} 2021, Virtual Conference,
January 11-12, 2021},
pages = {57--67},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976496.6},
doi = {10.1137/1.9781611976496.6},
timestamp = {Wed, 19 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/sosa/AxiotisBBJNTW21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2101-08248,
author = {Sam Wiseman and
Arturs Backurs and
Karl Stratos},
title = {Generating (Formulaic) Text by Splicing Together Nearest Neighbors},
journal = {CoRR},
volume = {abs/2101.08248},
year = {2021},
url = {https://arxiv.org/abs/2101.08248},
eprinttype = {arXiv},
eprint = {2101.08248},
timestamp = {Sun, 24 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2101-08248.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2102-08341,
author = {Arturs Backurs and
Piotr Indyk and
Cameron Musco and
Tal Wagner},
title = {Faster Kernel Matrix Algebra via Density Estimation},
journal = {CoRR},
volume = {abs/2102.08341},
year = {2021},
url = {https://arxiv.org/abs/2102.08341},
eprinttype = {arXiv},
eprint = {2102.08341},
timestamp = {Fri, 19 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2102-08341.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2110-06500,
author = {Da Yu and
Saurabh Naik and
Arturs Backurs and
Sivakanth Gopi and
Huseyin A. Inan and
Gautam Kamath and
Janardhan Kulkarni and
Yin Tat Lee and
Andre Manoel and
Lukas Wutschitz and
Sergey Yekhanin and
Huishuai Zhang},
title = {Differentially Private Fine-tuning of Language Models},
journal = {CoRR},
volume = {abs/2110.06500},
year = {2021},
url = {https://arxiv.org/abs/2110.06500},
eprinttype = {arXiv},
eprint = {2110.06500},
timestamp = {Fri, 22 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2110-06500.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/BackursBG20,
author = {Arturs Backurs and
Avrim Blum and
Neha Gupta},
editor = {Jacob D. Abernethy and
Shivani Agarwal},
title = {Active Local Learning},
booktitle = {Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual
Event [Graz, Austria]},
series = {Proceedings of Machine Learning Research},
volume = {125},
pages = {363--390},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v125/backurs20a.html},
timestamp = {Fri, 27 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/BackursBG20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/BackursDIRW20,
author = {Arturs Backurs and
Yihe Dong and
Piotr Indyk and
Ilya P. Razenshteyn and
Tal Wagner},
title = {Scalable Nearest Neighbor Search for Optimal Transport},
booktitle = {Proceedings of the 37th International Conference on Machine Learning,
{ICML} 2020, 13-18 July 2020, Virtual Event},
series = {Proceedings of Machine Learning Research},
volume = {119},
pages = {497--506},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v119/backurs20a.html},
timestamp = {Tue, 15 Dec 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/icml/BackursDIRW20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/AbboudBBK20,
author = {Amir Abboud and
Arturs Backurs and
Karl Bringmann and
Marvin K{\"{u}}nnemann},
editor = {Hugo Larochelle and
Marc'Aurelio Ranzato and
Raia Hadsell and
Maria{-}Florina Balcan and
Hsuan{-}Tien Lin},
title = {Impossibility Results for Grammar-Compressed Linear Algebra},
booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference
on Neural Information Processing Systems 2020, NeurIPS 2020, December
6-12, 2020, virtual},
year = {2020},
url = {https://proceedings.neurips.cc/paper/2020/hash/645e6bfdd05d1a69c5e47b20f0a91d46-Abstract.html},
timestamp = {Tue, 19 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/AbboudBBK20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/swat/BackursH20,
author = {Arturs Backurs and
Sariel Har{-}Peled},
editor = {Susanne Albers},
title = {Submodular Clustering in Low Dimensions},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory, {SWAT}
2020, June 22-24, 2020, T{\'{o}}rshavn, Faroe Islands},
series = {LIPIcs},
volume = {162},
pages = {8:1--8:14},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2020},
url = {https://doi.org/10.4230/LIPIcs.SWAT.2020.8},
doi = {10.4230/LIPICS.SWAT.2020.8},
timestamp = {Fri, 12 Jun 2020 14:09:17 +0200},
biburl = {https://dblp.org/rec/conf/swat/BackursH20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2004-05494,
author = {Arturs Backurs and
Sariel Har{-}Peled},
title = {Submodular Clustering in Low Dimensions},
journal = {CoRR},
volume = {abs/2004.05494},
year = {2020},
url = {https://arxiv.org/abs/2004.05494},
eprinttype = {arXiv},
eprint = {2004.05494},
timestamp = {Tue, 14 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2004-05494.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2008-10577,
author = {Kyriakos Axiotis and
Arturs Backurs and
Karl Bringmann and
Ce Jin and
Vasileios Nakos and
Christos Tzamos and
Hongxun Wu},
title = {Fast and Simple Modular Subset Sum},
journal = {CoRR},
volume = {abs/2008.10577},
year = {2020},
url = {https://arxiv.org/abs/2008.10577},
eprinttype = {arXiv},
eprint = {2008.10577},
timestamp = {Wed, 19 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2008-10577.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2008-13374,
author = {Arturs Backurs and
Avrim Blum and
Neha Gupta},
title = {Active Local Learning},
journal = {CoRR},
volume = {abs/2008.13374},
year = {2020},
url = {https://arxiv.org/abs/2008.13374},
eprinttype = {arXiv},
eprint = {2008.13374},
timestamp = {Wed, 16 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2008-13374.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2010-14181,
author = {Amir Abboud and
Arturs Backurs and
Karl Bringmann and
Marvin K{\"{u}}nnemann},
title = {Impossibility Results for Grammar-Compressed Linear Algebra},
journal = {CoRR},
volume = {abs/2010.14181},
year = {2020},
url = {https://arxiv.org/abs/2010.14181},
eprinttype = {arXiv},
eprint = {2010.14181},
timestamp = {Mon, 02 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2010-14181.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/BackursIOSVW19,
author = {Arturs Backurs and
Piotr Indyk and
Krzysztof Onak and
Baruch Schieber and
Ali Vakilian and
Tal Wagner},
editor = {Kamalika Chaudhuri and
Ruslan Salakhutdinov},
title = {Scalable Fair Clustering},
booktitle = {Proceedings of the 36th International Conference on Machine Learning,
{ICML} 2019, 9-15 June 2019, Long Beach, California, {USA}},
series = {Proceedings of Machine Learning Research},
volume = {97},
pages = {405--413},
publisher = {{PMLR}},
year = {2019},
url = {http://proceedings.mlr.press/v97/backurs19a.html},
timestamp = {Tue, 11 Jun 2019 15:37:38 +0200},
biburl = {https://dblp.org/rec/conf/icml/BackursIOSVW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/BackursIW19,
author = {Arturs Backurs and
Piotr Indyk and
Tal Wagner},
editor = {Hanna M. Wallach and
Hugo Larochelle and
Alina Beygelzimer and
Florence d'Alch{\'{e}}{-}Buc and
Emily B. Fox and
Roman Garnett},
title = {Space and Time Efficient Kernel Density Estimation in High Dimensions},
booktitle = {Advances in Neural Information Processing Systems 32: Annual Conference
on Neural Information Processing Systems 2019, NeurIPS 2019, December
8-14, 2019, Vancouver, BC, Canada},
pages = {15773--15782},
year = {2019},
url = {https://proceedings.neurips.cc/paper/2019/hash/a2ce8f1706e52936dfad516c23904e3e-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/BackursIW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AxiotisBJTW19,
author = {Kyriakos Axiotis and
Arturs Backurs and
Ce Jin and
Christos Tzamos and
Hongxun Wu},
editor = {Timothy M. Chan},
title = {Fast Modular Subset Sum using Linear Sketching},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {58--69},
publisher = {{SIAM}},
year = {2019},
url = {https://doi.org/10.1137/1.9781611975482.4},
doi = {10.1137/1.9781611975482.4},
timestamp = {Wed, 19 Jul 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/AxiotisBJTW19.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1902-03519,
author = {Arturs Backurs and
Piotr Indyk and
Krzysztof Onak and
Baruch Schieber and
Ali Vakilian and
Tal Wagner},
title = {Scalable Fair Clustering},
journal = {CoRR},
volume = {abs/1902.03519},
year = {2019},
url = {http://arxiv.org/abs/1902.03519},
eprinttype = {arXiv},
eprint = {1902.03519},
timestamp = {Tue, 21 May 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1902-03519.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/ndltd/Backurs18,
author = {Arturs Backurs},
title = {Below {P} vs {NP:} fine-grained hardness for big data problems},
school = {Massachusetts Institute of Technology, Cambridge, {USA}},
year = {2018},
url = {https://hdl.handle.net/1721.1/120376},
timestamp = {Wed, 04 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/phd/ndltd/Backurs18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/BackursI18,
author = {Arturs Backurs and
Piotr Indyk},
title = {Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless
{SETH} is False)},
journal = {{SIAM} J. Comput.},
volume = {47},
number = {3},
pages = {1087--1097},
year = {2018},
url = {https://doi.org/10.1137/15M1053128},
doi = {10.1137/15M1053128},
timestamp = {Mon, 23 Jul 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/BackursI18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/AbboudBW18,
author = {Amir Abboud and
Arturs Backurs and
Virginia Vassilevska Williams},
title = {If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser},
journal = {{SIAM} J. Comput.},
volume = {47},
number = {6},
pages = {2527--2555},
year = {2018},
url = {https://doi.org/10.1137/16M1061771},
doi = {10.1137/16M1061771},
timestamp = {Fri, 05 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/AbboudBW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/talg/AbboudBHWZ18,
author = {Amir Abboud and
Arturs Backurs and
Thomas Dueholm Hansen and
Virginia Vassilevska Williams and
Or Zamir},
title = {Subtree Isomorphism Revisited},
journal = {{ACM} Trans. Algorithms},
volume = {14},
number = {3},
pages = {27:1--27:23},
year = {2018},
url = {https://doi.org/10.1145/3093239},
doi = {10.1145/3093239},
timestamp = {Wed, 21 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/talg/AbboudBHWZ18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BackursCIS18,
author = {Arturs Backurs and
Moses Charikar and
Piotr Indyk and
Paris Siminelakis},
editor = {Mikkel Thorup},
title = {Efficient Density Evaluation for Smooth Kernels},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {615--626},
publisher = {{IEEE} Computer Society},
year = {2018},
url = {https://doi.org/10.1109/FOCS.2018.00065},
doi = {10.1109/FOCS.2018.00065},
timestamp = {Sat, 30 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/BackursCIS18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BackursRSWW18,
author = {Arturs Backurs and
Liam Roditty and
Gilad Segal and
Virginia Vassilevska Williams and
Nicole Wein},
editor = {Ilias Diakonikolas and
David Kempe and
Monika Henzinger},
title = {Towards tight approximation bounds for graph diameter and eccentricities},
booktitle = {Proceedings of the 50th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2018, Los Angeles, CA, USA, June 25-29, 2018},
pages = {267--280},
publisher = {{ACM}},
year = {2018},
url = {https://doi.org/10.1145/3188745.3188950},
doi = {10.1145/3188745.3188950},
timestamp = {Wed, 21 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BackursRSWW18.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1803-00796,
author = {Amir Abboud and
Arturs Backurs and
Karl Bringmann and
Marvin K{\"{u}}nnemann},
title = {Fine-Grained Complexity of Analyzing Compressed Data: Quantifying
Improvements over Decompress-And-Solve},
journal = {CoRR},
volume = {abs/1803.00796},
year = {2018},
url = {http://arxiv.org/abs/1803.00796},
eprinttype = {arXiv},
eprint = {1803.00796},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1803-00796.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1807-04825,
author = {Kyriakos Axiotis and
Arturs Backurs and
Christos Tzamos},
title = {Fast Modular Subset Sum using Linear Sketching},
journal = {CoRR},
volume = {abs/1807.04825},
year = {2018},
url = {http://arxiv.org/abs/1807.04825},
eprinttype = {arXiv},
eprint = {1807.04825},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1807-04825.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1808-08494,
author = {Arturs Backurs and
Liam Roditty and
Gilad Segal and
Virginia Vassilevska Williams and
Nicole Wein},
title = {Towards Tight Approximation Bounds for Graph Diameter and Eccentricities},
journal = {CoRR},
volume = {abs/1808.08494},
year = {2018},
url = {http://arxiv.org/abs/1808.08494},
eprinttype = {arXiv},
eprint = {1808.08494},
timestamp = {Thu, 14 Oct 2021 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1808-08494.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbboudBBK17,
author = {Amir Abboud and
Arturs Backurs and
Karl Bringmann and
Marvin K{\"{u}}nnemann},
editor = {Chris Umans},
title = {Fine-Grained Complexity of Analyzing Compressed Data: Quantifying
Improvements over Decompress-and-Solve},
booktitle = {58th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2017, Berkeley, CA, USA, October 15-17, 2017},
pages = {192--203},
publisher = {{IEEE} Computer Society},
year = {2017},
url = {https://doi.org/10.1109/FOCS.2017.26},
doi = {10.1109/FOCS.2017.26},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbboudBBK17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icml/BackursT17,
author = {Arturs Backurs and
Christos Tzamos},
editor = {Doina Precup and
Yee Whye Teh},
title = {Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms},
booktitle = {Proceedings of the 34th International Conference on Machine Learning,
{ICML} 2017, Sydney, NSW, Australia, 6-11 August 2017},
series = {Proceedings of Machine Learning Research},
volume = {70},
pages = {311--321},
publisher = {{PMLR}},
year = {2017},
url = {http://proceedings.mlr.press/v70/backurs17a.html},
timestamp = {Wed, 29 May 2019 08:41:45 +0200},
biburl = {https://dblp.org/rec/conf/icml/BackursT17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/AbboudB17,
author = {Amir Abboud and
Arturs Backurs},
editor = {Christos H. Papadimitriou},
title = {Towards Hardness of Approximation for Polynomial Time Problems},
booktitle = {8th Innovations in Theoretical Computer Science Conference, {ITCS}
2017, January 9-11, 2017, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {67},
pages = {11:1--11:26},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2017},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2017.11},
doi = {10.4230/LIPICS.ITCS.2017.11},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/innovations/AbboudB17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/BackursIS17,
author = {Arturs Backurs and
Piotr Indyk and
Ludwig Schmidt},
editor = {Isabelle Guyon and
Ulrike von Luxburg and
Samy Bengio and
Hanna M. Wallach and
Rob Fergus and
S. V. N. Vishwanathan and
Roman Garnett},
title = {On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel
Methods and Neural Networks},
booktitle = {Advances in Neural Information Processing Systems 30: Annual Conference
on Neural Information Processing Systems 2017, December 4-9, 2017,
Long Beach, CA, {USA}},
pages = {4308--4318},
year = {2017},
url = {https://proceedings.neurips.cc/paper/2017/hash/635440afdfc39fe37995fed127d7df4f-Abstract.html},
timestamp = {Thu, 21 Jan 2021 13:58:27 +0100},
biburl = {https://dblp.org/rec/conf/nips/BackursIS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BackursIS17,
author = {Arturs Backurs and
Piotr Indyk and
Ludwig Schmidt},
editor = {Philip N. Klein},
title = {Better Approximations for Tree Sparsity in Nearly-Linear Time},
booktitle = {Proceedings of the Twenty-Eighth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2017, Barcelona, Spain, Hotel Porta Fira, January
16-19},
pages = {2215--2229},
publisher = {{SIAM}},
year = {2017},
url = {https://doi.org/10.1137/1.9781611974782.145},
doi = {10.1137/1.9781611974782.145},
timestamp = {Tue, 02 Feb 2021 17:07:33 +0100},
biburl = {https://dblp.org/rec/conf/soda/BackursIS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursIS17,
author = {Arturs Backurs and
Piotr Indyk and
Ludwig Schmidt},
title = {On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel
Methods and Neural Networks},
journal = {CoRR},
volume = {abs/1704.02958},
year = {2017},
url = {http://arxiv.org/abs/1704.02958},
eprinttype = {arXiv},
eprint = {1704.02958},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursIS17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/BackursS16,
author = {Arturs Backurs and
Anastasios Sidiropoulos},
editor = {Klaus Jansen and
Claire Mathieu and
Jos{\'{e}} D. P. Rolim and
Chris Umans},
title = {Constant-Distortion Embeddings of Hausdorff Metrics into Constant-Dimensional
l{\_}p Spaces},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms
and Techniques, {APPROX/RANDOM} 2016, September 7-9, 2016, Paris,
France},
series = {LIPIcs},
volume = {60},
pages = {1:1--1:15},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.1},
doi = {10.4230/LIPICS.APPROX-RANDOM.2016.1},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/BackursS16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/BackursI16,
author = {Arturs Backurs and
Piotr Indyk},
editor = {Irit Dinur},
title = {Which Regular Expression Patterns Are Hard to Match?},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {457--466},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.56},
doi = {10.1109/FOCS.2016.56},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/BackursI16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/BackursDT16,
author = {Arturs Backurs and
Nishanth Dikkala and
Christos Tzamos},
editor = {Ioannis Chatzigiannakis and
Michael Mitzenmacher and
Yuval Rabani and
Davide Sangiorgi},
title = {Tight Hardness Results for Maximum Weight Rectangles},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming,
{ICALP} 2016, July 11-15, 2016, Rome, Italy},
series = {LIPIcs},
volume = {55},
pages = {81:1--81:13},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2016},
url = {https://doi.org/10.4230/LIPIcs.ICALP.2016.81},
doi = {10.4230/LIPICS.ICALP.2016.81},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/icalp/BackursDT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/pods/BackursO16,
author = {Arturs Backurs and
Krzysztof Onak},
editor = {Tova Milo and
Wang{-}Chiew Tan},
title = {Fast Algorithms for Parsing Sequences of Parentheses with Few Errors},
booktitle = {Proceedings of the 35th {ACM} {SIGMOD-SIGACT-SIGAI} Symposium on Principles
of Database Systems, {PODS} 2016, San Francisco, CA, USA, June 26
- July 01, 2016},
pages = {477--488},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2902251.2902304},
doi = {10.1145/2902251.2902304},
timestamp = {Tue, 06 Nov 2018 16:58:02 +0100},
biburl = {https://dblp.org/rec/conf/pods/BackursO16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/BackursIRW16,
author = {Arturs Backurs and
Piotr Indyk and
Ilya P. Razenshteyn and
David P. Woodruff},
editor = {Robert Krauthgamer},
title = {Nearly-optimal bounds for sparse recovery in generic norms, with applications
to \emph{k}-median sketching},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {318--337},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch24},
doi = {10.1137/1.9781611974331.CH24},
timestamp = {Tue, 02 Feb 2021 17:07:56 +0100},
biburl = {https://dblp.org/rec/conf/soda/BackursIRW16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/AbboudBHWZ16,
author = {Amir Abboud and
Arturs Backurs and
Thomas Dueholm Hansen and
Virginia Vassilevska Williams and
Or Zamir},
editor = {Robert Krauthgamer},
title = {Subtree Isomorphism Revisited},
booktitle = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
pages = {1256--1271},
publisher = {{SIAM}},
year = {2016},
url = {https://doi.org/10.1137/1.9781611974331.ch88},
doi = {10.1137/1.9781611974331.CH88},
timestamp = {Tue, 02 Feb 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/soda/AbboudBHWZ16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursDT16,
author = {Arturs Backurs and
Nishanth Dikkala and
Christos Tzamos},
title = {Tight Hardness Results for Maximum Weight Rectangles},
journal = {CoRR},
volume = {abs/1602.05837},
year = {2016},
url = {http://arxiv.org/abs/1602.05837},
eprinttype = {arXiv},
eprint = {1602.05837},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursDT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursT16,
author = {Arturs Backurs and
Christos Tzamos},
title = {Improving Viterbi is Hard: Better Runtimes Imply Faster Clique Algorithms},
journal = {CoRR},
volume = {abs/1607.04229},
year = {2016},
url = {http://arxiv.org/abs/1607.04229},
eprinttype = {arXiv},
eprint = {1607.04229},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursT16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbboudBW15,
author = {Amir Abboud and
Arturs Backurs and
Virginia Vassilevska Williams},
editor = {Venkatesan Guruswami},
title = {Tight Hardness Results for {LCS} and Other Sequence Similarity Measures},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {59--78},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.14},
doi = {10.1109/FOCS.2015.14},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbboudBW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbboudBW15a,
author = {Amir Abboud and
Arturs Backurs and
Virginia Vassilevska Williams},
editor = {Venkatesan Guruswami},
title = {If the Current Clique Algorithms are Optimal, So is Valiant's Parser},
booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS}
2015, Berkeley, CA, USA, 17-20 October, 2015},
pages = {98--117},
publisher = {{IEEE} Computer Society},
year = {2015},
url = {https://doi.org/10.1109/FOCS.2015.16},
doi = {10.1109/FOCS.2015.16},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/AbboudBW15a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/BackursI15,
author = {Arturs Backurs and
Piotr Indyk},
editor = {Rocco A. Servedio and
Ronitt Rubinfeld},
title = {Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless
{SETH} is false)},
booktitle = {Proceedings of the Forty-Seventh Annual {ACM} on Symposium on Theory
of Computing, {STOC} 2015, Portland, OR, USA, June 14-17, 2015},
pages = {51--58},
publisher = {{ACM}},
year = {2015},
url = {https://doi.org/10.1145/2746539.2746612},
doi = {10.1145/2746539.2746612},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/BackursI15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AbboudBW15,
author = {Amir Abboud and
Arturs Backurs and
Virginia Vassilevska Williams},
title = {Quadratic-Time Hardness of {LCS} and other Sequence Similarity Measures},
journal = {CoRR},
volume = {abs/1501.07053},
year = {2015},
url = {http://arxiv.org/abs/1501.07053},
eprinttype = {arXiv},
eprint = {1501.07053},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AbboudBW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursIPRW15,
author = {Arturs Backurs and
Piotr Indyk and
Eric Price and
Ilya P. Razenshteyn and
David P. Woodruff},
title = {Nearly-optimal bounds for sparse recovery in generic norms, with applications
to {\textdollar}k{\textdollar}-median sketching},
journal = {CoRR},
volume = {abs/1504.01076},
year = {2015},
url = {http://arxiv.org/abs/1504.01076},
eprinttype = {arXiv},
eprint = {1504.01076},
timestamp = {Fri, 22 Apr 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursIPRW15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AbboudBW15a,
author = {Amir Abboud and
Arturs Backurs and
Virginia Vassilevska Williams},
title = {If the Current Clique Algorithms are Optimal, so is Valiant's Parser},
journal = {CoRR},
volume = {abs/1504.01431},
year = {2015},
url = {http://arxiv.org/abs/1504.01431},
eprinttype = {arXiv},
eprint = {1504.01431},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AbboudBW15a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/AbboudBHWZ15,
author = {Amir Abboud and
Arturs Backurs and
Thomas Dueholm Hansen and
Virginia Vassilevska Williams and
Or Zamir},
title = {Subtree Isomorphism Revisited},
journal = {CoRR},
volume = {abs/1510.04622},
year = {2015},
url = {http://arxiv.org/abs/1510.04622},
eprinttype = {arXiv},
eprint = {1510.04622},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/AbboudBHWZ15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursI15,
author = {Arturs Backurs and
Piotr Indyk},
title = {Which Regular Expression Patterns are Hard to Match?},
journal = {CoRR},
volume = {abs/1511.07070},
year = {2015},
url = {http://arxiv.org/abs/1511.07070},
eprinttype = {arXiv},
eprint = {1511.07070},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursI15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/coco/BackursB14,
author = {Arturs Backurs and
Mohammad Bavarian},
title = {On the Sum of {L1} Influences},
booktitle = {{IEEE} 29th Conference on Computational Complexity, {CCC} 2014, Vancouver,
BC, Canada, June 11-13, 2014},
pages = {132--143},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/CCC.2014.21},
doi = {10.1109/CCC.2014.21},
timestamp = {Fri, 24 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/coco/BackursB14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/compgeom/BackursI14,
author = {Arturs Backurs and
Piotr Indyk},
editor = {Siu{-}Wing Cheng and
Olivier Devillers},
title = {Better embeddings for planar Earth-Mover Distance over sparse sets},
booktitle = {30th Annual Symposium on Computational Geometry, SoCG'14, Kyoto, Japan,
June 08 - 11, 2014},
pages = {280},
publisher = {{ACM}},
year = {2014},
url = {https://doi.org/10.1145/2582112.2582120},
doi = {10.1145/2582112.2582120},
timestamp = {Mon, 14 Jun 2021 16:39:30 +0200},
biburl = {https://dblp.org/rec/conf/compgeom/BackursI14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/BackursI14,
author = {Arturs Backurs and
Piotr Indyk},
title = {Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless
{SETH} is false)},
journal = {CoRR},
volume = {abs/1412.0348},
year = {2014},
url = {http://arxiv.org/abs/1412.0348},
eprinttype = {arXiv},
eprint = {1412.0348},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/BackursI14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/sofsem/AmbainisBBSSV13,
author = {Andris Ambainis and
Arturs Backurs and
Kaspars Balodis and
Agnis Skuskovniks and
Juris Smotrovs and
Madars Virza},
editor = {Peter van Emde Boas and
Frans C. A. Groen and
Giuseppe F. Italiano and
Jerzy R. Nawrocki and
Harald Sack},
title = {Worst Case Analysis of Non-local Games},
booktitle = {{SOFSEM} 2013: Theory and Practice of Computer Science, 39th International
Conference on Current Trends in Theory and Practice of Computer Science,
{\v{S}}pindler{\r{u}}v Ml{\'{y}}n, Czech Republic, January 26-31,
2013. Proceedings},
series = {Lecture Notes in Computer Science},
volume = {7741},
pages = {121--132},
publisher = {Springer},
year = {2013},
url = {https://doi.org/10.1007/978-3-642-35843-2\_12},
doi = {10.1007/978-3-642-35843-2\_12},
timestamp = {Mon, 28 Aug 2023 21:17:48 +0200},
biburl = {https://dblp.org/rec/conf/sofsem/AmbainisBBSSV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stacs/AmbainisBSW13,
author = {Andris Ambainis and
Arturs Backurs and
Juris Smotrovs and
Ronald de Wolf},
editor = {Natacha Portier and
Thomas Wilke},
title = {Optimal quantum query bounds for almost all Boolean functions},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science,
{STACS} 2013, February 27 - March 2, 2013, Kiel, Germany},
series = {LIPIcs},
volume = {20},
pages = {446--453},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2013},
url = {https://doi.org/10.4230/LIPIcs.STACS.2013.446},
doi = {10.4230/LIPICS.STACS.2013.446},
timestamp = {Tue, 11 Feb 2020 15:52:14 +0100},
biburl = {https://dblp.org/rec/conf/stacs/AmbainisBSW13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1302-4625,
author = {Arturs Backurs and
Mohammad Bavarian},
title = {On the sum of {\textdollar}L1{\textdollar} influences},
journal = {CoRR},
volume = {abs/1302.4625},
year = {2013},
url = {http://arxiv.org/abs/1302.4625},
eprinttype = {arXiv},
eprint = {1302.4625},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1302-4625.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BackursB13,
author = {Arturs Backurs and
Mohammad Bavarian},
title = {On the sum of {L1} influences},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-039}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/039},
eprinttype = {ECCC},
eprint = {TR13-039},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BackursB13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/icalp/AmbainisBBKOSV12,
author = {Andris Ambainis and
Arturs Backurs and
Kaspars Balodis and
Dmitrijs Kravcenko and
Raitis Ozols and
Juris Smotrovs and
Madars Virza},
editor = {Artur Czumaj and
Kurt Mehlhorn and
Andrew M. Pitts and
Roger Wattenhofer},
title = {Quantum Strategies Are Better Than Classical in Almost Any {XOR} Game},
booktitle = {Automata, Languages, and Programming - 39th International Colloquium,
{ICALP} 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part {I}},
series = {Lecture Notes in Computer Science},
volume = {7391},
pages = {25--37},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-31594-7\_3},
doi = {10.1007/978-3-642-31594-7\_3},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/icalp/AmbainisBBKOSV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/memics/AmbainisBNR12,
author = {Andris Ambainis and
Arturs Backurs and
Nikolajs Nahimovs and
Alexander Rivosh},
editor = {Anton{\'{\i}}n Kucera and
Thomas A. Henzinger and
Jaroslav Nesetril and
Tom{\'{a}}s Vojnar and
David Antos},
title = {Grover's Algorithm with Errors},
booktitle = {Mathematical and Engineering Methods in Computer Science, 8th International
Doctoral Workshop, {MEMICS} 2012, Znojmo, Czech Republic, October
25-28, 2012, Revised Selected Papers},
series = {Lecture Notes in Computer Science},
volume = {7721},
pages = {180--189},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-36046-6\_17},
doi = {10.1007/978-3-642-36046-6\_17},
timestamp = {Fri, 30 Aug 2019 10:02:27 +0200},
biburl = {https://dblp.org/rec/conf/memics/AmbainisBNR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tqc/AmbainisBNOR12,
author = {Andris Ambainis and
Arturs Backurs and
Nikolajs Nahimovs and
Raitis Ozols and
Alexander Rivosh},
editor = {Kazuo Iwama and
Yasuhito Kawano and
Mio Murao},
title = {Search by Quantum Walks on Two-Dimensional Grid without Amplitude
Amplification},
booktitle = {Theory of Quantum Computation, Communication, and Cryptography, 7th
Conference, {TQC} 2012, Tokyo, Japan, May 17-19, 2012, Revised Selected
Papers},
series = {Lecture Notes in Computer Science},
volume = {7582},
pages = {87--97},
publisher = {Springer},
year = {2012},
url = {https://doi.org/10.1007/978-3-642-35656-8\_7},
doi = {10.1007/978-3-642-35656-8\_7},
timestamp = {Tue, 14 May 2019 10:00:55 +0200},
biburl = {https://dblp.org/rec/conf/tqc/AmbainisBNOR12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-3330,
author = {Andris Ambainis and
Arturs Backurs and
Kaspars Balodis and
Dmitry Kravchenko and
Raitis Ozols and
Juris Smotrovs and
Madars Virza},
title = {Quantum strategies are better than classical in almost any {XOR} game},
journal = {CoRR},
volume = {abs/1112.3330},
year = {2011},
url = {http://arxiv.org/abs/1112.3330},
eprinttype = {arXiv},
eprint = {1112.3330},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-3330.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-3337,
author = {Andris Ambainis and
Arturs Backurs and
Nikolajs Nahimovs and
Raitis Ozols and
Alexander Rivosh},
title = {Search by quantum walks on two-dimensional grid without amplitude
amplification},
journal = {CoRR},
volume = {abs/1112.3337},
year = {2011},
url = {http://arxiv.org/abs/1112.3337},
eprinttype = {arXiv},
eprint = {1112.3337},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-3337.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-07 22:29 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
