Igor L. Markov

In this name that follows East Slavic naming customs, the patronymic is Leonidovich and the family name is Markov.

Igor Leonidovich Markov^[a] (born in 1973) is an American professor,^[1] computer scientist and engineer. Markov is known for results in quantum computation, work on limits of computation, research on algorithms for optimizing integrated circuits and on electronic design automation, as well as artificial intelligence. Additionally, Markov is an American non-profit executive^[2] responsible for aid to Ukraine worth over a hundred million dollars.^[3][4][5]

Igor Leonidovich Markov
Ігор Леонідович Марков
Born	(1973-03-31) 31 March 1973 (age 52) Kiev, Ukrainian SSR, Soviet Union (now Kyiv, Ukraine)
Nationality	Ukraine
Alma mater	UCLA, Taras Shevchenko National University of Kyiv
Scientific career
Fields	Computer science, Electrical engineering, Optimization, Electronic design automation, Artificial intelligence, Quantum computing
Institutions	University of Michigan, Stanford University, Meta Platforms, Google
Thesis	Top-Down Timing-Driven Placement with Direct Minimization of Maximal Signal Delay  (2001)
Doctoral advisor	Andrew B. Kahng
Doctoral students	Smita Krishnaswamy
Other notable students	Vivek Shende

Igor L. Markov has no known relation to the mathematician Andrey Markov.

Education

Markov graduated from Kyiv Natural Science Lyceum No. 145. He completed his undergraduate studies in mathematics at Taras Shevchenko National University of Kyiv. Markov obtained an M.A. degree in mathematics and a Doctor of Philosophy degree in computer science from UCLA in 2001.^[6][7]

Career

From the early 2000s through 2018 Markov was a professor at University of Michigan,^[1] where he supervised doctoral dissertations and degrees of 12 students in electrical engineering and computer science.^[7] He worked as a principal engineer at Synopsys during a sabbatical leave.^[8][9] In 2013-2014 he was a visiting professor at Stanford University.^[10] Markov worked at Google on Search and information retrieval,^[11] and at Meta on Machine Learning platforms.^[12][13][14] He returned to Synopsys in 2024^[15] and remains a Distinguished Architect as of 2025.^[16][17][18]

Markov is a member of the Board of Directors of Nova Ukraine, a California 501(c)(3) charity organization that provides humanitarian aid in Ukraine.^[19]He is also a member of the Board of Directors of the American Coalition for Ukraine, an umbrella organization that coordinates one hundred US-based nonprofits concerned about events in Ukraine.^[20]

University Teaching

Markov served as a professor in the Department of Electrical Engineering and Computer Science at the University of Michigan from the early 2000s through 2018, teaching both undergraduate and graduate courses in computer engineering and computer science disciplines.^[21] Markov regularly taught a range of courses, including:

• EECS 270: Introduction to Logic Design
• EECS 281: Data Structures and Algorithms
• EECS 478: Logic Synthesis and Optimization
• EECS 527: Circuit Layout Synthesis

He also supervised individual study and research projects, directed studies (EECS 499/599), and graduate seminars.^[21]

Feedback from students, including comments on RateMyProfessors, described Markov as a highly knowledgeable instructor with a rigorous, detail-oriented approach to teaching. Students frequently noted his strong command of course material, especially in technical and algorithmic topics. While some reviews recognized the challenging nature of his courses, others appreciated his clear explanations and use of real-world examples. Students also noted his availability during office hours and his encouragement of analytical thinking.^[21][22]

Overall, Markov's teaching was regarded as intellectually demanding but rewarding, preparing students for advanced topics in computer science, engineering, and research.^[21][22]

Awards and distinctions

The ACM Special Interest Group on Design Automation honored Markov with an Outstanding New Faculty Award in 2004.^[23] Markov received the NSF CAREER award in 2005. Along with Andrew Kahng, in 2011 Igor Markov won the A. Richard Newton GSRC Industrial Impact Award for research on circuit placement and the Capo software package, used by researchers and companies worldwide.^[24]

Markov was the 2009 recipient of IEEE CEDA Ernest S. Kuh Early Career Award "for outstanding contributions to algorithms, methodologies and software for the physical design of integrated circuits."^[25][26] Markov became ACM Distinguished Scientist in 2011.^[27][28] In 2013 he was named an IEEE fellow^[29] "for contributions to optimization methods in electronic design automation".^[30]

