Igor L. Markov

Personal

Education

• Ph. D. in Computer Science, UCLA, 2001. Advisor: Prof. Andrew B. Kahng.
• Master of Arts in Mathematics, UCLA, 1994.
• Diploma with Honors in Mathematics, Kiev University, 1994.
• Languages: Russian (native), Ukrainian (fluent), English (fluent), reading knowledge of French.

Work experience

Univ. of Michigan Ann Arbor, EECS Dept., 2006-current

Associate Professor.

Univ. of Michigan Ann Arbor, EECS Dept., 2000-2006

Assistant Professor.

UCLA, Computer Science Department, 1996-2000

Research in VLSI CAD. Research Assistant.

UCLA, Mathematics Department, 1994-96

Teaching Assist./Assoc.: College Mathematics and Computer Programming.

Parametric Technology Corp. (NASDAQ: PMTC), 1995

Solid Modeling CAD and Computer Graphics.
C/C++ programming in Unix and Windows environments. Software Engineer.

Honors, Awards and Selected Invited Lectures

• Best research poster, UCLA, Computer Science Dept., 1999.
• Outstanding Ph.D. student, UCLA, Computer Science Dept., 2000.
• IBM University Partnership Award, 2001.
• The IEEE/ACM Design Automation Conference fellowship, 2001.
• Invited speaker at the IBM Annual All-site Meeting in Fishkill, NY 2001.
• Invited papers/talks at Int'l Symp. on Quality Electronic Design 2003, Int'l Symp. on Physical Design 2003 and Int'l Workshop on Logic Synthesis 2003.
• Distinguished Lecture in Quantum Information Processing, National Institute of Standards and Technology (NIST), Radiation Physics Division, January 2004.
• The 2004 IEEE Circuits and Systems (CaS) Society Donald O. Pederson Award (presented at DAC 2004) for the paper, "Synthesis of Reversible Logic Circuits", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 6, pp. 710-722, June 2003 (with V.V. Shende, A.K. Prasad, and J.P. Hayes).
• Three-lecture tutorial at a summer school on symmetries in AI at the Univ. St. Andrews, Scotland, June 2004.
• Invited speaker at the Intel research symposium in Haifa, Israel, June 2004.
• Panelist at the workshop on Symmetries in Constraint Satisfaction Problems (SymCon), Toronto, Canada, Sept. 2004.
• The 2004 ACM Special Interest Group on Design Automation (SIGDA) Outstanding New Faculty Award
  (presented at ICCAD in November 2004).
• Best paper award at DATE 2005 in the Circuit Test category, for the paper "Accurate Reliablity Evaluation and Enhancement via Probabilistic Transfer Matrices" by S. Krishnaswamy, G. F. Viamontes, I. L. Markov and J. P. Hayes.
• NSF CAREER Award 2005.
• Synplicity Inc. Faculty Award 2005.
• ACM SIGDA Technical Leadership Award (presented at ICCAD in November 2005).
• IEEE Senior Member, November 2005.
• Best-paper award nominations at DAC 1997, ASPDAC 1999, ASPDAC 2000, DAC 2003, DAC 2004, DATE 2005, ISPD 2006.
• My group's software has been used to design successful chips (structured ASICs) at these companies: LSI Logic, NEC, Fujitsu, Hewlett Packard, Silicon Graphics, Hitachi, Seagate, Cisco, Nortel Networks, Raytheon, Marconi, Alcatel, 3COM, EMC², Timble, IP Wireless, Cryptek. These chips include hard-drive controllers (Ultra320 SCSI), wireless communication systems (Time-Division Duplexing), a 24-channel GPS receiver and inertial navigation systems.

Research interests

• Physical design and physical synthesis for VLSI.
• Quantum information and computation: synthesis and simulation of quantum circuits.
• Formal and semi-formal verification of digital circuits and systems.
• Combinatorial optimization: hypergraph partitioning, block packing.
• Search in artificial intelligence: Boolean satisfiability, block packing, compressed reasoning, stochastic optimization.

Teaching interests

• Established a graduate-level course on algorithms for circuit layout
• Guided graduate student seminars on (i) quantum computing,
  (ii) physical synthesis, verification and test of integrated circuits
• Taught large undergraduate courses on logic circuits, algorithms and data structures, and algorithm analysis

Professional Service

• Member of the Fulbright Committee, 2001
• Undergraduate student advisor at the Department of EECS, 2001-2003
• Member of the Computing Infrastructure committee at the Department of, EECS 2003-2005
• Member of the Graduate Committee at the CSE Division, 2005-2006
• Internal referee for two faculty reviews, 2005
• Chair of a major review committee at the CSE Division, 2005-2006
• Member of 19 Ph.D. committees at the EECS Department and one Ph.D. committee at the IOE Department
• Member of qualifying examination committees (every semester)
• Also see Work with Graduate and Undergraduate Students below

• Guest Editor, Integration: the VLSI Journal, 2005-2006
• Editor of the ACM SIGDA newsletter, 2005-current
• Associate Editor of the ACM SIGDA newsletter, 2002-2005
• Editor of the online GSRC Bookshelf for CAD Algorithms http://vlsicad.eecs.umich.edu/BK, 2000-current

• ACM Special Interest Group on Design Automation (SIGDA) advisory board, 2005-current
• Digital Logic advisory board with McGraw Hill Corp.,
  focusing on undergraduate courses in Digital Logic, 2005-2006
• Technical advisory board of the EDA Encyclopedia, to be published by Kluwer Academic Publishers

