Arturs Backurs
Arturs Backurs
Email verificata su ttic.edu
Titolo
Citata da
Citata da
Anno
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
A Backurs, P Indyk
Proceedings of the forty-seventh annual ACM symposium on Theory of computing …, 2015
2522015
Tight hardness results for LCS and other sequence similarity measures
A Abboud, A Backurs, VV Williams
2015 IEEE 56th Annual Symposium on Foundations of Computer Science, 59-78, 2015
169*2015
If the current clique algorithms are optimal, so is Valiant's parser
A Abboud, A Backurs, VV Williams
SIAM Journal on Computing 47 (6), 2527-2555, 2018
622018
Which regular expression patterns are hard to match?
A Backurs, P Indyk
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
492016
Scalable fair clustering
A Backurs, P Indyk, K Onak, B Schieber, A Vakilian, T Wagner
arXiv preprint arXiv:1902.03519, 2019
382019
Towards tight approximation bounds for graph diameter and eccentricities
A Backurs, L Roditty, G Segal, VV Williams, N Wein
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018
322018
Subtree isomorphism revisited
A Abboud, A Backurs, TD Hansen, V Vassilevska Williams, O Zamir
ACM Transactions on Algorithms (TALG) 14 (3), 1-23, 2018
282018
Improving viterbi is hard: Better runtimes imply faster clique algorithms
A Backurs, C Tzamos
International Conference on Machine Learning, 311-321, 2017
262017
Tight hardness results for maximum weight rectangles
A Backurs, N Dikkala, C Tzamos
arXiv preprint arXiv:1602.05837, 2016
252016
Towards hardness of approximation for polynomial time problems
A Abboud, A Backurs
8th Innovations in Theoretical Computer Science Conference (ITCS 2017), 2017
232017
Search by quantum walks on two-dimensional grid without amplitude amplification
A Ambainis, A Bačkurs, N Nahimovs, R Ozols, A Rivosh
Conference on Quantum Computation, Communication, and Cryptography, 87-97, 2012
212012
Better approximations for tree sparsity in nearly-linear time
A Backurs, P Indyk, L Schmidt
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete …, 2017
202017
On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks
A Backurs, P Indyk, L Schmidt
Advances in Neural Information Processing Systems, 4308-4318, 2017
182017
Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve
A Abboud, A Backurs, K Bringmann, M Künnemann
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017
162017
Search by quantum walks on two-dimensional grid without amplitude amplification
A Ambainis, A Backurs, N Nahimovs, R Ozols, A Rivosh
arXiv preprint arXiv:1112.3337, 2011
132011
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
A Backurs, P Indyk, I Razenshteyn, DP Woodruffs
Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete …, 2016
112016
Quantum strategies are better than classical in almost any XOR game
A Ambainis, A Bačkurs, K Balodis, D Kravčenko, R Ozols, J Smotrovs, ...
International Colloquium on Automata, Languages, and Programming, 25-37, 2012
112012
Constant-distortion embeddings of hausdorff metrics into constant-dimensional l_p spaces
A Backurs, A Sidiropoulos
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2016
62016
On the sum of L1 influences
A Backurs, M Bavarian
2014 IEEE 29th Conference on Computational Complexity (CCC), 132-143, 2014
62014
Grover’s algorithm with errors
A Ambainis, A Bačkurs, N Nahimovs, A Rivosh
International Doctoral Workshop on Mathematical and Engineering Methods in …, 2012
62012
Il sistema al momento non può eseguire l'operazione. Riprova più tardi.
Articoli 1–20