Markov won 2007-08 EECS Outstanding Achievement Awards at University of Michigan in recognition of excellence in research, teaching, and service.^[31]

Award-winning publications

Markov's peer-reviewed scholarly work was recognized with five best-paper awards, including four at major conferences and a journal in the field of electronic design automation, and one in theoretical computer science:

• The 2003 IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems Donald O. Pederson Best Paper Award, shared with Vivek Shende and John P. Hayes for work^[32] on reversible logic circuits.^[33]
• The 2004 best-paper award at the Design Automation and Test in Europe (DATE) conference, shared with Smita Krishnaswamy, George F. Viamontes, and John P. Hayes for work^[34] on circuit reliability evaluation with probabilistic transfer matrices.^[35] Full journal version of this work was published four years later.^[36]
• The 2008 best-paper award at the International Symposium on Physical Design (ISPD), shared with Stephen Plaza and Valeria Bertacco, for work^[37] on physical synthesis.^[38]
• The 2010 best-paper award at the International Conference on Computer-Aided Design (ICCAD) for work^[39] on circuit placement.^[40] The full journal version of this work was published two years later.^[41]
• The best-paper award at the 2012 Alan Turing Centenary Conference in Manchester, UK, shared with Karem A. Sakallah for work^[42] on graph automorphism and canonical labeling.^[43]
  

Key technical contributions

Quantum computing

Markov's contributions include results on quantum circuit synthesis (creating circuits from specifications) and simulation of quantum circuits on conventional computers (obtaining the output of a quantum computer without a quantum computer).

• An algorithm for the synthesis of linear reversible circuits with at most ${\displaystyle O(n^{2}/\log n)}$ CNOT gates (asymptotically optimal)^[44] that was extended by Scott Aaronson and Daniel Gottesman to perform optimal synthesis of Clifford circuits,^[45] with applications to quantum error correction.
• Optimal synthesis of a two-qubit unitary that uses the minimal number of CNOT gates^[46][47]
• Asymptotically optimal synthesis of an ${\displaystyle n}$-qubit quantum circuit that (a) implements a given unitary matrix using no more than${\displaystyle (23/48)\times 4^{n}-(3/2)\times 2^{n}+4/3}$ CNOT gates (less than a factor of two away from the theoretical lower bound) and (b) induces an initial quantum state using no more than ${\displaystyle 2^{n+1}-2n}$ CNOT gates (less than a factor of four away from the theoretical lower bound).^[46] IBM Qiskit uses Markov's circuit synthesis algorithm.^[48]
• Efficient simulation of quantum circuits with low tree-width using tensor-network contraction.^[49] Follow-up works extended this technique with approximations, which allowed them to simulate quantum Fourier transform in poly time.^[50][51] Markov's work was used in an essential way in the first proof (by Dorit Aharonov et al.) that quantum Fourier transform can be classically simulated.^[50]

Markov has been leading early quantum computing efforts at Synopsys with emphasis on leveraging the existing design and manufacturing ecosystem for silicon chips.^[16][52]

Physical design of integrated circuits

Markov's Capo placer^[53] provided a baseline for comparisons used in the placement literature. The placer was commercialized and used to design industry chips.^[25] Markov's contributions include algorithms, methodologies and software for

• Circuit partitioning:^[54][55] high-performance heuristic optimizations for hypergraph partitioning
• Placement:^[41][53] algorithms for finding ${\displaystyle (x,y)}$ locations of circuit components that optimize interconnects between those components
• Floorplanning:^[56] algorithms and methodologies for chip planning in terms of locations of large components
• Routing:^[57] algorithms based on Lagrangian relaxation to construct global wire routs on a multilayer grid structure
• Physical synthesis:^[37] algorithms and methodologies for altering logic circuits to admit layouts with shorter interconnects or lower latency

Machine learning

Markov led the development of an end-to-end AI platform called Looper, which supports the full machine learning lifecycle from model training, deployment, and inference all the way to evaluation and tuning of products. Looper provides easy-to-use APIs for optimization, personalization, and feedback collection.^[12][58][59]

Nonprofit involvement

At Nova Ukraine, Markov leads government and media relations, as well as advocacy efforts. Markov curated publicity efforts, established and curated large medical and evacuation projects, and contributed to fundraising. As part of Ukraine Action Summits organized by the American Coalition for Ukraine, Markov participates in Congressional advocacy.^[60]

