Skip to main content

Publications of Alexander Tiskin

In the list of publications below, colour tags correspond to my main research topics: ST (string algorithms), PA (parallel computation), CO (combinatorial optimisation and graph theory).

Book draft

[ST, CO] A. Tiskin. Semi-local string comparison: Algorithmic techniques and applications. [arXiv]

Doctorate thesis

[PA, CO] A. Tiskin. The Design and Analysis of Bulk-Synchronous Parallel Algorithms. DPhil thesis. University of Oxford, 1999. [Local PS (double-sided)] [Local PS (single-sided)]

Book chapters

[PA] A. Tiskin. Bulk-synchronous parallelism (BSP). In Encyclopedia of Parallel Computing, Part 2, pp. 192—199. Springer, 2011. [DOI]

[PA] A. Tiskin. Bulk-synchronous parallelism: An emerging paradigm of high-performance computing. In L. T. Yang and M. Guo, eds., High Performance Computing: Paradigm and Infrastructure, pp. 69—80. John Wiley and Sons, 2005. [DOI]

Journal papers

[ST] A. Tiskin. Fast distance multiplication of unit-Monge matrices. Algorithmica, 71, 4, pp.859-888, 2015. [DOI (open access)]

[CO] V. G. Deineko, B. Klinz, A. Tiskin, and G. J. Woeginger. Four-point conditions for the TSP: The complete complexity classification. Discrete Optimization, 14, pp.147—159, 2014. [DOI]

[ST] S. Wandelt, Dong Deng, S. Gerdjikov, S. Mishra, P. Mitankin, M. Patil, E. Siragusa, A. Tiskin, W. Wang, Jiaying Wang, and U. Leser. State-of-the-art in String Similarity Search and Join. SIGMOD Record, 43, 1, pp.64—76, 2014. [Publisher’s HTML] [PDF]

[ST] L. Baxter, A. Jironkin, R. Hickman, J. Moore, C. Barrington, P. Krusche, N. P. Dyer, V. Buchanan-Wollaston, A. Tiskin, J. Beynon, K. Denby, and S. Ott. Conserved Noncoding Sequences Highlight Shared Components of Regulatory Networks in Dicotyledonous Plants. Plant Cell, 24, 10, pp.3949—3965, 2012. [DOI] [University’s press release]

[CO] N. Korpelainen, V. Lozin, D. S. Malyshev, and A. Tiskin. Boundary properties of graphs for algorithmic graph problems. Theoretical Computer Science, 412, 29, pp. 3545–3554, 2011. [DOI]

[ST] E. Picot, P. Krusche, A. Tiskin, I. Carré, and S. Ott. Evolutionary Analysis of Regulatory Sequences (EARS) in Plants. The Plant Journal, 164, 1, pp. 165—176, 2010. [DOI] [Software]

[CO] V. Deineko and A. Tiskin. Fast minimum-weight double-tree shortcutting for Metric TSP: Is the best one good enough? ACM Journal on Experimental Algorithmics, 14, Article 4.6, 2009. [arXiv] [DOI]

[ST] A. Tiskin. Faster subsequence recognition in compressed strings. Journal of Mathematical Sciences, 158, 5, pp. 759—769, 2009. [arXiv] [DOI] (Superseded by the book draft “Semi-local string comparison: Algorithmic techniques and applications”)

[ST] A. Tiskin. Semi-local longest common subsequences in subquadratic time. Journal of Discrete Algorithms, 6, 4, pp. 570—581, 2008. [Local PDF] [DOI] (Superseded by the book draft “Semi-local string comparison: Algorithmic techniques and applications”)

[ST] A. Tiskin. Semi-local string comparison: Algorithmic techniques and applications. Mathematics in Computer Science, 1, 4, pp. 571—603, 2008. [arXiv] [DOI] (Superseded by the book draft “Semi-local string comparison: Algorithmic techniques and applications”)

[PA] A. Tiskin. Communication-efficient parallel generic pairwise elimination. Future Generation Computer Systems, 23, 2, pp. 179—188, 2007. [Local PDF] [DOI]