• Vice-chair of the Tools and Methodologies track at IEEE Intl. Conf. on Computer Design (ICCD), 2005
• Co-founder of the ACM/IEEE Intl. Workshop On System-Level Interconnect (SLIP),
  served as publicity chair, publication chair, special sessions chair 2000-2003
• Program Committee chair (2004) and General chair (2005)
  of the ACM/IEEE Intl. Workshop On System-Level Interconnect Prediction
• Organizer of a special session on Quantum Computing at DAC 2003
• Session chair: DATE 2003,2004; SLIP 2000-2005; ISPD 2002,2003,2005; ISCAS 2002,2003; ICCAD 2003-2005

• ACM/IEEE Design Automation Conf. (DAC), 2004-2006
• ACM/IEEE Intl. Conf. on Computer-Aided Design of Integrated Circuits (ICCAD), 2003-2005
• ACM/IEEE Design Automation and Test in Europe (DATE) Conf., 2003-2005
• ACM/IEEE Intl. Symposium on Physical Design (ISPD), 2002-2005
• ACM/IEEE Great Lakes Symposium on VLSI (GLSVLSI), 2002-2004
• AAAI Workshop on Symmetry in Constraint-Satisfaction Problems (SymCon), since 2003
• ACM/IEEE Intl. Workshop on Logic and Synthesis (IWLS), since 2002
• ACM/IEEE Intl. Workshop On System-Level Interconnect (SLIP), since 1999

• Member of two proposal review panels at the National Science Foundation (NSF), 2005
• Reviewer for journals: IEEE Transactions on Computers, ACM Transactions on Design Automation, IEEE Transactions on CAD, IEEE Transactions on VLSI, IEEE Transactions on Circuits and Systems I, IEEE Transactions on Circuits and Systems II, IEEE Design and Test, IEE Proceedings: Computers and Digital Techniques, IEE Proceedings: Circuits, Devices and Systems, IEE Electronic Letters, Journal of Electronic Testing, Journal of Universal Computer Science, Journal of Multiple-Valued Logic and Soft Computing, Journal of Formal Methods in System Design, Quantum Information and Computation, Discrete and Applied Mathematics, Theoretical Computer Science, Integration: the VLSI Journal, Microelectronics Journal, International Journal of Electronics
• Reviewer for conferences: ACM/IEEE Design Automation Conf. (DAC), ACM/IEEE Intl. Conf. on Computer-Aided Design (ICCAD), IEEE/ACM Design Automation & Test in Europe (DATE), IEEE/ACM Intl. Symposium on Circuits and Systems (ISCAS), ACM Intl. Symposium on Computer Architecture (ISCA), ACM Architectural Support for Programming ACM Languages and Operating Systems (ASPLOS), AAAI Intl. Joint Conf. on Artificial Intelligence (IJCAI)
• Reference for 9 job-seekers with recent Ph.D. degrees in EE, CS and Mathematics from Michigan, Berkeley, Cornell, UCLA, UCSD, Waterloo and Univ. Victoria

Research Funding (over $2.5M in toto)

• Int'l Business Machines Corp. (IBM), 2000-2003.
• Defense Advanced Projects Agency (DARPA), Quantum Information Science and Technology, 2001-2005.
• Semiconductor Industry Association (SIA/MARCO) and DARPA
  via the Gigascale Silicon Research Center (GSRC), 2001-2006.
• National Science Foundation (NSF) Information Technology Research (ITR), 2002-2006.
• National Science Foundation (NSF) Computer Architecture (CA), 2002-2005.
• Synplicity, Inc., 2003-2006.
• National Science Foundation (NSF) Design Automation (DA/SGER), 2003-2004.
• National Science Foundation (NSF) CAREER, 2005-2010.
• Univ. of Michigan, Division of Computer Science and Engineering, High-visibility Projects in CSE, 2004-2005.
• US AirForce, 2006-2010.
• Equipment donations from IBM (2002), Intel (2004), Altera (2005) and AMD (2006).

Consulting

• McGraw Hill Corporation
• Oxford University Press
• Cambridge University Press
• Synplicity Inc.
• Calypto Design Systems
• Belgian government
• O'Melveny & Meyers LLP

Work with Graduate Students

• Graduated two Ph.D. students - Dr. Arathi Ramani is working for Microsoft in Redmond, WA; Dr. Saurabh Adya is currently working for Synplicity Inc., an EDA vendor in the Silicon Valley. Former students who graduated with M.S. degrees currently work for Xilinx, AMD and Microsoft.
• Currently directing research of 7 graduate students (2 co-advised with Prof. John Hayes, 2 with Prof. Valeria Bertacco).
  Most of my students have published and presented their work at national and international conferences and symposia.
  Of the current and past graduate students, two are minorities and three are women.
• Coached teams of two graduate students who won the first prize at the ACM SIGDA CAD-athlon (programming contest) at ICCAD in November 2002, November 2004 and November 2005 (teams from Berkeley and MIT won the first place once, each).
• Current graduate student George Viamontes won a Department of Energy (DoE) High-Performance Computer Science Fellowship that supports his Ph.D. work on quantum computing and a summer practicum at the Los Alamos Nat'l Lab.
• Current graduate student Jarrod Roy won a Rackham pre-doctoral Fellowship that supports his Ph.D. work on physical design of integrated circuits.
• Graduate students in my group have successfully interned at IBM, Cadence Berkeley Labs and Calypto Design Systems.

Work with Undergraduate Students

