University of Cincinnati Logo

 
COMPUTER SCIENCE
THEORY and ALGORITHMS

John Franco

Personal photo - John Franco

Research Interests

Design and analysis of algorithms, probabilistic analysis of algorithms, NP-complete problems, the Satisfiability problem, approximation algorithms for NP-complete problems, mathematics in artificial intelligence Satisfiability solver design.

Biography

Publications

Probabilistic Analysis of Satisfiability Algorithms

John Franco

In Boolean Methods and Models, Yves Crama and Peter Hammer (eds.), Cambridge University Press, to appear.

Avoiding Unnecessary Calculations in Robot Navigation

Weiya Yue and John Franco

In Proc. WCECS, San Francisco, 2009, pages 718-723, Newswood Limited, Hong Kong.

A History of Satisfiability

John Franco and John Martin

In Handbook of Satisfiability, Armin Biere, Marijn Huele, Hans van Maaren, Toby Walsh (eds.), pages 3-74. IOS Press, 2009.

Workshop on Satisfiability: Assessing the Progress

John Franco, Victor Marek, Sean Weaver

U.S. Department of Defense internal publication, 2008.

View all

Projects and Activities

publications
conferences
contests
outreach
software
students

Local Environment and History

 
interesting
facts
about UC

  Donald Shell discovered the Shell Sort algorithm while working on a Masters degree in the Mathematics Department.

  Vinod Dham, chief architect of the Pentium Chip, is a graduate of Electrical Engineering at UC.

  Frank B. Brady, one of the pioneers of ILS before and during WWII and director of the introduction of ILS systems into North Atlantic routes and the European theatre of operations, studied radio and electrical engineering at UC from 1933 to 1939, working also at Crosley Radio.

  Arnold Spielberg, father of Steven Spielberg and grandfather of E.T., graduated from the old Department of Electrical Engineering in 1949. In 1953 he designed the first computerized point-of-sale system in the world for RCA. His system was tested at Higbees department store in Cleveland. Later he fathered GE's series 200 computers. Spielberg and Brady knew each other when Spielberg co-oped at Crosley.

  Joseph Strauss, an 1892 Civil Engineering graduate of UC, designed and built the Golden Gate Bridge (why did you think the bridge is painted red?). A brick from the old McMicken Hall is cemented into the base of the south anchorage.

  Michael J. Fister, holder of Bachelor's (1977) and Master's (1978) degrees in Electrical Engineering from UC, has served as Vice President at Intel and President and CEO of Cadence Design Systems, Inc.

  James Kaiser, co-pioneer of Digital Signal Processing, graduated from UC in 1952 as an Electrical Engineer.

  Brad Kuhn, a graduate of the old Department of Electrical and Computer Engineering and Computer Science, was director of the Free Software Foundation and is now the Free/Libre/Open-Source Software (FLOSS) community liaison, Technology Director of the Software Freedom Law Center (SFLC), and president of the Software Freedom Conservancy. In short, he is known as a free software activist.

  Ken Seidelmann, Director of Astrometry at the US Naval Observatory, co-discoverer of the Saturn satellite Calypso, and member of the Wide Field/Planetary Camera Team of the Hubble Space Telescope, graduated from UC with E.E., M.S., and Ph.D. degrees. The minor planet 3217 is named after him.

  John H. Hall, pioneer of low-power CMOS integrated circuit technology, and developer of Tungsten Gate Merged BiCMOS technology, graduated from UC in 1961. He is credited with saving the Minuteman project by solving a circuit problem that made the missles explode unexpectedly while flying through clouds.

  Sebastian Mauchly, father of ENIAC inventor John Mauchly, graduated with a doctorate from the University of Cincinnati.

  Albert Sabin developed the oral polio vaccine while on the faculty at UC.

  George Rieveschl Jr. discovered the first commercial antihistamine agent, known as Benadryl, while on the faculty at UC. He also holds Undergraduate, Masters, and Ph.D. degrees from UC.

  Brian Rose, a faculty member in the Classics Department, is in charge of the Troy excavations. Carl Blegen of UC established modern scientific methods in archaeology during his excavations of the Troy site which lasted six years beginning in 1932.

  Neil Armstrong, first man on the Moon, was a member of the Aerospace Engineering faculty at UC.

  William Howard Taft, the only US President to serve as Chief Justice of the United States, graduated from the UC Law School and served as its Dean.

  Sports greats Sandy Koufax and Oscar Robinson played for UC as students. Koufax came to UC on a basketball scholarship.

  Herman Schneider started cooperative education in the United States, as Dean of the College of Engineering, in 1906. To this day the College of Engineering requires all its graduates to have co-op training.

  Heather French, a former student of Design, Art, Architecture, and Planning, is Miss America for the year 2000 and Kristen Haglund became Miss America for 2008 while a student at UC's College-Conservatory for Music.

  The work of Cleveland Abbe, former director of the Cincinnati Observatory, led to the creation of the National Weather Service.

  Kathleen Battle earned Undergraduate and Masters degrees from UC's Cincinnati Conservatory of Music in the early 1970s. Recently, she was granted an honorary Doctorate as well.

  Thomas Berger, author of Little Big Man, Crazy in Berlin and the "Rhinehart" Trilogy, graduated from the College of Arts and Sciences in 1948.

  Miller Huggins, feared manager of the New York Yankees, started out with a Law Degree from UC in 1902.

  Jerry Rubin, the anti-war protestor of the 1960's, graduated from UC in 1961 before briefly attending UC, Berkeley.

ERC
MainStreet
Paul Erdos
NIT
Ladies on Campus
Oscar Robinson