[CO] A. Tiskin. Packing tripods: Narrowing the density gap. Discrete Mathematics, 307, 16, pp. 1973—1981, 2007. [Local PS] [DOI]

[PA] D. Irony, S. Toledo and A. Tiskin. Communication lower bounds for distributed-memory matrix multiplication. Journal of Parallel and Distributed Computing, 64, 9, pp. 1017—1026, 2004. [Local PS] [DOI]

[PA] A. V. Gerbessiotis, C. J. Siniolakis and A. Tiskin. Parallel priority queue and list contraction: The BSP approach. Computing and Informatics, 21, pp. 59—90, 2002. [Publisher’s HTML abstract]

[PA] A. Tiskin. Bulk-synchronous parallel Gaussian elimination. Journal of Mathematical Sciences, 108, 6, pp. 977—991, 2002. [DOI] (Superseded by “Communication-efficient parallel generic pairwise elimination”, see Journal papers])

[PA] A. Tiskin. A new way to divide and conquer. Parallel Processing Letters, 11, 4, pp. 409—422, 2001. [Local PS] [DOI]

[PA] W. F. McColl and A. Tiskin. Memory-efficient matrix computations in the BSP model. Algorithmica, 24, 3—4, pp. 287—297, 1999. [Local PS] [DOI]

[PA] A. Tiskin. The bulk-synchronous parallel random access machine. Theoretical Computer Science, 196, 1—2, pp. 109—130, 1998. [Local PS] [DOI]

A. N. Terekhov and A. V. Tiskin. Public-key cryptography: from theory to standard. Programming and Computer Software, 20, 5, pp. 189—192, 1994. (Translated from Russian.)

Conference papers

[ST] A. Tiskin. Threshold Approximate Matching in Grammar-Compressed Strings. In Proceedings of Prague Stringology Conference, pp. 124—138, 2014. [Publisher’s HTML+PDF]

[ST] M. Felice Pace and A. Tiskin. Parallel suffix array construction by accelerated sampling. In Proceedings of Prague Stringology Conference, pp. 142—156, 2013. [Publisher’s HTML+PDF]

[ST] A. Tiskin. Efficient high-similarity string comparison: The waterfall algorithm. In Proceedings of the Joint EDBT/ICDT Workshops, pp. 358—365, 2013. [DOI]

[ST] A. Tiskin. Towards approximate matching in compressed strings: Local subsequence recognition. In Proceedings of CSR, vol. 6651 of Lecture Notes in Computer Science, pp. 401—414, 2011. [DOI]

[ST, PA] P. Krusche and A. Tiskin. New algorithms for efficient parallel string comparison. In Proceedings of ACM SPAA, pp. 209—216, 2010. [DOI]

[PA] A. Tiskin. Parallel selection by regular sampling. In Proceedings of Euro-Par, Part II, vol. 6272 of Lecture Notes in Computer Science, pp. 393—399, 2010. [DOI]

[ST] A. Tiskin. Fast distance multiplication of unit-Monge matrices. In Proceedings of ACM-SIAM SODA, pp. 1287—1296, 2010. [Publisher’s HTML+PDF]

[CO] N. Korpelainen, V. Lozin and A. Tiskin. Hamiltonian cycles in subcubic graphs: What makes the problem difficult. In Proceedings of TAMC, vol. 6108 of Lecture Notes in Computer Science, pp. 320—327, 2010. [DOI]

[ST, PA] P. Krusche and A. Tiskin. Parallel longest increasing subsequences in scalable time and memory. In Proceedings of PPAM 2009, Revised Selected Papers, Part I, vol. 6067 of Lecture Notes in Computer Science, pp. 176—185, 2010. [DOI]

[ST, PA] P. Krusche and A. Tiskin. Computing alignment plots efficiently. In Proceedings of ParCo, 2009. Appeared in Parallel Computing: From Multicores and GPU’s to Petascale, vol. 19 of Advances in Parallel Computing series, IOS Press, pp. 158—165, 2010. [arXiv] [DOI]