• Directed research of 10 undergraduate students.
• Shared the 2004 Donald O. Pederson "paper-of-the-year" award (presented at DAC) with two undergraduates Vivek Shende and Aditya Prasad (the latter is now with Amazon.com).
• Together with undergraduate co-authors, published three peer-reviewed workshop papers (IWLS 2002, IWLS 2003 and SymCon 2003), four conference papers (ICCAD 2002, DATE 2004, SPIE QIC 2004, GLSVLSI 2004), and four journal papers (IEEE Trans. on CAD 2003, Quantum Information and Computation, and two in APS Physical Review A 2004).
• Undergraduate student Hayward H. Chan received an honorable mention from CRA in Fall 2004 for his work on block packing with symmetries.
• Organized directed studies projects (EECS 499) and summer research projects for 13 talented undergraduate students. Some of them are now employed at Amazon.com, Google.com and Dept. of Defense, and others are in graduate school.
• Provided reference letters to a number of undergraduate students applying to graduate school.

Papers in journals, magazines, edited volumes etc.

J37. (with K.-H. Chang and V. Bertacco), "Simulation-based Bug Trace Minimization with BMC-based Refinement", to appear in IEEE Trans. on Computer-Aided Design, 2007.
J36. (with D. A. Papa), "Hypergraph Partitioning and Clustering", in Approximation Algorithms and Metaheuristics, T. Gonzalez, ed.; CRC Press, 2006, in print (invited survey).
J35. (with A. Ramani, F. A. Aloul and K. A. Sakallah), "Breaking Instance-Independent Symmetries in Exact Graph Coloring", to appear in Journal of Artificial Intelligence Research, 2006.
J34. (with S. N. Adya and P. G. Villarrubia), "On Whitespace and Stability in Min-cut Placement", Integration: the VLSI Journal, vol. 39/4, pp. 340-362, 2006.
J33. (with J. A. Roy, S. N. Adya and D. A. Papa), "Min-cut Floorplacement", IEEE Trans. on CAD, vol.25, no. 7, July 2006.
J32. (with V. V. Shende and S. S. Bullock), "Synthesis of Quantum Logic Circuits", IEEE Trans. on CAD, vol.25, no. 6, June 2006, pp. 1000-1010.
J31. (with F. A. Aloul and K. A. Sakallah) "Efficient Symmetry Breaking for Boolean Satisfiability", IEEE Trans. on Computers, vol. 55, no. 5, pp. 541-558, 2006.
J30. (with K. M. Svore, A. W. Cross, I. L. Chuang and A. V. Aho), "A Layered Software Architecture for Quantum Computing Design Tools", IEEE Computer, January 2006, pp. 74-83.
J29. (with G. F. Viamontes and J. P. Hayes), "Is Quantum Search Practical?", IEEE/AIP Computing in Science and Engineering, May/June 2005, pp. 62-70.
J28. (with D. B. Motter and J. A. Roy), "Resolution Cannot Polynomially Simulate Compressed-BFS," Annals of Mathematics and Artificial Intelligence, vol. 44, no.1-2, pp. 121-156, May 2005.
J27. (with G. F. Viamontes and J. P. Hayes), "Graph-based Simulation of Quantum Computation in the Density Matrix Representation", Quantum Information and Computation, vol.5, no.2 pp. 113-130, February 2005.
J26. (with S. N. Adya), "Combinatorial Techniques for Mixed-size Placement," ACM Trans. on Design Automation of Electronic Systems, vol. 10, no. 5, January 2005.
J25. (with V. V. Shende), "Quantum Circuits for Incompletely Specified Two-Qubit Operators", Quantum Information and Computation, vol.5, no.1, pp. 49-57, January 2005.
J24. (with F. A. Aloul and K. A. Sakallah), "MINCE: A Static Global Variable-Ordering for SAT Search and BDD Manipulation", Journal of Universal Computer Science, vol. 10, no. 12, pp. 1559-1562, December 2004.
J23. (with K. N. Patel), "Error Correction and Crosstalk Avoidance in DSM Busses," IEEE Trans. on VLSI vol. 12, no.10, pp. 1076-1081, October 2004.
J22. (with K. N. Patel and J. P. Hayes), "Fault Testing for Reversible Circuits," IEEE Trans. on CAD, 23(8), pp. 1220-1230, August 2004.
J21. (with V. V. Shende and S. S. Bullock), "Recognizing Small-circuit Structure in Two-qubit Operators," APS Physical Review A 70, 012310-012314, 2004. Reprinted in APS/AIP Virtual Journal of Quantum Information, August 2004.
J20. (with V. V. Shende and S. S. Bullock), "Minimal Universal Two-qubit Controlled-NOT-based Circuits," APS Physical Review A 69, 062321-62329, 2004. Reprinted in APS/AIP Virtual Journal of Quantum Information, July 2004.
J19. (with S. N. Adya et al.) "Benchmarking for Large-scale Placement and Beyond," IEEE Trans. on CAD, 23(4), pp. 472-488, April 2004.
J18. (with S. S. Bullock) "Asymptotically Optimal Circuits for Arbitrary n-qubit Diagonal Computations," Quantum Information and Computation, vol. 4, no. 1, pp. 27-47, January 2004.
J17. (with S. N. Adya) "Fixed-outline Floorplanning : Enabling Hierarchical Design," IEEE Trans. on VLSI, vol. 11(6), pp. 1120-1135, December 2003.
J16. (with A. E. Caldwell and A. B. Kahng) "Hierarchical Whitespace Allocation in Top-down Placement," IEEE Trans. on CAD, vol. 22(11), pp. 716-724, November 2003.
J15. (with G. F. Viamontes and J. P. Hayes), "Improving Gate-Level Simulation of Quantum Circuits," Quantum Information Processing, vol. 2(5), pp.347-380, October 2003.
J14. (with F. A. Aloul, A. Ramani and K. A. Sakallah) "Solving Difficult Instances of Boolean Satisfiability in the Presence of Symmetry," IEEE Trans. on CAD, vol. 22(9), pp. 1117-1137, September 2003.
J13. (with S. S. Bullock) "An Arbitrary Two-qubit Computation in 23 Gates or Less," APS Physical Review A, vol. 68, no. 1, 012318-012325, July 2003. Reprinted in APS/AIP Virtual Journal of Quantum Information, August 2003.
J12. (with V. V. Shende, A. K. Prasad and J. P. Hayes) "Synthesis of Reversible Logic Circuits," IEEE Trans. on CAD, vol. 22(6), p. 710-722, June 2003. IEEE CAS Donald O. Pederson "paper of the year" award.
J11. (with Y. Cao et al.) "Improved A Priori Interconnect Predictions and Technology Extrapolation in the GTX System", IEEE Trans. on VLSI, vol. 11(1), pp. 3-14. 2003.
J10. (with A. E. Caldwell and A. B. Kahng), "Toward CAD-IP Reuse: The MARCO GSRC Bookshelf of Fundamental CAD Algorithms", IEEE Design and Test, pp. 72-81, May 2002.
J9. (with A. A. Kennings), "Smoothening Max-terms and Analytical Minimization of Half-Perimeter Wirelength", VLSI Design, vol. 14(3), pp. 229-237, 2002.
J8. (with A. B. Kahng et al.), "Constraint-Based Watermarking Techniques for Design Intellectual Property Protection", IEEE Trans. on CAD, vol. 20(10), pp. 1236-1252, October 2001.
J7. (with R. Baldick, A. B. Kahng and A. A. Kennings), "Efficient Optimization by Modifying the Objective Function", IEEE Trans. on Circuits and Systems, vol. 48(8), pp. 947-957, 2001,
J6. (with A. E. Caldwell and A. B. Kahng), "Iterative Partitioning With Varying Node Weights", VLSI Design, vol.11, no.3, pp. 249-58, 2000.
J5. (with C. J. Alpert, A. E. Caldwell and A. B. Kahng), "Hypergraph Partitioning With Fixed Vertices", IEEE Trans. on CAD, vol. 19, no. 2, (2000), pp. 267-272, February-March 2000.
J4. (with C. J. Alpert et al.), "Analytical Engines Are Unnecessary in Top-Down Partitioning-Based Placement", VLSI Design, 10(1), pp. 99-116, January 1999.
J3.
• (with A. E. Caldwell and A. B. Kahng), "Design and Implementation of Move-based Heuristics for VLSI Hypergraph Partitioning", ACM Journal of Experimental Algorithms, vol. 5, 2000 (online publication).
• (with A. E. Caldwell and A. B. Kahng), "Design and Implementation of the Fiduccia-Mattheyses Heuristic for VLSI Netlist Partitioning", book chapter, Lecture Notes in Comp. Science v.1619, Springer, pp. 177-193, 1999,