In March 2022, Igor Markov, serving as a director of Nova Ukraine, coordinated one of the organization's largest humanitarian aid operations following the Russian invasion of Ukraine. Under Markov's leadership, Nova Ukraine partnered with the Ukrainian Student Association at Stanford University and the Ukrainian Association of Washington State to organize the shipment of 32 tons of emergency medical supplies valued at $3.5 million. These efforts involved the aggregation of donations from hospitals throughout the Pacific Northwest, key medical surplus facilities, and the broader Ukrainian American community. The supplies included surgical kits, syringes, anesthesia machines, life-saving first aid kits, and pediatric medicines, among other critical equipment, destined for hospitals and front-line medical personnel in Ukraine. The operation culminated in a chartered Airbus A330 flight departing from Seattle–Tacoma International Airport and arriving in Lublin, Poland, on March 29, 2022, where the cargo was subsequently transported to Ukraine's Ministry of Health for further distribution across the country.^[61][62][63]

Markov emphasized the urgency of the humanitarian situation in Ukraine, highlighting the use of air cargo flights to dramatically reduce delivery times for critical medical supplies to under two weeks, compared to traditional shipping methods that could take months. The effort was widely recognized by community leaders and public officials in Washington State and led to the establishment of further transatlantic supply efforts following its success.

In October 2023, Igor Markov played a key role in organizing a visit of the Ukrainian Council of Churches and Religious Organizations (UCCRO) to the United States. The UCCRO delegation, representing more than 95 percent of Ukraine’s religious communities, aimed to raise international awareness about the consequences of Russia’s full-scale invasion for religious freedom and civil society in Ukraine. The visit was coordinated with the support of Nova Ukraine, where Markov serves in a leadership capacity, in collaboration with Razom for Ukraine and other Ukrainian-American organizations. As part of the delegation’s program, religious leaders held meetings with members of the United States Congress, the Department of State, academic institutions, and faith-based organizations. The initiative was recognized by the Embassy of Ukraine in the United States as an important demonstration of Ukraine’s religious unity and democratic values in the context of war.^{[64][65][66][67]}

Books and other publications

Markov co-authored over 200 peer-reviewed publications in journals and archival conference proceedings, and Google Scholar reported over 21,000 citations of his publications as of April 2025.

In a 2014 Nature article,^[68] Markov surveyed known limits to computation, pointing out that many of them are fairly loose and do not restrict near-term technologies. When practical technologies encounter serious limits, understanding these limits can lead to workarounds. More often, what is practically achievable depends on technology-specific engineering limitations.

In 2024, Markov published a paper in Communications of the ACM critical of a prior Nature publication on chip design.^[69][70]

Books

Authored

• George F. Viamontes; Igor L. Markov; John P. Hayes (2009). Quantum Circuit Simulation. Springer. ISBN 978-90-481-3064-1.
• Kai-hui Chang; Valeria Bertacco; Igor L. Markov (2009). Functional Design Errors in Digital Circuits - Diagnosis, Correction and Repair. Lecture Notes in Electrical Engineering. Vol. 32. Springer. ISBN 978-1-4020-9364-7.
• David A. Papa; Igor L. Markov (2013). Multi-Objective Optimization in Physical Synthesis of Integrated Circuits. Lecture Notes in Electrical Engineering. Vol. 166. Springer. ISBN 978-1-4614-1355-4.
• Andrew B. Kahng; Jens Lienig; Igor L. Markov; Jin Hu (2022). VLSI Physical Design - From Graph Partitioning to Timing Closure (second ed.). Springer. ISBN 978-3-030-96415-3. (first edition published in 2011)
• Smita Krishnaswamy; Igor L. Markov; John P. Hayes (21 September 2012). Design, Analysis and Test of Logic Circuits Under Uncertainty. Springer. ISBN 978-90-481-9643-2.

Edited

• Luciano Lavagno; Igor L. Markov; Grant Martin; Louis K. Scheffer, eds. (2016). Electronic Design Automation for IC System Design, Verification, and Testing (second ed.). Taylor & Francis. ISBN 9781138586000.

Activity on social media

Markov was awarded a Top Writer status on Quora in 2018, 2017, 2016, 2015 and 2014, he has over 80,000 followers. His contributions were republished by Huffington Post, Slate, and Forbes.^[71]

Markov is a moderator for the cs.ET (Emerging Technologies in Computing and Communications) subject area on arXiv.

Notes

1. Ukrainian: Ігор Леонідович Марков, romanized: Ihor Leonidovych Markov