[ST] A. Tiskin. Periodic string comparison. In Proceedings of CPM, vol. 5577 of Lecture Notes in Computer Science, pp. 193—206, 2009. [DOI]

[CO] V. Deineko and A. Tiskin. Minimum-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio. In Proceedings of DIMAP Workshop on Algorithmic Graph Theory, Electronic Notes in Discrete Mathematics, 32, pp. 19—26, 2009. [arXiv] [DOI]

[ST] P. Krusche and A. Tiskin. String comparison by transposition networks. In Proceedings of London Algorithmics Workshop, 2008. Appeared in London Algorithmics 2008: Theory and Practice, vol. 11 of Texts in Algorithmics, College Publications, pp. 184—204, 2009. [arXiv] [Publisher’s HTML]

[ST, PA] P. Krusche and A. Tiskin. Efficient parallel string comparison. In Proceedings of ParCo, 2007. Appeared in Parallel Computing: Architectures, Algorithms and Applications, vol. 15 of Advances in Parallel Computing series, IOS Press, pp. 193—200, 2008. [Publisher’s HTML+PDF] Also appeared in Parallel Computing: Architectures, Algorithms and Applications, vol. 38 of NIC Series, John von Neumann Institute for Computing, pp. 193—200, 2007. [Publisher’s HTML+PDF]

[CO] V. Deineko and A. Tiskin. Fast minimum-weight double-tree shortcutting for Metric TSP. In Proceedings of WEA, vol. 4525 of Lecture Notes in Computer Science, pp. 136—149, 2007. [Local PS] [DOI]

[ST, CO] A. Tiskin. Longest common subsequences in permutations and maximum cliques in circle graphs. In Proceedings of CPM, vol. 4009 of Lecture Notes in Computer Science, pp. 271—282, 2006. [Local PDF] [DOI] (Superseded by the book draft “Semi-local string comparison: Algorithmic techniques and applications”)

[ST] A. Tiskin. All semi-local longest common subsequences in subquadratic time. In Proceedings of CSR, vol. 3967 of Lecture Notes in Computer Science, pp. 352—363, 2006. [Local PDF] [DOI] (Superseded by the book draft “Semi-local string comparison: Algorithmic techniques and applications”)

[ST, PA] P. Krusche and A. Tiskin. Efficient longest common subsequence computation using bulk-synchronous parallelism. In Proceedings of ICCSA, vol. 3984 of Lecture Notes in Computer Science, pp. 165—174, 2006. [Local PDF] [DOI]

[CO] V. Deineko and A. Tiskin. One-sided Monge TSP is NP-hard. In Proceedings of ICCSA, vol. 3982 of Lecture Notes in Computer Science, pp. 793—801, 2006. [Local PDF] [DOI]

[ST, PA] A. Tiskin. Efficient representation and parallel computation of string-substring longest common subsequences. In Proceedings of ParCo, vol. 33 of NIC Series, John von Neumann Institute for Computing, pp. 827—834, 2005. [Local PDF] [Publisher’s HTML+PDF] (Superseded by conference paper “Efficient parallel string comparison”)

[PA] J. M. R. Martin and A. V. Tiskin. Dynamic BSP: Towards a flexible approach to parallel computing over the grid. In Communicating Process Architectures: Proceedings of WoTUG, pp. 219—226, 2004. [Local PS] [Publisher’s HTML+PDF]

[PA] A. Tiskin. Communication-efficient parallel Gaussian elimination. In Proceedings of PaCT, vol. 2763 of Lecture Notes in Computer Science, pp. 369—383, 2003. (Superseded by journal paper “Communication-efficient parallel generic pairwise elimination”)

[CO] A. Tiskin. Packing tripods: A computational approach. Extended abstract in Proceedings of Eurocomb, Charles University, pp. 353—357, 2003. (Superseded by journal paper “Packing tripods: Narrowing the density gap”)

[PA] A. Tiskin. Parallel convex hull computation by generalised regular sampling. In Proceedings of Euro-Par, vol. 2400 of Lecture Notes in Computer Science, pp. 392—399, 2002. [Local PS] [DOI]