J2. (with A. E. Caldwell, A. B. Kahng, S. Mantik and A. Zelikovsky), "On Wirelength Estimations for Row-Based Placement", IEEE Trans. on CAD 18(9), pp. 1265-1278, 1999.
J1. (with C. J. Alpert, T. Chan, A. B. Kahng and P. Mulet), "Faster Minimization of Linear Wirelength for Global Placement" IEEE Trans. on CAD 17(1), pp. 3-13, 1998.

Refereed papers in conference proceedings

C71. (with M. D. Moffitt, A. N. Ng, and M. E. Pollack), "Constraint-driven Floorplan Repair", to apear in Proc. Design Automation Conf., San Francisco, CA, July 2006.
C70. (with R. Das and J. P. Hayes), "On-Chip Test Generation Using Linear Subspaces", to appear in Proc. European Test Symposium (ETS), Southampton, UK, May 2006.
C69. (with J. A. Roy, D. A. Papa, A. N. Ng, I. L Markov), "Satisfying Whitespace Requirements in Top-down Placement", Proc. Int'l Symp. on Physical Design (ISPD), pp. 170-177, San Jose, CA, April 2006 (invited).
C68. (with J. A. Roy and J. F. Lu), "Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement", Proc. Int'l Symp. on Physical Design (ISPD), pp. 78-85, San Jose, CA, April 2006.
C67. (with A. N. Ng, R. Aggarwal and V. Ramachandran), "Solving Hard Instances of Floorplacement",(BPA nominee), Proc. Int'l Symp. on Physical Design (ISPD), pp. 170-177, San Jose, CA, April 2006.
C66. (with D. A. Papa and P. Chong), "Utility of OpenAccess in Academic Research", Proc. Asia and South Pacific Design Conf. (ASPDAC), pp. 440-441, Yokohama, Japan 2006 (invited).

---


