Igor L. Markov Explained

Igor Leonidovich Markov
Native Name Lang:uk
Native Name:Ігор Леонідович Марков
Birth Date:1973 3, df=yes
Field:Computer Science, Electrical Engineering, Optimization, Electronic Design Automation, Artificial Intelligence, Quantum Computing
Work Institution:University of Michigan, Stanford University, Meta Platforms, Google
Doctoral Advisor:Andrew B. Kahng
Thesis Title:Top-Down Timing-Driven Placement with Direct Minimization of Maximal Signal Delay
Thesis Year:2001
Notable Students:Vivek Shende
Doctoral Students:Smita Krishnaswamy

Igor Leonidovich Markov (Ukrainian: Ігор Леонідович Марков|{{transliteration|uk|ukrainian|Ihor Leonidovych Markov; born in 1973 in Kyiv, Ukraine) is an American professor, 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[1] responsible for aid to Ukraine worth over a hundred million dollars.[2] [3] [4]

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

Career

Markov obtained an M.A. degree in mathematics and a Doctor of Philosophy degree in Computer Science from UCLA in 2001.[5] [6] From the early 2000s through 2018 he was a professor at University of Michigan, where he supervised doctoral dissertations and degrees of 12 students in Electrical engineering and Computer science.[6] He worked as a principal engineer at Synopsys during a sabbatical leave.[7] [8] In 2013-2014 he was a visiting professor at Stanford University.[9] Markov worked at Google on Search and Information Retrieval,[10] and at Meta on Machine Learning platforms.[11] [12] [13] As of 2024, he works at Synopsys.[14]

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.[15] 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.

Markov is 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.[16]

Awards and distinctions

ACM Special Interest Group on Design Automation honored Markov with an Outstanding New Faculty Award in 2004.[17]

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."[18] [19] Markov became ACM Distinguished Scientist in 2011. In 2013 he was named an IEEE fellow[20] "for contributions to optimization methods in electronic design automation".

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:

Books and other publications

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

In a 2014 Nature article,[33] Markov surveyed known limits to computation, pointing out that many of them are fairly lose 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.

Markov co-edited the two-volume Electronic Design Automation handbook published in second edition by Taylor & Francis in 2016.[34] He also co-authored five scholarly books published by Springer, among them are two textbooks:

Markov's other books cover uncertainty in logic circuits,[38] dealing with functional design errors in digital circuits,[39] and physical synthesis of integrated circuits.[40]

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).

O(n2/logn)

CNOT gates (asymptotically optimal)[41] that was extended by Scott Aaronson and Daniel Gottesman to perform optimal synthesis of Clifford circuits,[42] with applications to quantum error correction.

n

-qubit quantum circuit that (a) implements a given unitary matrix using no more than

(23/48) x 4n-(3/2) x 2n+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

2n+1-2n

CNOT gates (less than a factor of four away from the theoretical lower bound). IBM Qiskit uses Markov's circuit synthesis algorithm.[45]

Physical design of integrated circuits

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

(x,y)

locations of circuit components that optimize interconnects between those components

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.[55] [56]

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.[57]

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

References

  1. Web site: Nova Ukraine: Supporting Ukraine in Crisis and Beyond. National Philanthropic Trust. March 30, 2022.
  2. Web site: Civilians Evacuated from Mariupol . CNN Newsroom Transcripts. May 2, 2022.
  3. Web site: Nova Ukraine has raised $30M to help with relief in #Ukraine since #Russia's invasion (video) . Twitter. First Move CNN. May 11, 2022.
  4. Web site: 2022 . Nova Ukraine Delivers More Than $50 Million of Aid to Ukraine in 2022. . December 19, 2022 . PR Newswire.
  5. Web site: Igor Leonidovich Markov. Mathematics Genealogy Project. August 11, 2023.
  6. Web site: Igor Markov: IEEE Xplore author profile . IEEE Xplore . October 8, 2023.
  7. US8141024B2. Temporally-assisted resource sharing in electronic systems. 2012-03-20. Markov. McElvain. Igor L.. Kenneth S..
  8. US9285796B2. Approximate functional matching in electronic systems. 2016-03-15. Markov. McElvain. Igor L.. Kenneth S..
  9. Web site: Visiting Professor: Igor Markov. Stanford Electrical Engineering. August 11, 2023.
  10. Web site: Patent US 10,235,432 "Document retrieval using multiple sort orders". Google Patents. August 11, 2023.
  11. Web site: Inside Meta's AI optimization platform for engineers across the company. Facebook. August 11, 2023.
  12. Web site: VanBilliard . Jefferson . 2023-07-26 . Igor Markov . 2023-10-05 . The AI Conference . en-US.
  13. Kasturi . Nitya . Markov . Igor L. . 2022-02-11 . Text Ranking and Classification using Data Compression . I (Still) Can't Believe It's Not Better! Workshop at NeurIPS 2021 . en . PMLR . 48–53. 2109.11577 .
  14. Web site: Mona Knutsen on LinkedIn: #genairevolution #welcometothefuture #innovationleader #legend . 2024-03-27 . www.linkedin.com . en.
  15. Web site: Nova Ukraine Board of Directors. Nova Ukraine. 18 April 2022 . August 12, 2023.
  16. Web site: Board of Directors – American Coalition for Ukraine . 2024-06-23 . en-US.
  17. Web site: Outstanding New Faculty Award . 18 June 2019 . ACM SIGDA . October 8, 2023.
  18. Web site: IEEE CEDA Ernest S. Kuh Early Career Award. IEEE Council on Electronic Design Automation . August 7, 2023.
  19. News: IEEE Council on EDA Honors Igor Markov with Early Career Award . . October 3, 2023.
  20. Web site: Igor Markov IEEE CASS . 2023-10-05 . ieee-cas.org.
  21. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . Vivek V. Shende . Aditya K. Prasad . Igor L. Markov . John P. Hayes . Synthesis of reversible logic circuits . 22 . 6 . 2003 . 710–722. 10.1109/TCAD.2003.811448 .
  22. Web site: IEEE Transactions on Computer-Aided Design Donald O. Pederson Best Paper Award IEEE Council on Electronic Design Automation . 2023-08-12 . ieee-ceda.org . en.
  23. Smita Krishnaswamy . George F. Viamontes . Igor L. Markov . John P. Hayes . Accurate Reliability Evaluation and Enhancement via Probabilistic Transfer Matrices . Proceedings of Design Automation and Test in Europe (DATE) . 2005 . 2005 . 282–287.
  24. Web site: Best Paper Awards DATE 2006 . August 12, 2023.
  25. Smita Krishnaswamy . George F. Viamontes . Igor L. Markov . John P. Hayes . Probabilistic transfer matrices in symbolic reliability analysis of logic circuits . ACM Transations on Design Automation of Electronic Systems . 13 . 1 . 8:1–8:35 . 2008.
  26. Proceedings of International Symposium on Physical Design (ISPD) . 2008 . 2008. Stephen Plaza . Igor L. Markov . Valeria Bertacco . Optimizing non-monotonic interconnect using functional simulation and logic restructuring . 95–102.
  27. Web site: Best Paper Awards International Symposium on Physical Design (ISPD) 2008 . October 26, 2023.
  28. Myung-Chul Kim . Dongjin Lee . Igor L. Markov . SimPL: An effective placement algorithm . Proceedings of International Conference on Computer-Aided Design (ICCAD) . 2010 . 2010 . 649–656.
  29. Web site: Best Paper Awards IEEE/ACM International Conference on Computer-Aided Design (ICCAD) 2010 . October 26, 2023.
  30. Myung-Chul Kim . Dongjin Lee . Igor L. Markov . SimPL: An Effective Placement Algorithm . . 31 . 1 . 50–60 . 2012. 10.1109/TCAD.2011.2170567 . 47293399 .
  31. Book: Hadi Katebi . Karem A. Sakallah . Igor L. Markov . Graph Symmetry Detection and Canonical Labeling: Differences and Synergies . Turing-100 . 2012 . Easy Chair . 9781782310006.
  32. Web site: Computer Scientists Win Best Paper Award at Turing Centenary Conference . 2023-08-13 . Computer Science and Engineering . en-US.
  33. Markov . Igor . 2014 . Limits on Fundamental Limits to Computation. . 512 . 7513. 147–154. 10.1038/nature13570 . 25119233 . 1408.3821 . 2014Natur.512..147M. 4458968 .
  34. Book: Electronic Design Automation for IC System Design, Verification, and Testing; 2nd ed. Luciano Lavagno . Igor L. Markov . Grant Martin . Louis K. Scheffer . 2016 . Taylor & Francis. 9781138586000 . 664.
  35. Book: Quantum Circuit Simulation . George F. Viamontes . Igor L. Markov . John P. Hayes . Springer . 2009 . 200 . 978-90-481-3064-1 .
  36. Book: Andrew B. Kahng . Jens Lienig . Igor L. Markov . Jin Hu . VLSI Physical Design - From Graph Partitioning to Timing Closure . Springer . 2011 . 978-90-481-9590-9 . 1–310.
  37. Book: Andrew B. Kahng . Jens Lienig . Igor L. Markov . Jin Hu . VLSI Physical Design - From Graph Partitioning to Timing Closure, 2nd ed . Springer . 2022 . 978-3-030-96415-3 . 1–317.
  38. Book: Design, Analysis and Test of Logic Circuits Under Uncertainty . Smita Krishnaswamy . Igor L. Markov . John P. Hayes . 21 September 2012 . Springer . 978-90-481-9643-2.
  39. Book: Functional Design Errors in Digital Circuits - Diagnosis, Correction and Repair . Lecture Notes in Electrical Engineering . 32 . Kai-hui Chang . Valeria Bertacco . Igor L. Markov . Springer . 2009 . 978-1-4020-9364-7 . 185.
  40. Book: Multi-Objective Optimization in Physical Synthesis of Integrated Circuits . Lecture Notes in Electrical Engineering . 166 . David A. Papa . Igor L. Markov . Springer . 2013 . 978-1-4614-1355-4 . 155.
  41. Efficient Synthesis of Linear Reversible Circuits . Quantum Information and Computation . 8. 3–4 . 282–294 . 2008 . K. N. Patel . I. L. Markov . J. P. Hayes . 10.26421/QIC8.3-4-4 . quant-ph/0302002 .
  42. Improved Simulation of Stabilizer Circuits . Scott . Aaronson . Daniel . Gottesman . Phys. Rev. A . 70 . 052328 . 2004 . 5 . quant-ph/0406196 . 10.1103/PhysRevA.70.052328 . 2004PhRvA..70e2328A . 5289248 .
  43. Vivek V.. Shende. Stephen S.. Bullock. Igor L.. Markov. Synthesis of quantum logic circuits . . 25 . 6 . 1000–1010 . 2006 . 10.1109/TCAD.2005.855930. quant-ph/0406176. 265038781.
  44. Shende . Vivek V. . Markov . Igor L. . Bullock . Stephen S. . 2004-06-30 . Minimal universal two-qubit controlled-NOT-based circuits . Physical Review A . 69 . 6 . 062321 . 10.1103/PhysRevA.69.062321. quant-ph/0308033 . 2004PhRvA..69f2321S . 119489186 .
  45. Araujo . Israel F. . Park . Daniel K. . Petruccione . Francesco . da Silva . Adenilton J. . 2021-03-18 . A divide-and-conquer algorithm for quantum state preparation . Scientific Reports . en . 11 . 1 . 6329 . 10.1038/s41598-021-85474-1 . 33737544 . 7973527 . 2045-2322. free .
  46. Markov . Igor L. . Shi . Yaoyun . January 2008 . Simulating Quantum Computation by Contracting Tensor Networks . SIAM Journal on Computing . en . 38 . 3 . 963–981 . 10.1137/050644756 . 0097-5397. quant-ph/0511069 . 3187832 .
  47. Yoran . Nadav . Short . Anthony J. . 2007-10-16 . Efficient classical simulation of the approximate quantum Fourier transform . Physical Review A . 76 . 4 . 042321 . 10.1103/PhysRevA.76.042321. quant-ph/0611241 . 2007PhRvA..76d2321Y . 119444986 .
  48. Aharonov . Dorit . Landau . Zeph . Makowsky . Johann . The quantum FFT can be classically simulated . 2006 . quant-ph/0611156.
  49. Web site: IEEE Council on EDA Honors Igor Markov with Early Career Award . 2023-10-03 . www.chipestimate.com.
  50. Optimal partitioners and end-case placers for standard-cell layout . Andrew E. Caldwell . Andrew B. Kahng . Igor L. Markov . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. . 19 . 11 . 1304–1313 . 2000. 10.1109/43.892854 .
  51. Caldwell . Andrew E. . Kahng . Andrew B. . Markov . Igor L. . 2001-12-31 . Design and implementation of move-based heuristics for VLSI hypergraph partitioning . ACM Journal of Experimental Algorithmics . 5 . 5–es . 10.1145/351827.384247 . 2074760 . 1084-6654.
  52. Book: Proceedings of the 37th conference on Design automation - DAC '00 . https://ieeexplore.ieee.org/document/855358 . Andrew E. Caldwell . Andrew B. Kahng . Igor L. Markov . Can recursive bisection alone produce routable placements? . 2000 . 2000 . 477–482. 10.1145/337292.337549 . 1581131879 . 4926321 .
  53. Fixed-outline floorplanning: enabling hierarchical design . Saurabh N. Adya . Igor L. Markov . IEEE Trans. Very Large Scale Integr. Syst. . 11 . 6 . 1120–1135 . 2003. 10.1109/TVLSI.2003.817546 .
  54. High-performance routing at the nanometer scale . Jarrod A. Roy . Igor L. Markov . IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. . 27 . 6 . 1066–1077 . 2008. 10.1109/ICCAD.2007.4397313 . 61607526 .
  55. Book: Markov . Igor L. . Wang . Hanson . Kasturi . Nitya S. . Singh . Shaun . Garrard . Mia R. . Huang . Yin . Yuen . Sze Wai Celeste . Tran . Sarah . Wang . Zehui . Glotov . Igor . Gupta . Tanvi . Chen . Peng . Huang . Boshuang . Xie . Xiaowen . Belkin . Michael . Looper: An End-to-End ML Platform for Product Decisions . 2022-08-14 . Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining . https://doi.org/10.1145/3534678.3539059 . KDD '22 . New York, NY, USA . Association for Computing Machinery . 3513–3523 . 10.1145/3534678.3539059 . 978-1-4503-9385-0. 2110.07554 .
  56. Looper: An End-to-End ML Platform for Product Decisions - Igor Markov Stanford MLSys #60 . en.
  57. Web site: Igor Markov's profile . Quora . October 8, 2023.

[58] [59] [60] [61]

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Igor L. Markov".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.