• Home
• Research
• Teaching
• Links

I work on developing efficient algorithms for mathematical problems, from both a complexity-theoretic and a practical standpoint. Much of my work has been on novel and effective uses of randomization in order to improve the running time, space, or communication cost of algorithms. Much of my work has focused on computations with polynomials, and sparse polynomials in particular. I also do some work in applied cryptography, namely secure cloud computing and enhanced privacy on mobile devices.

Publications

—, Adam J. Aviv, Seung Geol Choi, and Travis Mayberry.
Deterministic, Stash-Free, Write-Only ORAM (arXiv, ePrint, doi:10.1145/3133956.3134051).
ACM SIGSAC Conference on Computer and Communications Security (CCS), Dallas, Texas, USA, October 2017.
Implementation on github.

Adam J. Aviv, Seung Geol Choi, Travis Mayberry, and —.
ObliviSync: Practical Oblivious File Backup and Synchronization (arXiv, ePrint, doi:10.14722/ndss.2017.23188).
Network and Distributed System Security Symposium (NDSS) 2017. San Diego, California, USA, January 2017.

—, Daniel Apon, Seung Geol Choi, and Arkady Yerikhimovich.
POPE: Partial Order Preserving Encoding (arXiv, ePrint, doi:10.1145/2976749.2978345).
ACM SIGSAC Conference on Computer and Communications Security (CCS). Vienna, Austria, October 2016.
Slides from CCS'16 talk.

Andrew Arnold, Mark Giesbrecht, and —.
Faster Sparse Multivariate Polynomial Interpolation of Straight-Line Programs (arXiv, doi:10.1016/j.jsc.2015.11.005).
Journal of Symbolic Computation, July-August 2016.

—, Adam J. Aviv, and Seung Geol Choi.
A Practical Oblivious Map Data Structure with Secure Deletion and History Independence (ePrint, arXiv, doi:10.1109/SP.2016.19).
IEEE Symposium on Security and Privacy (S&P). San Jose, California, USA, May 2016.

Mohamed Khochtali, —, and Xisen Tian.
Parallel sparse interpolation using small primes (arXiv, doi:10.1145/2790282.2790290).
Parallel Symbolic Computation (PASCO) 2015.
Bath, UK, July 2015.
Slides from PASCO'15 talk.

Andrew Arnold and —.
Output-sensitive algorithms for sumset and sparse polynomial multiplication (arXiv, doi:10.1145/2755996.2756653).
International Symposium on Symbolic and Algebraic Computation (ISSAC) 2015.
Slides from ISSAC'15 talk.

Andrew Arnold and —.
Multivariate sparse interpolation using randomized Kronecker substitutions (arXiv, doi:10.1145/2608628.2608674).
International Symposium on Symbolic and Algebraic Computation (ISSAC) 2014.
Kobe, Japan, July 21-25, 2014.
Slides from ISSAC 14 talk.

Andrew Arnold, Mark Giesbrecht, and —.
Faster sparse polynomial interpolation of straight-line programs over finite fields (arXiv, doi:10.1145/2608628.2608671).
International Symposium on Symbolic and Algebraic Computation (ISSAC) 2014.
Kobe, Japan, July 21-25, 2014.

Andrew Arnold, Mark Giesbrecht, and —.
Faster sparse polynomial interpolation of straight-line programs (arXiv, doi:10.1007/978-3-319-02297-0_5).
Computer Algebra in Scientific Computing (CASC) 2013.
Berlin, Germany, September 9-13, 2013.

Mark Giesbrecht, —, and Hrushikesh Tilak.
Computing Sparse Multiples of Polynomials (arXiv, doi:10.1007/s00453-012-9652-4).
Algorithmica, Special Issue on Algorithms and Computation, November 2012.

Mark Giesbrecht and —. Detecting lacunary perfect powers and computing their roots (arXiv, doi:10.1016/j.jsc.2011.08.006).
Journal of Symbolic Computation, November 2011.

—. Chunky and Equal-Spaced Polynomial Multiplication (arXiv, doi:10.1016/j.jsc.2010.08.013).
Journal of Symbolic Computation, Special Issue in Honour of Keith Geddes on his 60th Birthday, July 2011.

Mark Giesbrecht and —. Diversification improves interpolation (arXiv, doi:10.1145/1993886.1993909).
International Symposium on Symbolic and Algebraic Computation (ISSAC) 2011.
San Jose, California, USA, June 8-11, 2011.
Implementation and abstract.

—. Efficient Computation with Sparse and Dense Polynomials (UW Space).
Ph.D. thesis, April 2011.
Abstract and individual chapters.

Mark Giesbrecht, —, and Hrushikesh Tilak.
Computing Sparse Multiples of Polynomials, extended abstract (PDF, doi:10.1007/978-3-642-17517-6_25).
International Symposium on Algorithms and Computation (ISAAC) 2010.
Jeju Island, Korea, December 15-17, 2010.
Presentation (PDF).