C65. (with K.-H. Chang and V. Bertacco), "Post-Placement Rewiring and Rebuffering by Exhaustive Search For Functional Symmetries", Proc. Int'l Conf. Computer-Aided Design (ICCAD), pp. 56-63, San Jose, CA, November 2005.
C64. (with K.-H. Chang and V. Bertacco), "Simulation-based Bug Trace Minimization with BMC-based Refinement", Proc. Int'l Conf. Computer-Aided Design (ICCAD), pp. 1045-1051, San Jose, CA, November 2005.
C63. (with S. Krishnaswamy and J. P. Hayes), "Testing Logic Circuits for Transient Faults", in Proc. IEEE Eur. Test Symp. (ETS), pp. 102-107, Tallinn, Estonia, May 2005.
C62. (with J. A. Roy, D. A. Papa, S. N. Adya, H. H. Chan, J. F. Lu, A. N. Ng), "Capo: Robust and Scalable Open-Source Min-cut Floorplacer", in Proc. Intl. Symposium on Physical Design (ISPD), pp. 224-227, San Francisco, April 2005.
C61. (with Zh. Xiu, D. A. Papa, P. Chong, A. Kuehlmann, R. A. Rutenbar), "Early Research Experience with OpenAccess Gear: An Open Source Development Environment for Physical Design," in Proc. Intl. Symposium on Physical Design (ISPD), pp. 94-100, San Francisco, April 2005 (invited).
C60. (with H. H. Chan and S. N. Adya), "Are Floorplan Representations Useful in Digital Design?", in Proc. Intl. Symposium on Physical Design (ISPD), pp. 129-136, San Francisco, April 2005.
C59. (with A. Ramani), "Automatically Exploiting Symmetries in Constraint Programming", Symmetries in Constraints (SymCon), Toronto, Canada. Lecture Notes in Computer Science, vol. 3419, p. 98, Springer, March 2005.
C58. (with A. N. Ng), "Toward High Quality Tools and Tool Flows Through High-Performance Computing", Proc. Intl. Symposium on Quality Electronic Design (ISQED), pp. 22-27, San Jose, March 2005.
C57. (with S. Krishnaswamy and J. P. Hayes), "Accurate Reliablity Evaluation and Enhancement via Probabilistic Transfer Matrices", Proc. Design Automation and Test in Europe (DATE), pp. 282 - 287, Munich, Germany, March 2005 (best paper award).
C56. (with D. Maslov), "Uniformly-switching Logic for Cryptographic Applications", to appear in Proc. Design Automation and Test in Europe (DATE), Munich, Germany, pp. 432-433, March 2005.
C55. (with F. A. Aloul, A. Ramani, and K. A. Sakallah), "Dynamic Symmetry-Breaking for Improved Boolean Optimization", Proc. Asia and South Pacific Design Autom. Conf. (ASPDAC), pp. 445-450, Shanghai, China, January 2005.
C54. (with V. S. Shende and S. S. Bullock), "`Synthesis of Quantum Logic Circuits", Proc. Asia and South Pacific Design Autom. Conf. (ASPDAC), pp. 272-275, Shanghai, China, January 2005.

---


C53. (with S. N. Adya, D. A. Papa, J. A. Roy and S. Chaturvedi), "Unification of Partitioning, Placement and Floorplanning", Intl. Conf. Computer-Aided Design (ICCAD), San Jose, CA, November 2004, pp. 550-557.
C52. (with P. T. Darga, M. H. Liffiton and K. A. Sakallah), "Exploiting Structure in Symmetry Generation for CNF," Proc. Design Autom. Conf. (DAC), San Diego, California, June 2004, pp. 518-523.
C51. (with Y. Oh, M. Mneimneh, Z. S. Andraus, and K. A. Sakallah), "AMUSE: A Minimally Unsatisfiable Subformula Extractor," Proc. Design Autom. Conf. (DAC), (BPA nominee), San Diego, California, June 2004, pp. 530-534.
C50. (A. B. Kahng and S. Reda), Proc. Great Lakes Symp. on VLSI (GLSVLSI), Boston, Massachusetts, April 2004, pp. 214-219.
C49. (with H. H. Chan), "Practical Slicing and Nonslicing Block-Packing without Simulated Annealing," Proc. Great Lakes Symp. on VLSI (GLSVLSI), Boston, Massachusetts, April 2004, pp. 282-287.
C48. (with D. A. Papa and S. N. Adya), "Constructive Benchmarking for Placement," Proc. Great Lakes Symp. on VLSI (GLSVLSI), Boston, Massachusetts, April 2004, pp. 113-118.
C47. (with V. V. Shende and S. S. Bullock), "Finding Small Two-Qubit Circuits," Proc. SPIE vol. 5436 (Conf. on Quantum Information and Computation), pp. 348-359, Orlando, Florida, April 2004.
C46. (with G. F. Viamontes and J. P. Hayes), "Graph-based Simulation of Quantum Computation in the State-vector and Density-matrix Representation," Proc. SPIE vol. 5436 (Conf. on Quantum Information and Computation), pp. 285-296, Orlando, Florida, April 2004.
C45. (with A. Ramani, F. A. Aloul and K. A. Sakallah), "Breaking Instance-Independent Symmetries in Exact Graph Coloring," Proc. Design Autom. and Test in Europe (DATE), Paris, France, February 2004, pp. 324-329.
C44. (with V. V. Shende and S. S. Bullock), "Smaller Two-Qubit Circuits for Quantum Communication and Computation," Proc. Design Autom. and Test in Europe (DATE), Paris, France, February 2004, pp. 980-985.
C43. (with S. Reda and A. B. Kahng), "Boosting: Min-cut Placement with Improved Signal Delay," Proc. Design Autom. and Test in Europe (DATE), Paris, France, February 2004, pp. 1098-1103.
C42. (with G. F. Viamontes and J. P. Hayes), "High-performance QuIDD-based Simulation of Quantum Circuits," Proc. Design Autom. and Test in Europe (DATE), Paris, France, February 2004, pp. 1354-1359.
C41. (with F. A. Aloul, A. Ramani and K. A. Sakallah), "Symmetry-Breaking for Pseudo-Boolean Formulas," Proc. Asia and South Pacific Design Autom. Conf. (ASPDAC), Yokohama, Japan, January 2004, pp. 884-887.

