Pekka Orponen's Publications

Edited books

• T. Elomaa, H. Mannila, P. Orponen (Eds.): Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday. Springer-Verlag, Berlin, 2010.
• T. Erlebach, S. Nikoletseas, P. Orponen (Eds.): Proc. AlgoSensors 2011: 7th Intl. Symp. on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (Saarbrücken, Germany, September 2011). Springer-Verlag, Berlin, 2012.
• I. Kostitsyna, P. Orponen (Eds.): Proc. UCNC 2021: 19th Intl. Conf. on Unconventional Computation and Natural Computation (Espoo, Finland, October 2021). Springer Nature, Cham, 2021.

  Journal articles and book chapters

• P. Orponen, U. Schöning: The density and complexity of polynomial cores for intractable sets. Information and Control 70 (1986), 54-68.
• P. Orponen: A classification of complexity core lattices. Theoret. Computer Science 47 (1986), 121-130.
• P. Orponen, D. Russo, U. Schöning: Optimal approximations and polynomially levelable sets. SIAM J. Computing 15 (1986), 399-408.
• D. Russo, P. Orponen: On P-subset structures. Math. Systems Theory 20 (1986), 129-136.
• R. Book, P. Orponen, D. Russo, O. Watanabe: Lowness properties of sets in the exponential-time hierarchy. SIAM J. Computing 17 (1988), 504-516.
• P. Floréen, P. Orponen: On the computational complexity of analyzing Hopfield nets. Complex Systems 3 (1989), 577-587.
• P. Orponen: Dempster's rule of combination is #P-complete. Artificial Intelligence 44 (1990), 245-253.
• P. Floréen, P. Myllymäki, P. Orponen, H. Tirri: Compiling object declarations into connectionist networks. AI Communications 3 (1990), 172-183.
• P. Floréen, P. Myllymäki, P. Orponen, H. Tirri: NEULA: a hybrid neural-symbolic expert system shell. Tietojenkäsittelytiede (journal of the Finnish Society for Computer Science) 3 (1992), 11-18.
• P. Floréen, P. Orponen: Attraction radii in binary Hopfield nets are hard to compute. Neural Computation 5 (1993), 812-821.
• P. Orponen, K. Ko, U. Schöning, O. Watanabe: Instance complexity. J. Assoc. Comput. Mach. 41 (1994), 96-121.
• P. Orponen: Computational complexity of neural networks: A survey. Nordic Journal of Computing 1 (1994), 94-110.
• P. Orponen: The computational power of discrete Hopfield nets with hidden units. Neural Computation 8 (1996), 403-415.
• R. Greiner, P. Orponen: Probably approximately optimal satisficing strategies. Artificial Intelligence 82 (1996), 21-44.
• H. Buhrman, P. Orponen: Random strings make hard instances. J. Comput. System Sciences 53 (1996), 261-266.
• P. Orponen: Computing with truly asynchronous threshold logic networks. Theoret. Computer Science 174 (1997), 123-136.
• P. Orponen: A survey of continuous-time computation theory. Advances in Algorithms, Languages, and Complexity (eds. D.-Z. Du, K.-I Ko), 209-224. Kluwer Academic Publishers, Dordrecht, 1997.
• W. Maass, P. Orponen: On the effect of analog noise in discrete-time analog computations. Neural Computation 10 (1998), 1071-1095.
• J. Sima, P. Orponen, T. Antti-Poika: On the computational complexity of binary and analog symmetric Hopfield nets. Neural Computation 12 (2000), 2965-2989.
• J. Sima, P. Orponen: Continuous-time symmetric Hopfield nets are computationally universal. Neural Computation 15 (2003), 693-733.
• J. Sima, P. Orponen: Exponential transients in continuous-time Liapunov systems. Theoret. Computer Science 306 (2003), 353-372.
• J. Sima, P. Orponen: General purpose computation with neural networks: a survey of complexity theoretic results. Neural Computation 15 (2003), 2727-2778.
• P. Floréen, P. Kaski, J. Kohonen, P. Orponen: Lifetime maximization for multicasting in energy-constrained wireless networks. IEEE J. on Selected Areas in Communications 23 (2005), 117-126.
• E. J. Griffiths, P. Orponen: Optimization, block designs and No Free Lunch theorems. Information Processing Letters 94 (2005), 55-61.
• S. Seitz, M. Alava, P. Orponen: Focused local search for random 3-satisfiability. J. Statistical Mechanics June 2005, P06006, 27 pp.
• P. Floréen, P. Kaski, J. Kohonen, P. Orponen: Exact and approximate balanced data gathering in energy-constrained sensor networks. Theoret. Computer Science 344 (2005), 30-46.
• M. Alava, J. Ardelius, E. Aurell, P. Kaski, S. Krishnamurthy, P. Orponen, S. Seitz: Circumspect descent prevails in solving random constraint satisfaction problems. Proceedings of the National Academy of Sciences (USA) 105 (2008), 15253-15257.
• H. Haanpää, A. Schumacher, P. Orponen: Distributed algorithms for lifetime maximization in sensor networks via min-max spanning subgraphs. Wireless Networks 16 (2010), 875-887.
• L. Ahlroth, A. Schumacher, P. Orponen: Online bin packing with delay and holding costs. Operations Research Letters 41 (2013), 1-6.
• L.-L. Wu, H.-J. Zhou, M. Alava, E. Aurell, P. Orponen: Witness of unsatisfiability for a random 3-satisfiability formula. Physical Review E 87 (2013), 052807.
• A. Bar-Noy, T. Erlebach, M. M. Halldórsson, S. Nikoletseas, P. Orponen (Eds.): Special Issue on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities. Theoretical Computer Science 553 (2014), 1-114.
• M. Göös, T. Lempiäinen, E. Czeizler, P. Orponen: Search methods for tile sets in patterned DNA self-assembly. Journal of Computer and System Sciences 80 (2014), 297-319.
• E. Benson, A. Mohammed, J. Gardell, S. Masich, E. Czeizler, P. Orponen, B. Högberg: DNA rendering of polyhedral meshes at the nanoscale. Nature 523 (2015), 441-444 (23 July 2015). DOI: 10.1038/nature14586.
• E. Czeizler, P. Orponen: Fault tolerant design and analysis of carbon nanotube circuits affixed on DNA origami tiles. IEEE Transactions on Nanotechnology 14 (2015), 817-877. DOI: 10.1109/tnano.2015.2455673.
• E. Benson, A. Mohammed, A. Bosco, A. I. Teixeira, P. Orponen, B. Högberg: Computer-aided production of scaffolded DNA nanostructures from flat sheet meshes. Angewandte Chemie International Edition 55 (2016), 8869-8872. DOI: 10.1002/anie.201602446.
• P. Orponen: Design methods for 3D wireframe DNA nanostructures. Natural Computing 17 (2018), 147-160. DOI: 10.1007/s11047-9647-9
• E. Benson, A. Mohammed, D. Rayneau-Kirkhope, A. Gådin, P. Orponen, B. Högberg: Effects of design choices on the stiffness of wireframe DNA origami structures. ACS Nano 12 (2018), 9291-9299. DOI: 10.1021/acsnano.8b04148
• I. T. Hoffecker, Y. Yang, G. Bernardinelli, P. Orponen, B. Högberg: A computational framework for DNA microscopy. Proceedings of the National Academy of Sciences 116 (2019), 19282-19287. DOI: https://doi.org/10.1073/pnas.1821178116
• Vo H. T., D. Korpela, P. Orponen: Cotranscriptional kinetic folding of RNA secondary structures including pseudoknots. Journal of Computational Biology 28 (2021), 892-908. DOI: 10.1089/cmb.2020.0606
• M. Saman Booy, A. Ilin, P. Orponen: RNA secondary structure prediction with convolutional neural networks. BMC Bioinformatics 23:58 (2022), 15 pp. DOI: 10.1186/s12859-021-04540-7
• A. Elonen, A. K. Natarajan, I. Kawamata, L. Oesinghaus, A. Mohammed, J. Seitsonen, Y. Suzuki, F. C. Simmel, A. Kuzyk, P. Orponen: Algorithmic design of 3D wireframe RNA polyhedra. ACS Nano 16 (2022), 16608-16616. DOI: 10.1021/acsnano.2c06035.
• S. El-Mahgary, E. Soisalon-Soininen, P. Orponen, P. Rönnholm, H. Hyyppä: OVI-3: A NoSQL visual query system supporting efficient anti-joins. Journal of Intelligent Information Systems 60 (2023), 777-801. DOI: 10.1007/s10844-022-00742-4
• A. Elonen, L. Wimbes, A. Mohammed, P. Orponen: DNAforge: a design tool for nucleic acid nanostructures. Nucleic Acids Research, gkae367 (Online 15 May 2024). DOI: 10.1093/nar/gkae367.