[PA] A. Tiskin. All-pairs shortest paths computation in the BSP model. In Proceedings of ICALP, vol. 2076 of Lecture Notes in Computer Science, pp. 178—189, 2001. [DOI] (Superseded by work in progress “Synchronisation-efficient parallel all-pairs shortest paths computation”)

[PA] A. Tiskin. A new way to divide and conquer. In Proceedings of HLPP, pp. 74—82, 2001. (Superseded by journal paper “A new way to divide and conquer”)

[CO] A. Tiskin. Tripods do not pack densely. In Proceedings of COCOON, vol. 1858 of Lecture Notes in Computer Science, pp. 272—280, 2000. [DOI] (Superseded by “Packing tripods: Narrowing the density gap”, see Journal papers.)

[PA] J. M. R. Martin and A. V. Tiskin. BSP modelling of two-tiered parallel architectures. In Architectures, Languages and Techniques for Concurrent Systems: Proceedings of WoTUG, pp. 47—55, 1999. [Publisher’s HTML+PDF] (Superseded by “BSP algorithm design for hierarchical supercomputers”, see Work in progress.)

[PA] A. Tiskin. Bulk-synchronous parallel Gaussian elimination. In Representation Theory, Dynamical Systems, Combinatorial and Algorithmic Methods (Part 4), vol. 258 of Zapiski Nauchnykh Seminarov POMI, pp. 115—133, 1999. [Publisher’s HTML+PS] (Superseded by “Communication-efficient parallel generic pairwise elimination”, see Journal papers.)

[PA] A. Tiskin. Bulk-synchronous parallel multiplication of Boolean matrices. In Proceedings of ICALP, vol. 1443 of Lecture Notes in Computer Science, pp. 494—506, 1998. Corrigendum in Proceedings of ICALP, vol. 1644 of Lecture Notes in Computer Science, p. 717, 1999. (Superseded by a new version of “Bulk-synchronous parallel multiplication of Boolean matrices”, see Work in progress.)

[PA] A. V. Gerbessiotis, C. J. Siniolakis and A. Tiskin. Parallel priority queue and list contraction: The BSP approach. In Proceedings of Euro-Par, vol. 1300 of Lecture Notes in Computer Science, pp. 409—416, 1997. (Superseded by a new version of “Parallel priority queue and list contraction: The BSP approach”, see Journal papers.)

[PA] A. Tiskin. The bulk-synchronous parallel random access machine. In Proceedings of Euro-Par, part II, vol. 1124 of Lecture Notes in Computer Science, pp. 327—338, 1996. (Superseded by a new version of “The bulk-synchronous parallel random access machine”, see Journal papers.)

Survey presentations

[ST] A. Tiskin. A superglue for string comparison. Last updated February 2017. [PDF (presentation)] [PDF (handout)]

[PA] A. Tiskin. Efficient Parallel Algorithms: The BSP Approach. Last updated February 2017. [PDF (presentation)] [PDF (handout)]

Other talks

[CO] V. Deineko and A. Tiskin. Minimum-weight tree shortcutting for metric TSP. January 2008. [PDF (presentation)] [PDF (handout)]

[PA] J. M. R. Martin and A. V. Tiskin. Dynamic BSP: Towards a flexible approach to parallel computing over the grid. 2004. [HTML+PPT]

Short & tweet

[ST] A. Tiskin. Approximate string matching as an algebraic computation. Tweeted in Volume 1 of Tiny Transactions on Computer Science, 2012. [PDF] [Journal’s website]

Editorship

[PA] F. Loulergue and A. Tiskin, eds. High-Level Parallel Programming and Applications: Proceedings of HLPP 2005. Special issue of Parallel Processing Letters, 18, 1, 2008.

Work in progress

[PA, CO] A. Tiskin. Synchronisation-efficient parallel all-pairs shortest paths computation. [Local PS]

[PA] J. M. R. Martin and A. V. Tiskin. BSP algorithm design for hierarchical supercomputers. [Local PS]

[PA, CO] A. Tiskin. Bulk-synchronous parallel multiplication of Boolean matrices. [Local PS]