---


C40. (with S. N. Adya and P. G. Villarrubia), "On Whitespace and Stability in Mixed-Size Placement", Proc. Intl. Conf. on Computer-Aided Design (ICCAD), San Jose, November 2003, pp. 311-318.
C39. (with F. A. Aloul and K. A. Sakallah), "Efficient Symmetry Breaking for Boolean Satisfiability," Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), Acapulco, Mexico, August 2003, pp. 271-282.
C38. (with A. Ramani), "Combining Two Local Search Approaches to Hypergraph Partitioning," Proc. Intl. Joint Conf. on Artificial Intelligence (IJCAI), Acapulco, Mexico, August 2003, pp. 1546-1548.
C37. (with S. Bullock), "An Arbitrary Two-qubit Computation In 23 Elementary Gates Or Less," Proc. ACM/IEEE Design Automation Conf., Anaheim, CA, June 2003 (BPA nominee), pp. 324-329.
C36. (with F. A. Aloul and K. A. Sakallah), "Shatter: Efficient Symmetry-Breaking for Boolean Satisfiability", Proc. ACM/IEEE Design Automation Conf., Anaheim, CA, June 2003, pp. 836-839.
C35. (with K. N. Patel and J. P. Hayes), "Fault Testing for Reversible Circuits," Proc. IEEE VLSI Test Symposium (VTS), Napa, CA, April 2003, pp. 410-416.
C34. (with F. A. Aloul and K. A. Sakallah), "FORCE: A Fast and Easy-To-Implement Variable-Ordering Heuristic," Proc. ACM Great Lakes Symp. on VLSI (GLSVLSI), Washington, DC, April 2003, pp. 116-119.
C33. (with S. N. Adya, M. Yildiz, P. G. Villarrubia, P. N. Parakh and P. H. Madden), "Benchmarking For Large-Scale Placement and Beyond", Proc. ACM/IEEE Intl. Symp. on Physical Design (ISPD), Monterey, CA, April 2003, pp. 95-103 (invited).
C32. (with K. N. Patel) "Error-Correction and Crosstalk Avoidance in DSM Busses," Proc. System-Level Interconnect Prediction (SLIP), Monterey, CA, April 2003, pp. 9-14.
C31. (with A. B. Kahng) "The Impact of Interoperability on CAD-IP Reuse: An Academic Viewpoint", in Proc. Intl. Symp. on Quality Electronic Design (ISQED), San Jose, CA, March 2003 (invited), pp. 208-213.
C30. (with S. N. Adya) "Improving Min-cut Placement for VLSI Using Analytical Techniques," in Proc. IBM Austin Center for Advanced Studies Conference (ACAS), Austin, TX, February 2003, pp. 55-62.
C29. (with G. F. Viamontes, M. Rajagopalan and J. P. Hayes), "Gate-level Simulation of Quantum Circuits", Proc. Asia and South-Pacific Design Automation Conf., Kitayushu, Japan, January 2003, pp. 295-301.

---


C28. (with F. A. Aloul, A. Ramani and K. A. Sakallah), "Generic ILP versus Specialized 0-1 ILP: an Update" in Proc. ACM/IEEE Intl. Conf. Comp.-Aided Design (ICCAD), San Jose, CA, November 2002, pp. 450-457.
C27. (with V. V. Shende, A. K. Prasad and J. P. Hayes), "Reversible Logic Circuit Synthesis", in Proc. ACM/IEEE Intl. Conf. Comp.-Aided Design (ICCAD), San Jose, CA, November 2002, pp. 353-360.
C26. (with F. A. Aloul and K. A. Sakallah), "Efficient Gate and Input Ordering for Circuit-to-BDD Conversion", in Proc. IEEE Intl. Conf. Computer Design (ICCD), Freiburg, Germany, September 2002, pp. 64-69.
C25. (with G. F. Viamontes, M. Rajagopalan and J. P. Hayes), "High-Performance Simulation of Quantum Computation Using QuIDD", in Proc. Quantum Communication, Measurement and Computation (QCMC), July 2002, 2003, pp. 311-314.
C24. (with F. A. Aloul, A. Ramani and K. A. Sakallah), "Solving Difficult SAT Instances In The Presence of Symmetry", in Proc. ACM/IEEE Design Automation Conf., June 2002, pp. 731-736.
C23. (with S. N. Adya), "Consistent Placement of Macro-blocks Using Floorplanning and Standard-Cell Placement", Proc. ACM/IEEE Intl. Symp. on Physical Design (ISPD), April 2002, pp. 12-17.
C22. (with A. B. Kahng and S. Mantik), "Min-max Placement For Large-scale Timing Optimization", Proc. ACM/IEEE Intl. Symp. on Physical Design, April 2002, pp. 143-148.
C21. (with A. B. Kahng), "Analytical Minimization of Signal Delays in VLSI Placement", in Proc. IBM Austin Center for Advanced Studies (ACAS) Conference, February 2002, p. 62-68.
C20. (with D. B. Motter), "A Compressed Breadth-first Search For Satisfiability", Proc. ACM Workshop on Algorithm Engineering and Experimentation (ALENEX), January 2002, Lecture Notes in Computer Science, vol. 2409, Springer, pp. 29-42.

