Lars Engebretsen

Currently on a career break.

Lars Engebretsen most recently worked as a Principal Software Engineer at Google. He has more than ten years of management experience and four years of experience as a senior individual contributor. He has earned a PhD (teknologie doktor) with habilitation (docent) from the Royal Institute of Technology.

E-mail; vCard; PGP key.
Key fingerprint: 5B38 3EE4 20EA 06E6 F2BA 0078 EEC4 6F59 77BF 998D

Engineering Lead at Google

Lars Engebretsen joined Google as a Software Engineer in 2005 and gradually took on larger and increasingly complex leadership and management roles across different areas in the company. He decided to leave Google in 2025.

2021–2025: Infrastructure SRE
Operated in a strategic individual contributor role with a focus on improvements to Google's global compute ecosystem across the Borg, Google Compute Engine, and Hardware Platforms organizations.
2017–2021: Google Assistant
Managed an 80-person engineering organization with multiple engineering teams. Partnered with product management, program management and UX functions across three areas to drive launches of new Google Assistant offerings as well as improvements to existing Assistant features on phones and smart displays. Established collaborations with the Android and Google Workspace business areas.
2008–2017: Search Ads Quality
Launched multiple improvements to Google's Search Ads targeting system. Improved both reach and accuracy of Google's Broad Match product. Rearchitected keyword targeting into a machine learning system. Grew from tech-lead, to manager, and to manager of managers with a 40-person organization. Promoted to Senior Staff Engineer, and then to Principal Engineer.
2005–2008: Search Quality
Designed, implemented and launched multiple ranking, retrieval, and index selection changes. Launched multiple improvements to Google's Safe Search product. Grew into a tech-lead role. Promoted to Staff Software Engineer.

Researcher in Theoretical Computer Science

Lars Engebretsen earned his doctorate in 2000 under the supervision of Professor Viggo Kann at the Department for Computer Science, Royal Institute of Technology. He spent the academic year 2000–2001 with Professor Madhu Sudan at MIT’s Laboratory for Computer Science and then returned to a Research Associate position at his alma mater. In 2005, he left academia to pursue a career in industry.

Engebretsen’s research was in the area of algorithmic complexity of constraint satisfaction problems on finite domains, probabilistically checkable proof systems, and approximation algorithms for NP-hard combinatorial optimization problems.

Studying Language and Culture

In addition to his focus on Computer Science, Lars Engebretsen has taken an interest in Russian language and culture as well as in the history of Nordic languages. This earned him a Bachelor of Arts with Russian as major subject and Nordic languages as minor subject.

Employment

Academic Degrees

Granted Patents

  1. Lars Engebretsen. Method and apparatus for producing a signature for an object. United States Patent 7,523,081, April 2009.
  2. Lars Engebretsen. Query classification. United States Patent 8,560,539, October 2013.
  3. Lars Engebretsen, Jennifer J. Huang, and Puneet Chopra. Broad match control. United States Patent 10,789,259, September 2020.
  4. Lars Engebretsen and Ian Leader. Systems and methods of generating semantic traffic reports. United States Patent 9,953,055, April 2018.
  5. Moritz Franosch, Wojtek Skut, Bianca Milatinovici, Lars Engebretsen, Julia Lennerz, Nadine Gerspacher, Elias Lieberich, and Ádám Ritter. Methods and systems for providing potential search queries that may be targeted by one or more keywords. United States Patent 9,378,517, June 2016.
  6. Wojciech Skut and Lars Engebretsen. Selection and display of online content items United States Patent 8,868,570, October 2014.

Published Patent Applications

  1. John B. Batali, Robert F. Day, Lars Engebretsen, Hartmut Maennel, John W. Merrill, and Matthew S. Weaver. Enhanced detection of like resources. United States Patent Application 12/324,334.
  2. Lars Engebretsen, Jennifer J. Huang, and Thomas Hofmann. Using entities in content selection. United States Patent Application 14/361,671.