• Conference papers

• P. Orponen: Complexity classes of alternating machines with oracles. Proc. of the 10th Internat. Colloq. on Automata, Languages, and Programming (Barcelona, Spain, July 1983) , 573-584. Springer-Verlag, Berlin Heidelberg, 1983.
• P. Orponen, P. Floréen, P. Myllymäki, H. Tirri: A neural implementation of conceptual hierarchies with Bayesian reasoning. Proc. of the Internat. Joint Conf. on Neural Networks (San Diego CA, June 1990), Vol. I , 297-303. IEEE, New York NY, 1990.
• P. Myllymäki, P. Orponen: Programming the Harmonium. Proc. of the Internat. Joint Conf. on Neural Networks (Singapore, November 1991), Vol. I , 671-677. IEEE, New York NY, 1991.
• P. Myllymäki, P. Orponen, T. Silander: Integrating symbolic reasoning with neurally represented background knowledge. Proc. of the Finnish AI Conference (Espoo, Finland, June 1992), Vol. 2 , 231-240. Finnish AI Society, Helsinki, 1992.
• P. Orponen, F. Prost: Parallel programming on Hopfield nets. Proc. of the Finnish AI Conference (Vaasa, Finland, August 1996), 5-12. Finnish AI Society, Vaasa, 1996.
• P. Orponen, M. Matamala: Universal computation by finite two-dimensional coupled map lattices. Proc. Physics and Computation 1996 (Boston MA, November 1996) , 243-247. New England Complex Systems Institute, Cambridge, MA, 1996.
• W. Maass, P. Orponen: On the effect of analog noise in discrete-time analog computations. Proc. Neural Information Processing Systems 1996 (Denver CO, December 1996), 218-224. The MIT Press, Cambridge, MA, 1997.
• J. Sima, P. Orponen, T. Antti-Poika: Some afterthoughts on Hopfield networks. Proc. SOFSEM'99: 26th Seminar on Current Trends in Theory and Practice of Informatics (Milovy, Czech Republic, November 1999), 459-469. Springer-Verlag, Berlin, 1999.
• J. Sima, P. Orponen: A continuous-time Hopfield net simulation of discrete neural networks. Proc. NC'2000: Second International ICSC Symposium on Neural Computing (Berlin, May 2000), 36-42. International Computer Science Conventions, Wetaskiwin, Canada, 2000.
• P. Orponen: An overview of the computational power of recurrent neural networks. Proc. of the Finnish AI Conference (Espoo, Finland, August 2000), Vol. 3: "AI of Tomorrow", 89-96. Finnish AI Society, Vaasa, 2000.
• J. Sima, P. Orponen: Computing with continuous-time Liapunov systems. Proc. of the 33rd Annual ACM Symposium on Theory of Computing (Crete, July 2001), 722-731. Association for Computing Machinery, New York NY, 2001.
• J. Sima, P. Orponen: Exponential transients in continuous-time symmetric Hopfield nets. Proc. Artificial Neural Networks - ICANN 2001 (Vienna, August 2001), 806-813. Springer-Verlag, Berlin, 2001.
• T. Ronkainen, H. Oja, P. Orponen: Computation of the multivariate Oja median. Proc. ICORS 2001: International Conference on Robust Statistics (Stift Vorau, Austria, July 2001), 344-359. Springer-Verlag, Berlin, 2002.
• S. Seitz, P. Orponen: An efficient local search method for random 3-satisfiability. Proc. LICS'03 Workshop on Typical Case Complexity and Phase Transitions (Ottawa, Canada, June 2003). Electronic Notes in Discrete Mathematics Vol. 16. Elsevier, Amsterdam, 2003.
• P. Floréen, P. Kaski, J. Kohonen, P. Orponen: Multicast time maximization in energy constrained wireless networks. MobiCom 2003 Joint Workshop on Foundations on Mobile Computing (DIALM-POMC'03, San Diego CA, September 2003), 50-58. Association for Computing Machinery, New York NY, 2003.
• E. Falck, P. Floréen, P. Kaski, J. Kohonen, P. Orponen: Balanced data gathering in energy-constrained sensor networks. Proc. Algosensors 2004: First International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Turku, Finland, July 2004), 59-70. Springer-Verlag, Berlin, 2004.
• P. Orponen, S. E. Schaeffer: Local clustering of large graphs by approximate Fiedler vectors. Proc. 4th International Workshop on Efficient and Experimental Algorithms (Santorini, Greece, May 2005), 524-533. Springer-Verlag, Berlin, 2005.
• S. Seitz, M. Alava, P. Orponen: Threshold behaviour of WalkSAT and focused Metropolis search on random 3-satisfiability. Proc. 8th International Conference on Theory and Applications of Satisfiability Testing (St. Andrews, Scotland, June 2005), 475-481. Springer-Verlag, Berlin, 2005.
• A. Schumacher, H. Haanpää, S. E. Schaeffer, P. Orponen: Load balancing by distributed optimisation in ad hoc networks. Proc. MSN 2006: Second International Conference on Mobile Ad-hoc and Sensor Networks (Hong Kong, China, December 2006), 873-884. Springer-Verlag, Berlin, 2006.
• H. Haanpää, A. Schumacher, T. Thaler, P. Orponen: Distributed computation of maximum lifetime spanning subgraphs in sensor networks. Proc. MSN 2007: Third International Conference on Mobile Ad-hoc and Sensor Networks (Beijing, December 2007), 445-456. Springer-Verlag, Berlin, 2007.
• S. Prasad, A. Schumacher, H. Haanpää, P. Orponen: Balanced multipath source routing. Proc. ICOIN 2007: 21st International Conference on Information Networking (Estoril, Portugal, January 2007), 315-324. Springer-Verlag, Berlin, 2008.
• A. Schumacher, P. Orponen, T. Thaler, H. Haanpää: Lifetime maximisation in wireless sensor networks by distributed binary search. Proc. ESWN'08: Fifth European Conference on Wireless Sensor Networks (Bologna, Italy, January 2008), 237-252. Springer-Verlag, Berlin, 2008.
• M. Göös, P. Orponen: Synthesizing minimal tile sets for patterned DNA self-assembly. Proc. DNA16: 16h International Conference on DNA Computing and Molecular Programming (Hong Kong, June 2010), 71-82. Springer-Verlag, Berlin, 2011.
• E. Czeizler, T. Lempiäinen, P. Orponen: A design framework for carbon nanotube circuits affixed on DNA origami tiles. Proc. FNANO11: 8th Annual Conference on Foundations of Nanoscience (Snowbird UT, April 2011), 186-187. Poster.
• T. Lempiäinen, E. Czeizler, P. Orponen: Synthesizing small and reliable tile sets for patterned DNA self-assembly. Proc. DNA17: 17th International Conference on DNA Computing and Molecular Programming (Pasadena CA, September 2011), 145-159. Springer-Verlag, Berlin, 2011.
• L. Ahlroth, P. Orponen: Unordered constraint satisfaction games. Proc. MFCS 2012: 37th International Symposium on Mathematical Foundations of Computer Science (Bratislava, August 2012), 64-75. Springer-Verlag, Berlin, 2012.
• E. Czeizler, P. Orponen: Yield optimization strategies for DNA staged tile assembly systems. Proc. TPNC 2013: 2nd International Conference on the Theory and Practice of Natural Computing (Cáceres, Spain, December 2013), 31-44. Springer-Verlag, Berlin, 2013.
• A. Mohammed, P. Orponen, S. Pai: Algorithmic design of cotranscriptionally folding 2D RNA origami structures. Proc. UCNC 2018: 17th International Conference on Unconventional Computation and Natural Computation (Fontainebleau, France, June 2018), 159-172. Springer-Verlag, Berlin, 2018.
• V. Gautam, S. Long, P. Orponen: RuleDSD: A rule-based modelling and simulation tool for DNA strand displacement systems. Proc. BIOSTEC 2020: 13th International Joint Conference on Biomedical Engineering Systems and Technologies (Valletta, Malta, February 2020), Vol. 3, 158-167. SCITEPRESS, 2020.
• A. Elonen, A. Mohammed, P. Orponen: A general design method for scaffold-free DNA wireframe nanostructures. Proc. UCNC 2024: 21st International Conference on Unconventional Computation and Natural Computation (Pohang, Republic of Korea, June 2024), 178-189. Springer Berlin Heidelberg, 2024.
• M. Nowicka, V. K. Gautam, P. Orponen: Automated rendering of multi-stranded DNA complexes with pseudoknots. Proc. UCNC 2024: 21st International Conference on Unconventional Computation and Natural Computation (Pohang, Republic of Korea, June 2024), 190-202. Springer Berlin Heidelberg, 2024.
• A. Elonen, P. Orponen:. Designing 3D RNA origami nanostructures with a minimum number of kissing loops. Proc. DNA30: 30th International Conference on DNA Computing and Molecular Programming (Baltimore MD, September 2024), 4:1-4:12. Leibniz International Proceedings in Informatics, 2024.

  Technical reports