---


C19. (with F. A. Aloul and K. A. Sakallah), "Faster SAT and Smaller BDDs via Common Function Structure", in Proc. ACM/IEEE Intl. Conf. on Computer-Aided Design, 2001, pp. 443-448.
C18. (with S. N. Adya), "Fixed-outline Floorplanning Through Better Local Search", in Proc. IEEE Intl. Conf. on Computer Design (ICCD), 2001, pp. 328-334.

---


C17. (with A. E. Caldwell et al.), "GTX: The MARCO GSRC Technology Extrapolation System", in Proc. ACM/IEEE Design Automation Conf., June 2000, pp. 693-698.
C16. (with A. E. Caldwell and A. B. Kahng), "Can Recursive Bisection Alone Produce Routable Placements?", in Proc. ACM/IEEE Design Automation Conf., June 2000, pp. 731-736.
C15. (with O. Coudert, C. Meinel and E. Sentovich), "Web-based frameworks to enable CAD RD", in Proc. ACM/IEEE Design Automation Conf., Los Angeles, June 2000, p. 711 (invited).
C14. (with A. A. Kennings), "Analytical Minimization of Half-Perimeter Wirelength", in Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., Japan, January 2000, pp. 179-184 (BPA nominee).
C13. (with A. E. Caldwell and A. B. Kahng), "Improved Algorithms for Hypergraph Bipartitioning", in Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., Japan, Jan. 2000, pp. 661-666.

---


C12. (with A. E. Caldwell, A. B. Kahng and A. A. Kennings), "Hypergraph Partitioning for VLSI CAD: Methodology for Reporting, and New Results", in Proc. ACM/IEEE Design Automation Conf., June 1999, pp. 349-354.
C11. (with A. E. Caldwell and A. B. Kahng), "Hypergraph Partitioning With Fixed Vertices", in Proc. ACM/IEEE Design Automation Conf., June 1999, pp. 355-359.
C10. (with A. E. Caldwell and A. B. Kahng), "Optimal Partitioners and End-Case Placers for Standard-Cell Layout", in Proc. ACM/IEEE Intl. Symp. on Physical Design, April 1999, pp. 90-96.
C9. (with C. J. Alpert, A. E. Caldwell and A. B. Kahng), "Partitioning With Terminals: A `New' Problem and New Benchmarks", in Proc. ACM/IEEE Intl. Symp. on Physical Design, April 1999, pp. 151-157.
C8. (with R. Baldick, A. B. Kahng and A. A. Kennings), "Function Smoothing with Applications to VLSI Layout", in Proc. IEEE/ACM Asia and South Pacific Design Automation Conf., Hong Kong, Jan. 1999, pp. 225-228 (BPA nominee).

---


C7. (with A. E. Caldwell and A. B. Kahng), "Relaxed Partitioning Balance Constraints in Top-Down Placement", in Proc. IEEE Intl. ASIC Conference, Rochester, September 1998, pp. 229-232.
C6. (with A. B. Kahng et al.), "Watermarking Techniques for Intellectual Property Protection", in Proc. ACM/IEEE Design Automation Conference, San Francisco, June 1998, pp. 776-781.
C5. (with A. B. Kahng et al.), "Robust IP Watermarking Methodologies for Physical Design", in Proc. ACM/IEEE Design Automation Conference, San Francisco, 1998, pp. 782-787.
C4. (with A. E. Caldwell, A. B. Kahng, S. Mantik and A. Zelikovsky), "On Wirelength Estimations for Row-Based Placement", in Proc. ACM/IEEE Intl. Symposium on Physical Design, Monterey, April 1998, pp. 4-11.
C3. (with A. E. Caldwell, A. B. Kahng and S. Mantik), "Implications of Area-Array I/O for Row-Based Placement Methodology", in Proc. IEEE Symp. on IC/Package Design Integr., Santa Cruz, February 1998, pp. 93-98.

---


C2. (with C. J. Alpert et al.), "Quadratic Placement Revisited", in Proc. ACM/IEEE Design Automation Conference (BPA nominee), Anaheim, June 1997, pp. 752-757.
C1. (with C. J. Alpert et al.), "Faster Minimization of Linear Wirelength for Global Placement", in Proc. ACM/IEEE Intl. Symp. on Physical Design, Napa, April 1997, pp. 4-11.

Conference and workshop presentations w/o proceedings
(in most cases, refereed)

