# 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]