# Publications

2016
Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. 2016. “Geometric median in nearly linear time.” In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Pp. 9–21. Publisher's Version
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. 2016. “Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.” In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, Pp. 1643–1649. Publisher's Version
Jakub Pachocki. 2016. “Graphs and Beyond: Faster Algorithms for High Dimensional Convex Optimization.” PhD thesis, Carnegie Mellon University.
Michael B. Cohen, Cameron Musco, and Jakub Pachocki. 2016. “Online Row Sampling.” In The 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016.
Alina Ene, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. 2016. “Routing under balance.” In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Pp. 598–611. Publisher's Version
2015
Michael Mitzenmacher, Jakub Pachocki, Richard Peng, Charalampos E. Tsourakakis, and Shen Chen Xu. 2015. “Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling.” In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 10-13, 2015, Pp. 815–824. Publisher's Version
2014
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub Pachocki, Richard Peng, Anup Rao, and Shen Chen Xu. 2014. “Solving SDD linear systems in nearly m sqrt(log n) time.” In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, Pp. 343–352. Publisher's Version
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. 2014. “On the String Consensus Problem and the Manhattan Sequence Consensus Problem.” In String Processing and Information Retrieval - 21st International Symposium, SPIRE 2014, Ouro Preto, Brazil, October 20-22, 2014. Proceedings, Pp. 244–255. Publisher's Version
2013
Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Wojciech Tyczynski, and Tomasz Walen. 2013. “A note on efficient computation of all Abelian periods in a string.” Inf. Process. Lett., 113, 3, Pp. 74–77. Publisher's Version
2012
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. 2012. “Efficient Counting of Square Substrings in a Tree.” In Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings, Pp. 207–216. Publisher's Version