• P. Orponen: The Separation of NLIN from DLIN Does Not Relativize. Report C-1983-61, Univ. of Helsinki, Dept. of Computer Science. 5 pp.
• P. Orponen: The Structure of Polynomial Complexity Cores. Dissertation, Report A-1986-3, Univ. of Helsinki, Dept. of Computer Science. 80 pp.
• P. Orponen, H. Mannila: On Approximation Preserving Reductions: Complete Problems and Robust Measures. Report C-1987-28, Univ. of Helsinki, Dept. of Computer Science. 22 pp.
• P. Floréen, P. Orponen: Complexity Issues in Discrete Hopfield Networks. Report A-1994-4, Univ. of Helsinki, Dept. of Computer Science. 54 pp.
• P. Orponen: The Computational Power of Continuous Time Asymmetric Neural Networks. Manuscript (1999). 20 pp.
• P. Orponen, S. E. Schaeffer: Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks. Technical Report cond-mat/0406048, arXiv.org (June 2004). 10 pp.
• P. Orponen, S. E. Schaeffer, V. Avalos Gaytán: Locally Computable Approximations for Spectral Clustering and Absorption Times of Random Walks. Technical Report cs.DM/0810.4061, arXiv.org (Oct 2008). 21 pp.

  Educational material, popular papers, etc.

• P. Orponen: Laskennan teoria (Theory of Computation). Typeset lecture notes (in Finnish). Report D-338, Univ. of Helsinki, Dept. of Computer Science, Dec. 1993. 152 pp.
• P. Orponen: Laskentaongelmien yksittäistapausten vaativuudesta. Logiikka, matematiikka ja tietokone. Perusteet: Historiaa, filosofiaa ja sovelluksia (toim. C. Gefwert, P. Orponen, J. Seppänen), 144-152. Suomen tekoälyseuran julkaisuja, Symposiosarja No. 14. Hakapaino, Helsinki, 1996.
• P. Orponen: Matematiikka ja tietotekniikka. Arkhimedes 2/1997, 25-29.
• P. Koikkalainen, P. Orponen: Tietotekniikan perusteet (Introduction to Computing). Typeset lecture notes (in Finnish). Univ. of Jyväskylä, 4th Ed. April 2002. 152 pp.
• P. Orponen, J. Ernvall: Algoritmitekniikka (Algorithmics). Typeset lecture notes (in Finnish). Univ. of Jyväskylä, November 2000. 106 pp.
• P. Orponen: Mitä tietojenkäsittelyteoriaan kuuluu? Tietojenkäsittelytiede 19/2003, 15-28.
• P. Orponen: Tietotekniikkaa ennen tietokoneita - Alan Turing ja tietotekniikan kiehtovat alkuvaiheet. Tietoa 4/2003, 4-6.
• P. Orponen: Tietojenkäsittelyteorian perusteet (Introduction to Theoretical Computer Science). Typeset lecture notes (in Finnish). Helsinki Univ. of Technology, Lab. for Theoretical Computer Science, September 2005. 119 pp. Revised and abbreviated edition of lecture notes on "Theory of Computation" (1993).
• P. Orponen: Combinatorial Models and Stochastic Algorithms. Typeset lecture notes. Helsinki Univ. of Technology, Lab. for Theoretical Computer Science, April 2007. 136 pp.
• P. Orponen: "P = NP" -ongelma ja laskennan vaativuusteoria. Tietojenkäsittelytiede 26/2007, 54-67.
• P. Orponen: Generoivat funktiot (Generating Functions). Typeset lecture notes (in Finnish). Helsinki Univ. of Technology, Dept. of Information and Computer Science, December 2008. 73 pp.