Peer-Reviewed Journal Articles

  1. Gunnar Andersson and Lars Engebretsen. Better approximation algorithms for set splitting and not-all-equal sat. Information Processing Letters, 65(6):305‒311, March 1998. doi:10.1016/S0020-0190(98)00021-0.
  2. Gunnar Andersson and Lars Engebretsen. Property testers for dense constraint satisfaction programs on finite domains. Random Structures and Algorithms, 21(1):14‒32, August 2002. doi:10.1002/rsa.10041.
  3. Gunnar Andersson, Lars Engebretsen, and Johan Håstad. A new way of using semi-definite programming with applications to linear equations mod p. Journal of Algorithms, 39(2):162‒204, May 2001. doi:10.1006/jagm.2000.1154.
  4. Lars Engebretsen. An explicit lower bound for TSP with distances one and two. Algorithmica, 35(4):301‒319, 2003. doi:10.1007/s00453-002-1001-6.
  5. Lars Engebretsen. The nonapproximability of non-Boolean predicates. SIAM Journal on Discrete Mathematics, 18(1):114‒129, 2004. doi:10.1137/S0895480100380458.
  6. Lars Engebretsen. Simplified tight analysis of Johnson’s algorithm. Information Processing Letters, 92(4):207‒210, November 2004. doi:10.1016/j.ipl.2004.08.001.
  7. Lars Engebretsen. Platform-independent code conversion within the C++ locale framework. Software: Practice and Experience, 36(15):1643‒1654, December 2006. doi:10.1002/spe.734.
  8. Lars Engebretsen. Bipartite multigraphs with expander-like properties. Discrete Applied Mathematics, 155(13):1667‒1677, July 2007. doi:10.1016/j.dam.2007.03.001.
  9. Lars Engebretsen and Venkatesan Guruswami. Is constraint satisfaction over two variables always easy? Random Structures and Algorithms, 25(2):150‒178, September 2004. doi:10.1002/rsa.20026.
  10. Lars Engebretsen and Jonas Holmerin. Towards optimal lower bounds for clique and chromatic number. Theoretical Computer Science, 299(1‒3):537‒584, 2003. doi:10.1016/S0304-3975(02)00535-2.
  11. Lars Engebretsen and Jonas Holmerin. Three-query PCPs with perfect completeness over non-Boolean domains. Random Structures and Algorithms, 27(1):46‒75, August 2005. doi:10.1002/rsa.20050.
  12. Lars Engebretsen and Jonas Holmerin. More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP. Random Structures and Algorithms, 33(4):497‒514, December 2008. doi:10.1002/rsa.20226.
  13. Lars Engebretsen, Jonas Holmerin, and Alexander Russell. Inapproximability results for equations over finite groups. Theoretical Computer Science, 312(1):17‒45, January 2004. doi:10.1016/S0304-3975(03)00401-8.
  14. Lars Engebretsen and Marek Karpinski. TSP with bounded metrics. Journal of Computer and System Sciences, 72(4):509‒546, June 2006. doi:10.1016/j.jcss.2005.12.001.
  15. Lars Engebretsen and Madhu Sudan. Harmonic broadcasting is bandwidth-optimal assuming constant bit-rate. Networks, 47(3):172‒177, May 2006. doi:10.1002/net.20105.

Books and Book Chapters

  1. Lars Engebretsen. Approximate Constraint Satisfaction. Doctoral dissertation, Department of Numerical Analysis and Computer Science, Royal Institute of Technology, April 2000. urn:nbn:se:kth:diva-2950.
  2. Lars Engebretsen. Electronic structure calculations of the elastic properties of alkali hydrides. Master’s thesis, School of Engineering Physics, Royal Institute of Technology, June 1995.
  3. Lars Engebretsen. Två brev från kriget mot Ryssland 1609‒1617. Bachelor’s thesis, Department of Slavonic Languages and Literature, Stockholm University, October 1999. In Swedish.
  4. Lars Engebretsen. Using easy optimization problems to solve hard ones. In Benedikt Löwe, Boris Piwinger, and Thoralf Räsch, editors, Classical and New Paradigms of Computation and their Complexity Hierarchies, pages 77‒93. Volume 23 of Trends in Logic, Kluwer Academic Publishers, Drodrecht, 2004. doi:10.1007/978-1-4020-2776-5_6.
  5. Lars Engebretsen, Fredrik Jönsson, Christian Olausson, and Andreas Skoog, editors. Manskören. Notfabriken, Danderyd, 2012. ISBN 978-91-86825-22-5. Sheet music.