David Harvey and —. An in-place truncated Fourier transform and applications to polynomial multiplication (arXiv, doi:10.1145/1837934.1837996).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2010.
Munich, Germany, July 25-28, 2010.

Mark Giesbrecht and —. Interpolation of Shifted-Lacunary Polynomials (arXiv, doi:10.1007/s00037-010-0294-0).
Computational Complexity, 2010.

—. Space- and Time-Efficient Polynomial Multiplication (PDF, doi:10.1145/1576702.1576743).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2009.
Seoul, Korea, July 28-31, 2009.
Implementation (gzipped tar).
Presentation (PDF).

Mark Giesbrecht and —. On Lacunary Polynomial Perfect Powers (PDF, doi:10.1145/1390768.1390785).
International Symposium on Symbolic and Algebraic Computaion (ISSAC) 2008.
Hagenberg, Austria, July 20-23, 2008.
Implementation (gzipped tar) - requires GMP and NTL.
Presentation (PDF).

—. Adaptive Polynomial Multiplication (PDF).
Milestones in Computer Algebra (MICA 2008).
Stonehaven Bay, Trinidad and Tobago, May 1-3, 2008.

Mark Giesbrecht and —. Interpolation of Shifted-Lacunary Polynomials [Extended Abstract] (PDF).
Mathematical Aspects of Computer and Information Sciences (MACIS) 2007. Paris, France, December 5-7, 2007.
Presentation (PDF).

Seminars

A Better Write-Only Oblivious RAM (PDF).
CASYS Seminar, Laboratiore Jean Kuntzmann, Université Grenoble Alpes, September 21, 2017.

Pattern matching, X + Y, and Sparse Multiplication (PDF).
University of Notre Dame, October 8, 2015.

Between Sparse and Dense Arithmetic.
Symbolic Computation Seminar, NC State University, December 6, 2012.

Between Sparse and Dense Arithmetic (PDF).
NARC Seminar, USNA, November 28, 2012.

Finding a polynomial multiple that is sparse .
AMS Special Session on Mathematics of Computation: Algebra and Number Theory, JMM Boston, January 6, 2012.

Stable Sparse Interpolation with Fewer Samples (PDF).
Fields Institute Workshop on Hybrid Methodologies for Symbolic-Numeric Computation, Waterloo, Ontario, Canada, November 18, 2011.

Between Dense and Sparse Polynomial Multiplication (PDF).
Computer Science Colloquium, Drexel University, May 9, 2011.

Sparse interpolation and small primes in arithmetic progressions (PDF).
Number Theory Session, CMS Winter Meeting, Windsor, Ontario, Canada, December 5, 2009.

Fast and Small: Multiplying Polynomials without Extra Space (PDF).
CECM Summer Meeting, Vancouver, British Columbia, Canada, July 24, 2009.

Memory Efficiency in Polynomial Multiplicaion.
Session on High-Performance Computer Algebra, Applications of Computer Algebra (ACA), Montreal, Quebec, Canada, June 29, 2009.

Interpolation of Shifted-Lacunary Polynomials (PDF).
SIG Theory and Algorithms Seminar, University of Delaware, January 9, 2009.

Fast Multiplication with Low Space Complexity (PDF).
AMS Special Session on SAGE and Mathematical Research Using Open Source Software, JMM Washington, D.C., January 8, 2009.

The LinBox Project for Linear Algebra Computation: A Practical Tutorial (PDF).
MOCAA M³ workshop in computational algebra, University of Western Ontario, May 8, 2008.

Adaptive Polynomial Multiplication (PDF).
ORCCA Joint Lab Meeting, University of Western Ontario, March 14, 2008.

Complexity of Shifted-Lacunary Polynomial Interpolation (PDF).
SCG Seminar, School of Computer Science, University of Waterloo, December 13, 2007.

Matrix Input and Toeplitz Determinant: Undergraduate Research Projects with LinBox (PDF).
Symbolic Computation Group Lab Meeting, University of Waterloo, December 8, 2006.

Posters

Arithmetic for Sparse Integers and Floats (SVG, PDF).
with MIDN Mark Atkins, James Browning III, and Norman Overfield.
ECCAD 2014, Duke University, April 2016, 2014.

Faster Sparse Interpolation over Finite Fields and Complex Numbers (PDF).
with Mark Giesbrecht.
East Coast Computer Algebra Day (ECCAD 2011), University of Waterloo, April 9, 2011.

Detecting Polynomial Perfect Powers (PDF).
with Mark Giesbrecht. ORCCA Joint Lab Meeting. Maplesoft, Waterloo, ON, Canada, February 8, 2008.

New Algorithms for Lacunary Polynomials (PDF).
with Mark Giesbrecht. International Symposium on Symbolic and Algebraic Computation (ISSAC 2007). Waterloo, ON, Canada, July 29-August 1, 2007.

New Algorithms for Lacunary Polynomials (PDF).
with Mark Giesbrecht. CMS-MITACS Joint Conference 2007. Winnipeg, MB, Canada, May 31-June 1, 2007.