• (with K.-H. Chang, D. A. Papa, and V. Bertacco), "Fast Simulation and Equivalence Checking Using OAGear", ACM/IEEE Intl. Workshop on Logic and Synthesis (IWLS), Denver, CO, June 2006.
• (with K.-H. Chang and V. Bertacco), "Keeping Physical Synthesis Safe and Sound", ACM/IEEE Intl. Workshop on Logic and Synthesis (IWLS), Denver, CO, June 2006.
• (with S. Krishnaswamy and J. P. Hayes), "When Are Multiple Gate Errors Significant in Logic Circuits?", System Effects of Logic Soft Errors (SELSE), Urbana, IL April 2006.
• (with Y. Shi), "Simulating quantum computation by contracting tensor networks", Quantum Information and Computation (QIP), Paris, France 2006.
• (single-author), Älgebraic Structure Helps in Finding and Using Almost-Symmetries", Symmetries in Constraints (SymCon), Sitges, Spain, October 2005.
• (with K.-H. Chang and V. Bertacco), "Post-Placement Rewiring by Exhaustive Search for Functional Symmetries", ACM/IEEE Intl. Workshop on Logic and Synthesis (IWLS), pp. 469-476, Lake Arrowhead, CA, June 2005.
• (with Y. Oh, E. Ernst, and K. A. Sakallah), "Constructive Logic and Layout Synthesis Does Not Work", ACM/IEEE Intl. Workshop on Logic and Synthesis (IWLS), pp. 367-374, Lake Arrowhead, CA, June 2005.
• (with A. Ramani), "Automatically Exploiting Symmetries in Constrait Satisfaction Problems", Symmetries in Constraints (SymCon), Toronto, September 2004.
• (with K. M. Svore, A. W. Cross, A. V. Aho and I. L. Chuang), "Toward a software architecture for quantum computing design tools" Workshop on Quantum Programming Languages, July 2004, Turku, Finland.
• (with J. A. Roy and V. Bertacco), "Restoring Circuit Structure from SAT Instances", ACM/IEEE Intl. Workshop on Logic and Synthesis, Temecula, CA, June 2004, pp. 361-368.
• (with G. F. Viamontes and J. P. Hayes) "Is Quantum Search Practical?" ACM/IEEE Intl. Workshop on Logic and Synthesis, Temecula, CA, June 2004, pp. 478-485.
• (with K. N. Patel and J. P. Hayes) "Efficient Synthesis of Linear Reversible Circuits", ACM/IEEE Intl. Workshop on Logic and Synthesis, Temecula, CA, June 2004, 470-477.
• (with H. H. Chan) "Symmetries in Rectangular Block-Packing", Intl. Workshop on Symmetry in Constraint-Satisfaction Problems (SymCon) 2003, pp. 27-40.
• (with F. A. Aloul, A. Ramani and K. A. Sakallah) "Symmetry-Breaking for Pseudo-Boolean Formulas", Intl. Workshop on Symmetry in Constraint-Satisfaction Problems (SymCon) 2003, pp. 1-12.
• (with J. A. Roy) "On Sub-optimality and Scalability of Logic Synthesis Tools," ACM/IEEE Intl. Workshop on Logic and Synthesis, Laguna Beach, CA, May 2003.
• (with V. V. Shende, A. K. Prasad, K. N. Patel and J. P. Hayes) "Scalable Simplification of Reversible Logic Circuits,", ACM/IEEE Intl. Workshop on Logic and Synthesis, Laguna Beach, CA, May 2003.
• (with K. N. Patel and J. P. Hayes), "Evaluating Circuit Reliability Under Probabilistic Gate-Level Fault Models," ACM/IEEE Intl. Workshop on Logic and Synthesis, pp. 59-64, Laguna Beach, CA, May 2003.
• "An Introduction to Reversible Circuits," ACM/IEEE Intl. Workshop on Logic and Synthesis, Laguna Beach, CA, May 2003 (invited).
• (with P. Kudva) "Benchmarking Activities," ACM/IEEE Intl. Workshop on Logic and Synthesis, Laguna Beach, CA, May 2003 (invited).
• (with F. A. Aloul and K. A. Sakallah) "Logic Minimization in Symmetry-breaking for SAT", Symmetry in Constraint Satisfaction Problems (SymCon `02), Ithaca, NY, September 2002, pp. 37-47.
• (with V. V. Shende, A. K. Prasad and J. P. Hayes) "Synthesis of Optimal Reversible Logic Circuits", ACM/IEEE Intl. Workshop on Logic and Synthesis, New Orleans, LA, June 2002, pp. 125-130.
• (with F. A. Aloul and K. A. Sakallah) "Efficient Gate and Input Ordering for Circuit-to-BDD Conversion", ACM/IEEE Intl. Workshop on Logic and Synthesis, New Orleans, LA, June 2002, pp. 134-142.
• (with D. B. Motter) "Overcoming Resolution-Based Lower Bounds for SAT Solvers", ACM/IEEE Intl. Workshop on Logic and Synthesis, New Orleans, LA, June 2002, pp. 373-379.
• (with F. A. Aloul, A. Ramani and K. A. Sakallah), "PBS: A Backtrack-Search Pseudo-Boolean Solver and Optimizer" Intl. Symposium on Boolean Satisfiability (SAT), Cincinnati, OH, May 2002, pp. 346-353.
• The material of paper C23, presented at Intl. Symposium on Boolean Satisfiability (SAT), Cincinnati, OH, May 2002, pp. 338-345.
• (with D. B. Motter) "On Proof Systems Behind Efficient SAT Solvers", Intl. Symposium on Boolean Satisfiability (SAT), Cincinnati, OH, May 2002, pp. 206-213.
• (with F. A. Aloul and K. A. Sakallah), "MINCE: A Static Global Variable-Ordering for SAT and BDD", Intl. Workshop on Logic Synthesis, Lake Tahoe, CA, June 2001.
• (with P. G. Villarrubia), "Lazy Timing-Driven Placement", IBM Annual All-site Meeting, Fishkill, NY, April 2001.
• (with P. G. Villarrubia),"Methods for Top-Down Timing-Driven Placement", 2nd IBM ACAS Conference, Austin, TX, February, 2001.
• (with A. B. Kahng and A. A. Kennings), "Effective Optimization Strategies for Large-scale Placement", Sixth SIAM Conference on Optimization, Minisymp. on Optimization in Circuit Placement for VLSI, Atlanta, GA, May, 1999.
• The material of conference paper C4, presented at the ACM/AMS DIMACS workshop "Robust Communication Networks: Interconnection and Survivability", November, 1998.

Technical reports

Footnotes: