Petteri Kaski

  • Aalto SCI Computer Science Konemiehentie 2

20012020

Research output per year

If you made any changes in Pure these will be visible here soon.

Research Output

2020

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Karppa, M., Kaski, P., Kohonen, J. & Ó Catháin, P., 1 Jan 2020, In : Algorithmica.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
2019

Algebraic methods in the congested clique

Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. & Suomela, J., 2019, In : DISTRIBUTED COMPUTING. 32, 6, p. 461-478 18 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access

An adaptive prefix-assignment technique for symmetry reduction

Junttila, T., Karppa, M., Kaski, P. & Kohonen, J., Jul 2019, In : JOURNAL OF SYMBOLIC COMPUTATION. 99, p. 21-49

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
24 Downloads (Pure)

Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

Björklund, A., Kaski, P. & Williams, R., 1 Oct 2019, In : Algorithmica. 81, 10, p. 4010-4028

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
39 Downloads (Pure)

Parameterized single-exponential time polynomial space algorithm for steiner tree

Fomin, F., Kaski, P., Lokshtanov, D., Panolan, F. & Saurabh, S., 2019, In : SIAM Journal on Discrete Mathematics. 33, 1, p. 327-345 19 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
94 Downloads (Pure)

Probabilistic tensors and opportunistic boolean matrix multiplication

Karppa, M. & Kaski, P., 1 Jan 2019, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 496-515 20 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
1 Citation (Scopus)
19 Downloads (Pure)

Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction

Björklund, A., Kaski, P. & Williams, R., 1 Jul 2019, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019. Chatzigiannakis, I., Baier, C., Leonardi, S. & Flocchini, P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-13 26. (Leibniz international proceedings in informatics; vol. 132).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
8 Downloads (Pure)

Tensor network complexity of multilinear maps

Austrin, P., Kaski, P. & Kubjas, K., 1 Jan 2019, 10th Innovations in Theoretical Computer Science, ITCS 2019. Blum, A. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-21 7. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 124).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
9 Downloads (Pure)
2018

A faster subquadratic algorithm for finding outlier correlations

Karppa, M., Kaski, P. & Kohonen, J., 1 Jul 2018, In : ACM Transactions on Algorithms. 14, 3, p. 1-26 31.

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

Counting Connected Subgraphs with Maximum-Degree-Aware Sieving

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2018, 29th International Symposium on Algorithms and Computation (ISAAC 2018). Hsu, W-L., Lee, D-T. & Liao, C-S. (eds.). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 1-12 17. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 123).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
7 Downloads (Pure)

Engineering a delegatable and error-Tolerant algorithm for counting small subgraphs

Kaski, P., 2018, 2018 Proceedings of the 20th Workshop on Algorithm Engineering and Experiments, ALENEX 2018. Vol. 2018-January. p. 184-198 15 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Engineering Motif Search for Large Motifs

Kaski, P., Lauri, J. & Muniyappa, S., 2018, 17th Symposium on Experimental Algorithms, SEA 2018. D'Angelo, G. (ed.). p. 1-19 28. (Leibniz International Proceedings in Informatics (LIPIcs); vol. 103).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
7 Downloads (Pure)

Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

Björklund, A., Kaski, P. & Williams, R., 1 Feb 2018, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-13 6. (Leibniz International Proceedings in Informatics ; vol. 89).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
1 Citation (Scopus)
78 Downloads (Pure)

On the number of connected sets in bounded degree graphs

Kangas, K., Kaski, P., Korhonen, J. H. & Koivisto, M., 1 Jan 2018, In : Electronic Journal of Combinatorics. 25, 4, p. 1-19 #P4.34.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
80 Downloads (Pure)

Sharper upper bounds for unbalanced uniquely decodable code pairs

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 1 Feb 2018, In : IEEE Transactions on Information Theory. 64, 2, p. 1368-1373 6 p., 7888502.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
1 Citation (Scopus)
8 Downloads (Pure)
2017

An adaptive prefix-assignment technique for symmetry reduction

Junttila, T., Karppa, M., Kaski, P. & Kohonen, J., 2017, Theory and Applications of Satisfiability Testing – SAT 2017 - 20th International Conference, Proceedings. p. 101-118 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 10491 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Counting thin subgraphs via packings faster than meet-in-the-middle time

Björklund, A., Kaski, P. & Kowalik, L., 1 Sep 2017, In : ACM Transactions on Algorithms. 13, 4, p. 1-26 48.

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Directed hamiltonicity and out-branchings via generalized laplacians

Björklund, A., Kaski, P. & Koutis, I., 1 Jul 2017, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-14 91. (Leibniz International Proceedings in Informatics ; vol. 80).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
8 Citations (Scopus)
29 Downloads (Pure)

Narrow sieves for parameterized paths and packings

Björklund, A., Husfeldt, T., Kaski, P. & Koivisto, M., 2017, In : JOURNAL OF COMPUTER AND SYSTEM SCIENCES. 87, p. 119–139

Research output: Contribution to journalArticleScientificpeer-review

30 Citations (Scopus)

The first Parameterized Algorithms and Computational Experiments challenge

Dell, H., Husfeldt, T., Jansen, B. M. P., Kaski, P., Komusiewicz, C. & Rosamond, F. A., 1 Feb 2017, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-9 30. (Leibniz international proceedings in informatics; vol. 63).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
22 Citations (Scopus)
98 Downloads (Pure)
2016

A faster subquadratic algorithm for finding outlier correlations

Karppa, M., Kaski, P. & Kohonen, J., 2016, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2016, Arlington, VA, USA, January 10-12, 2016. Krauthgamer, R. (ed.). ACM, Vol. 2. p. 1288-1305 18 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

17 Citations (Scopus)

Constrained Multilinear Detection and Generalized Graph Motifs

Björklund, A., Kaski, P. & Kowalik, Ł., 1 Feb 2016, In : Algorithmica. 74, 2, p. 947-967 21 p.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
File
24 Citations (Scopus)
104 Downloads (Pure)

Dense Subset Sum may be the hardest

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 1 Feb 2016, Leibniz International Proceedings in Informatics: LIPIcs. Ollinger, N. & Vollmer, H. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Vol. 47. p. 1-12 13

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
5 Citations (Scopus)
51 Downloads (Pure)

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time

Karppa, M., Kaski, P., Kohonen, J. & Ó Catháin, P., 22 Aug 2016, 24th Annual European Symposium on Algorithms: ESA 2016, August 22–24, 2016, Aarhus, Denmark. Sankowski, P. & Zaroliagis, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 1-17 17 p. 52. (Leibniz International Proceedings in Informatics; vol. 57).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Open Access
File
4 Citations (Scopus)
23 Downloads (Pure)

Fast möbius inversion in semimodular lattices and ER-labelable posets

Kaski, P., Kohonen, J. & Westerbäck, T., 19 Aug 2016, In : The Electronic Journal of Combinatorics. 23, 3, p. 1-13 P3.26.

Research output: Contribution to journalArticleScientificpeer-review

Open Access
1 Citation (Scopus)

Fast Zeta Transforms for Lattices with Few Irreducibles

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Nederlof, J. & Parviainen, P., Feb 2016, In : ACM Transactions on Algorithms. 12, 1, 19 p., 4.

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)

How proofs are prepared at camelot: [Extended Abstract]

Björklund, A. & Kaski, P., 25 Jul 2016, PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. ACM, Vol. 25-28-July-2016. p. 391-400 10 p.

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

Separating OR, SUM, and XOR circuits

Find, M., Göös, M., Järvisalo, M., Kaski, P., Koivisto, M. & Korhonen, J., 1 Aug 2016, In : JOURNAL OF COMPUTER AND SYSTEM SCIENCES. 82, 5, p. 793-801 9 p.

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 10 Aug 2016, Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory. IEEE, Vol. 2016-August. p. 335-339 5 p. 7541316

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)
2015

Algebraic methods in the congested clique

Censor-Hillel, K., Kaski, P., Korhonen, J. H., Lenzen, C., Paz, A. & Suomela, J., 2015, 34th Annual ACM Symposium on Principles of Distributed Computing (PODC), Donostia-San Sebastián, Spain, July 2015. ACM, p. 143-152

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

54 Citations (Scopus)

Engineering Motif Search for Large Graphs

Björklund, A., Kaski, P., Kowalik, L. & Lauri, J., 2015, Seventeenth Workshop on Algorithm Engineering and Experiments, ALENEX 2015, San Diego, CA, USA, January 5, 2015. Brandes, U. & Eppstein, D. (eds.). Philadelphia, PA: SIAM, p. 104-118

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

12 Citations (Scopus)

Enumeration of Steiner triple systems with subsystems,

Kaski, P., Östergård, P. R. J. & Popa, A., 2015, In : Mathematics of Computation. 84, p. 3051-3067

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Fast Subset Convolution

Kaski, P., 2015, Encyclopedia of Algorithms. Kao, M-Y. (ed.). Berlin Heidelberg, p. 1-5

Research output: Chapter in Book/Report/Conference proceedingChapterProfessional

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Fomin, F. V., Kaski, P., Lokshtanov, D., Panolan, F. & Saurabh, S., 2015, 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015, Kyoto, Japan, July 6-10, 2015. Springer-verlag Berlin, p. 494-505

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

8 Citations (Scopus)

Subset Sum in the Absence of Concentration

Austrin, P., Kaski, P., Koivisto, M. & Nederlof, J., 2015, 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany. Mayr, E. W. & Ollinger, N. (eds.). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p. 48-61

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

11 Citations (Scopus)
2014

Counting thin subgraphs via packings faster than meet-in-the-middle time

Björklund, A., Kaski, P. & Kowalik, L., 2014, ACM/SIAM Symposium on Discrete Algorithms, SODA 2014, January 5-7, Portland, Oregon, USA. Chekuri, C. (ed.). Philadelphia, p. 594-603

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

10 Citations (Scopus)

Fast monotone summation over disjoint sets

Kaski, P., Koivisto, M., Korhonen, J. H. & Sergeev, I. S., 2014, In : Information Processing Letters. 114, 5, p. 264-267

Research output: Contribution to journalArticleScientificpeer-review

Fast witness extraction using a decision oracle

Björklund, A., Kaski, P. & Kowalik, L., 2014, European symposium on algorithms, ESA 2014, Wroclaw, Poland, September 8-10, 2014. Schulz, A. S. & Wagner, D. (eds.). p. 149-160

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

11 Citations (Scopus)

On the number of connected sets in bounded degree graphs

Kangas, K., Kaski, P., Koivisto, M. & Korhonen, J. H., 2014, Graph-Theoretic Concepts in Computer Science, 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Kratsch, D. & Todinca, I. (eds.). p. 336-347

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

3 Citations (Scopus)

Switching in one-factorisations of complete graphs

Kaski, P., de Souza Medeiros, A., Östergård, P. R. J. & Wanless, I. M., 2014, In : The Electronic Journal of Combinatorics. 21, 1, p. 24

Research output: Contribution to journalArticleScientificpeer-review

6 Citations (Scopus)
2013

Counting closed trails

Björklund, A. & Kaski, P., 2013, In : Information Processing Letters. 113, 1-2, p. 1-3

Research output: Contribution to journalArticleScientificpeer-review

Exact exponential algorithms: Surprises in the face of intractability

Fomin, F. V. & Kaski, P., 2013, In : Communications of the ACM. 56, 3, p. 80-88

Research output: Contribution to journalReview ArticleScientificpeer-review

Probably optimal graph motifs

Björklund, A., Kaski, P. & Kowalik, L., 2013, 30th International Symposium on Theoretical Aspects of Computer Science, (STACS 2013), Kiel, 27 February 2013 - 2 March 2013. Portier, N. & Wilke, T. (eds.). Schloss Dagstuhl - Leibniz Center for Informatics, p. 20-31

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

24 Citations (Scopus)

Space-time tradeoffs for subset sum: An improved worst case algorithm

Austrin, P., Kaski, P., Koivisto, M. & Määttä, J., 2013, 40th International Colloquium on Automata, Languages and Programming, (ICALP 2013), Riga, 8 July 2013 - 12 July 2013. Fomin, F. V., Freivalds, R., Kwiatkowska, M. & Peleg, D. (eds.). Berlin, p. 45-56

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

13 Citations (Scopus)
2012

Algorithm Theory - SWAT 2012, 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012.Proceedings

Fomin, F. V. & Kaski, P., 2012, Berlin Heidelberg. 236 p.

Research output: Book/ReportAnthologyScientificpeer-review

Fast monotone summation over disjoint sets

Kaski, P., Koivisto, M. & Korhonen, J. H., 2012, IPEC Seventh International Symposium on Parameterized and Exact Computation (IPEC 2012) IPEC, Ljubljana, Slovenia, September 12-14, 2012. Thilikos, D. M. & Woeginger, G. J. (eds.). Berlin, p. 159-170

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

1 Citation (Scopus)

Fast zeta transforms for lattices with few irreducibles

Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M., Nederlof, J. & Parviainen, P., 2012, SODA The Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) SODA, (Kyoto, 17-19 January, 2012). Philadelphia: SIAM, p. 1436-1444

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

6 Citations (Scopus)

Finding efficient circuits for ensemble computation

Järvisalo, M., Kaski, P., Koivisto, M. & Korhonen, J. H., 2012, SAT Fifteenth International Conference on Theory and Applications of Satisfiability Testing (SAT 2012) SAT, Trento, Italy, June 17-20, 2012. Cimatti, A. & Sebastiani, R. (eds.). p. 369-382

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

Homomorphic hashing for sparse coefficient extraction

Kaski, P., Koivisto, M. & Nederlof, J., 2012, IPEC Seventh International Symposium on Parameterized and Exact Computation (IPEC 2012) IPEC, Ljubljana, Slovenia, September 12-14, 2012. Thilikos, D. M. & Woeginger, G. J. (eds.). Berlin, p. 147-158

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

9 Citations (Scopus)

Steiner triple systems satisfying the 4-vertex condition

Kaski, P., Khatirinejad, M. & Östergård, P. R. J., 2012, In : DESIGNS CODES AND CRYPTOGRAPHY. 62, 3, p. 323-330

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)