Department
and
 |
John Franco
|
|
|
John Franco
|
I received a B.S. in Electrical Engineering from the City College of New York in 1969. During my years as a student at CCNY I became Vice Chancellor of the Sigma Alpha honor/service society and President of the CCNY chapter of Eta Kappa Nu. I was the recipient of the CCNY Engineering Alumni Award in 1969. From 1969 to 1975 I was a member of technical staff in the Digital Signal Processing group at Bell Laboratories in Holmdel, New Jersey. During that time I earned a M.S. in Electrical Engineering from Columbia University in New York. In 1981 I received a Ph.D. in Theoretical Computer Science from Rutgers University in New Brunswick, New Jersey. I have served on the faculties of Case Western Reserve University and Indiana University before coming to the University of Cincinnati in 1990. I am a member of INFORMS, ACM, and SIAM.
Family Album: [John] [Suzanne] [Vanessa] [Veronica]
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, environmental software.
A Research Summary of my projects is available.
I am a member of the Society for Industrial and Applied Mathematics (SIAM), the Institute for Operations Research and the Management Sciences (INFORMS), and the Association for Computing Machinery (ACM).
Recent and Selected Publications
J. Franco, and R. Swaminathan.
Toward a good algorithm for determining the unsatisfiability of
propositional formulas.
Submitted.
J. Franco.
Results related to threshold phenomena research in Satisfiability:
lower bounds.
To appear in Theoretical Computer Science.
J. Franco.
Some interesting research directions in Satisfiability.
To appear in Annals of Mathematics and Artificial Intelligence.
J. Franco, and A. Van Gelder.
A perspective on certain polynomial time solvable classes of Satisfiability.
To appear in Discrete Applied Mathematics.
J. Franco.
Finding optimal boolean classifiers.
In Approximation and Complexity in Numerical Optimization: Continuous and
Discrete Problems from the series Nonconvex Optimization and its
Applications Vol. 42, P. Pardalos (Ed.), Kluwer, 2000.
J. Franco, J. Goldsmith, J. Schlipf, E. Speckenmeyer, and R. Swaminathan.
An algorithm for the class of pure implicational formulas.
Discrete Applied Mathematics 96-97:89-106, 1999.
J.W. Rosenthal, J.M. Plotkin, J. Franco.
The probability of pure literals.
Journal of Computational Logic 9:501-513, 1999.
J. Franco, and R. Swaminathan.
Average case results for satisfiability algorithms under the random
clause model.
Annals of Mathematics and Artificial Intelligence 20:357-391, 1997.
J. Gu, P.W. Purdom, J. Franco, and B. Wah.
Algorithms for the Satisfiability problem: a survey.
DIMACS Series on Discrete Mathematics and Theoretical Computer
Science 35:19-151, American Mathematical Society, 1997.
K. Berman, J. Franco, and J. Schlipf.
Unique satisfiability for Horn sets can be solved in nearly linear
time.
Discrete Applied Mathematics 60:77-91, 1995.
F. Annexstein, and J. Franco.
Work-preserving emulations of shuffle-exchange networks by linear
arrays.
Discrete Applied Mathematics 60:13-23, 1995.
J. Schlipf, F. Annexstein, J. Franco, and R. Swaminathan.
On finding solutions to extended Horn formulas.
Information Processing Letters 54:133-137, 1995.
K. Berman, J. Franco, and J. Schlipf.
Computing the well-founded semantics faster .
Lecture Notes in Artificial Intelligence 926:113-126, 1995.
J. Franco.
On the occurrence of null clauses in random instances of
satisfiability.
Discrete Applied Mathematics 41:203-209, 1993.
J. Franco, J. M. Dunn, and W. H. Wheeler.
Recent work at the interface of logic, combinatorics, and computer
science.
Annals of Mathematics and Artificial Intelligence 6:1-16, 1992.
Special issue on Logic and Combinatorics, J. Franco, J.M. Dunn, and
W.H. Wheeler, editors.
J. Franco.
Probabilistic analysis of algorithms for stuck-at test generation
in PLAs.
Lecture Notes in Control and Information Sciences No. 174, 1992.
Springer-Verlag, publisher.
P. Celis, and J. Franco.
Average case analysis of hashing with lazy deletions.
Information Sciences 62:13-26, 1992.
J. Franco.
Elimination of infrequent variables improves average case
performance of satisfiability algorithms.
SIAM Journal on Computing 20:1119-1127, 1991.
J. Franco, D. P. Friedman, and S. D. Johnson.
Multi-way streams in Scheme.
Computer Languages 15:109-125, 1990.
M. T. Chao, and J. Franco.
Probabilistic analysis of a generalization of the unit clause selection
heuristic for the k-satisfiability problem.
Information Sciences 51:289-314, 1990.
J. Franco, and Y. C. Ho.
Probabilistic performance of a heuristic for the satisfiability
problem.
Discrete Applied Mathematics 22:35-51, 1988.
M. T. Chao, and J. Franco.
Probabilistic analysis of two heuristics for the 3-satisfiability
problem.
SIAM Journal on Computing 15:1106-1118, 1986.
J. Franco.
On the probabilistic performance of algorithms for the satisfiability
problem.
Information Processing Letters 23:103-106, 1986.
J. Franco, and M. Paull.
Probabilistic analysis of the Davis-Putnam procedure for solving
satisfiability.
Discrete Applied Mathematics 5:77-87, 1983.
Recent and Selected Major Conferences
Past Results in Satisfiability Research, 7th International Symposium
on Math and Artificial Intelligence, Ft. Lauderdale, Florida (January,
2000).
Thresholds and Algorithms for Satisfiability, topical Conference
on NP-Hardness and Phase Transitions. The Abdus Salam
International Centre for Theoretical Physics, Trieste, Italy
(August, 1999 - invited).
Finding Optimal Boolean Classifiers, conference on
Approximation and Complexity in Numerical Optimization:
Continuous and Discrete Problems, Center for Applied Optimization,
University of Florida (March, 1999 - invited).
Finding Optimal Boolean Classifiers, 2nd Workshop on
Satisfiability, University of Paderborn, Germany (May, 1998 - invited).
Relative size of certain polynomial time solvable subclasses of
satisfiability, DIMACS Randomization Methods in Algorithm Design
Workshop, Princeton University (December, 1997 - invited).
Relative size of certain polynomial time solvable subclasses of satisfiability, 16th International Symposium on Mathematical Programming, Lausanne, Switzerland (September, 1997 - invited).
An improved algorithm for determining the falsifiability of implication
logic, with R. Swaminathan, 4th International Symposium on Mathematics
and Artificial Intelligence, Ft. Lauderdale, Florida
(January, 1996 - invited).
Computing the well-founded semantics faster, with K. Berman and
J. Schlipf, 14th European Symposium on Operations Research,
Jerusalem, Israel (July, 1995 - invited).
Computing well-founded semantics faster, with K. Berman and
J. Schlipf, INFORMS annual meeting, New Orleans, Louisiana
(November, 1995 - invited).
On finding solutions to extended Horn sets, J. Schlipf was
the speaker, Timberline conference on the interface between OR and AI,
Portland, Oregon (April, 1995).
Average case results for Satisfiability under the random-clause-width
model, 15th International Symposium on Mathematical Programming,
University of Michigan, Ann Arbor (August 1994 - invited).
Improved average case results for the Satisfiability problem,
3rd International Symposium on Mathematics and Artificial Intelligence,
Ft. Lauderdale, Florida (January, 1994 - invited).
Environmental decision support systems. with Jack Coleman and
William Wee, PSAM-II, San Diego, California (March, 1994).
Integrated Computer Assisted Site Evaluation (ICASE): a data
visualization system for characterization of hazardous waste sites,
with Lew Rossman, and Kevin Savage, National Association of Remedial
Project Managers, 8th Annual Meeting, Seattle, Washington (1993).
A data visualization system for bioremediation analysis,
with Lew Rossman, and Kevin Savage, USEPA Symposium on Bioremediation of
Hazardous Wastes: Research, Development, and Field Evaluation, Dallas, Texas
(1993).
Graphical Remedial Assessment and Cost Evaluation, EDUCOM '93,
Cincinnati, Ohio (October, 1993).
Distributed implementation of algorithms for Satisfiability problems,
with Fred Annexstein, R. Swaminathan, and Humberto Ortiz Zuazaga, DIMACS
challenge workshop, Rutgers, New Jersey (October, 1993).
Boolean Satisfiability, with R. Swaminathan, ORSA/TIMS Annual
Meeting, Chicago (May, 1993).
Graphical Remedial Assessment and Cost Evaluation (GRACE):
A Hydrologic and Economic-Based Environmental Design Tool, with Lawrence
Murdoch, Koustubh Jha, Kevin Savage, and James Uber,
104th National Annual Meeting of the Geological Society of America,
Cincinnati (October, 1992).
Unique Satisfiability of Horn sets can be solved in nearly linear time,
Dagstuhl workshop on Computer Science Logic, Wadern-Dagstuhl,
Germany (July, 1992 - invited).
Graphical remedial assessment and cost evalutation,
Third Annual Pittsburgh Hazardous Waste and Hazardous Materials
Management Conference, Pittsburgh, PA, (May, 1992).
Alogrithms for Satisfiability, Workshop on Logic and
Complexity, Prague, Czechoslovakia, (July, 1991).
Satisfiability Algorithms, 3rd IFORS Conference, Athens,
Greece, (June, 1990 - invited).
The Satisfiability Problem, 14th Symposium on Operations Research,
Ulm, Germany, (September, 1989 - invited).
Probabilistic analysis of the unit clause and maximum occurring
literal selection heuristics for the 3-Satisfiability problem,
Conference of Approximately Solved Problems, Columbia University,
New York, (1985).
An approximation algorithm for the maximum independent set
problem in cubic planar graphs, Conference of Approximately Solved
Problems, Columbia University, New York, (1985).
Recent and Selected Workshop Invitations
4th Workshop on Satisfiability, Cincinnati, Ohio, USA (Spring, 2002 - co-organizer).
Workshop on Next generation SAT Solvers, Cincinnati, Ohio, USA (Spring, 2001 - co-organizer).
3rd Workshop on Satisfiability, Renesse, The Netherlands (Spring, 2000 - co-organizer).
Randomization Methods in Algorithm Design Workshop, Fields
Institute, Toronto, Canada (Spring, 2000).
DIMACS Randomization Methods in Algorithm Design Workshop, Rutgers
University, Piscataway, New Jersey, USA (Fall, 1999).
Topical Conference on NP-hardness and Phase Transitions, Abdus Salam
International Centre for Theoretical Physics, Trieste, Italy (Summer, 1999).
2nd Workshop on Satisfiability, Paderborn, Germany (Spring, 1998 - co-organizer).
DIMACS Randomization Methods in Algorithm Design Workshop, Princeton
University, Princeton, New Jersey, USA (Spring, 1997).
DIMACS workshop on the Satisifability Problem, DIMACS, Rutgers
University, New Jersey (April, 1996).
Logic and Computational Complexity, Indianapolis, Indiana,
(October 1994).
15th International Symposium on Mathematical Programming, University
of Michigan, Ann Arbor (August 1994 - session chair).
3rd International Symposium on Artificial Intelligence and Mathematics,
Ft. Lauderdale, Florida (January, 1994 - session chair).
Workshop on New Environmental Software, Lawrence Livermore Laboratories,
Lawrence, California (November, 1992).
Computer Science Logic, Dagstuhl, Germany, (July, 1992).
7th Advanced Research Institute in Discrete Applied Mathematics (ARIDAM),
New Brunswick, New Jersey, (May, 1992).
6th Advanced Research Institute in Discrete Applied Mathematics (ARIDAM),
New Brunswick, New Jersey, (May, 1991).
First IFIP-TC WG 7.6 Conference on optimization-based computer aided
modelling and design, The Netherlands, (April, 1991).
5th Advanced Research Institute in Discrete Applied Mathematics (ARIDAM),
New Brunswick, New Jersey, (May, 1990).
Workshop on Boolean Functions, Propositional Logic and AI Systems,
Ulm, W. Germany, (September, 1989 - co-organizer).
Workshop on Mathematical Methods in Artificial Intelligence,
Ulm, W. Germany, (December, 1988).
Recent and Selected Invited Talks
To be announced, DIMACS workshop on the Satisfiability problem,
Rutgers University, New Jersey (April, 1996).
An improved algorithm for determining the falsifiability of implication
logic, 4th International Symposium on Mathematics and Artificial
Intelligence, Ft. Lauderdale, Florida (January, 1996).
Computing well-founded semantics faster,
INFORMS Annual Meeting, New Orleans, Louisiana (November, 1995).
Computing the well-founded semantics faster,
14th European Symposium on Operations Research, Jerusalem, Israel
(July, 1995).
Verifying the unsatisfiability of 3-SAT instances efficiently with
high probability, Carnegie-Mellon University, seminar series,
Pittsburg, Pennsylvania (December, 1994).
Survey of Satisfiability average case results using the random
clause-width model, 15th International Symposium on Mathematical
Programming (August, 1994).
A good algorithm for verifying unsatisfiabilit of Boolean
expressions, 3rd International Symposium on Mathematics and Artificial
Intelligence, Ft. Lauderdale, Florida (January, 1994).
GRACE, Air Force Institute of Technology, seminar series, Wright
Paterson Air Force Base (June, 1993).
Boolean Satisfiability, TIMS/ORSA Annual Meeting, Chicago
(May, 1993).
Unique Satisfiability for Horn sets can be solved in nearly linear
time, Dagstuhl workshop on Computer Science Logic, Wadern-Dagstuhl,
Germany (July, 1992).
Unique Satisfiability for Horn sets can be solved in nearly linear
time, Advanced Research Institute for Discrete Applied Mathematics
(ARIDAM) VII, RUTCOR, Rutgers University, New Jersey (June, 1992).
A work-preserving emulation of the Shuffle-Exchange architecture
by a line of processors, University of Milan, (July, 1991).
A Work-Preserving Emulation of the Shuffle-Exchange Architecture
by a Line of Processors, Advanced Research Institute for Discrete Applied
Mathematics (ARIDAM) VI, RUTCOR, Rutgers University, New Jersey
(May, 1991).
Probabilistic Analysis of Satisfiability Algorithms, IFIP WG7.6,
Den Haag, Holland (April, 1991).
Probabilistic Analysis of Satisfiability Algorithms, Department of
Computer Science, University of Duisburg, Germany (August, 1990).
Probabilistic Analysis of Satisfiability Algorithms, European
Computer Research Center, Munich, Germany (August, 1990).
Elimination of Infrequent Variables Improves the Average Performance
of Satisfiability Algorithms, IFORS Biannual Conference, Athens,
Greece (June, 1990).
Elimination of Infrequent Variables Improves the Average Performance
of Satisfiability Algorithms, Advanced Research Institute for Discrete
Applied Mathematics (ARIDAM) V, RUTCOR, Rutgers University,
New Jersey (May, 1990).
Probability in Proof Theory, Operations Research Department, Case
Western Reserve University, Cleveland, Ohio (October, 1989).
Probability in Proof Theory, 14th Symposium on Operations Research,
Ulm, Germany (September, 1989).
Analysis of Algorithms for Satisfiability Problems, Workshop on
Boolean Functions, Propositional Logic, and AI Systems, at the Research
Institute for Applied Knowledge Processing, Ulm, Germany (September 4, 1989).
Lectures in Scheme Research Institute for Applied Knowledge
Processing, Ulm, Germany (Julu-August, 1989).
Probability in Proof Theory at the Department of Statistics,
University of Rome, Rome, Italy (July 21, 1989).
Probability in Proof Theory at the Department of Computer Science,
University of Milan, Milan, Italy (July 17, 1989).
Probability in Proof Theory at the Department of Computer Science,
Universitat Dortmund, Dortmund, Germany (July 11, 1989).
Probability in Proof Theory at The Seminar for Natural Language
Processing at University of Tuebingen, Tuebingen, Germany (June 30, 1989).
Probabilistic Analysis of Algorithms for VLSI Testing and Design,
1989 CORS/TIMS/ORSA Annual Meeting, Vancouver, Canada (May, 1989).
Probabilistic Analysis of Algorithms for the Satisfiability Problem,
at Rutgers University, New Brunswick, New Jersey (January, 1989).
Probabilistic Analysis of Algorithms for the Satisfiability Problem,
at the Workshop on Mathematical Methods in Artificial Intelligence,
Ulm, West Germany (December, 1988).
Probabilistic Analysis of Algorithms for CNF Satisfiability,
at ATT Bell Laboratories, Murray Hill, New Jersey (May, 1988).
Awards
Department of Defense, Satisfiability (SAT) Algorithm Research
And Development To Enhance Formal Verification Tools,
John Franco, Principal Investigator, and John Schlipf. 7/1/99-6/30/01,
$493,185.
USENIX, Usenix Scholarship,
John Franco, Principal Investigator, and Brad Kuhn. 1999/2000, $21,269.
Kuhn acquired the Scholarship on his own, with small help from me.
USEPA, Graphical Remedial Assessment and Cost Evaluation,
John Franco, Principal Investigator, 10/1/94-10/1/95, $36,400
- administered through CERL.
US Army Corps of Engineers, A GRACE interface for GRASS,
John Franco and Humberto Zuazaga, 3/1/94-2/31/95, $75,000.
Office of Naval Research, N00014-94-1-0382, Complexity of Algorithms
for Problems in Propositional Logic, John Franco and John Schlipf,
Principal Investigators, 1/1/94-3/31/97, $260,000.
EDUCOM/Ohio Board of Regents, GRACE equipment grant, John V. Franco,
6/1/92-6/1/93, $10,000.
USEPA 68-C9-0031;WA2-33, Graphical Remedial Assessment and Cost
Evaluation, Kevin Savage, Lawrence Murdoch, and John Franco, Principal
Investigators, 1/1/92-10/1/93, $61,400.
USEPA 68-C9-0031;WA2-5, Computer Assisted Site Evaluation: System
Development and Technical Assistance, John Franco, Elizabeth Spencer,
and Kevin Savage, Principal Investigators, 10/1/91-10/1/93, $375,000.
USEPA 68-C9-0031;WA2-1, Computer Assisted Analysis of Trench Design,
John Franco, Larry Murdoch, and James Uber, Principal Investigators,
10/1/91-10/1/92, $22,000.
FAW-Ulm, Germany, Scientist in Residence, Summers, 1989, 1990, 1991.
AFOSR 89-0186, Data Compilation: It's Design and Analysis,
John Franco and Daniel P. Friedman, Principal Investigators,
12/15/88-5/30/90, $109,000.
AFOSR 84-0372, Probabilistic Analysis of Algorithms For NP-Complete
Problems, John Franco, Principal Investigator, 9/30/84-9/30/89, $261,000.
AFOSR 82-0331, Probabilistic Analysis of Algorithms for NP-Complete
Problems, John Franco, Principal Investigator, 9/1/82-8/31/84, $99,000.
Editing
Satisfiability Algorithms, special issue of
Discrete Applied Mathematics, J. Franco, H. van Maaren,,
E. Speckenmeyer, and H. K. Büning, in preparation.
Satisfiability Algorithms, special issue of
Discrete Applied Mathematics, J. Franco, G. Gallo,
E. Speckenmeyer, and H. K. Büning, Volume 10 in the series Topics
in Discrete Mathematics, Elsevier, 2000.
Logic in Computer Science, special issue of Annals of Mathematics
and Artificial Intelligence, E. Boros, J. Franco, E.C. Freuder,
M.C. Golumbic, R. Greiner, E. Mayoraz (eds.), Volume 24, J.C. Baltzer, 1998.
Logic and Combinatorics, special issue of Annals of
Mathematics and Artificial Intelligence, Volume 6, J.C. Baltzer, 1992,
with M. Dunn and W. Wheeler.
Books
Algorithms for the Satisfiability Problem, J. Gu, P.W. Purdom,
J. Franco, and B. Wah, Cambridge University Press, to appear.
Analysis of Algorithms for Monotonic and Non-monotonic Reasoning,
J. Franco, and J. Schlipf, SIAM Press, to appear.
News Items Workshop on Satisfiability.
Early May, 1996 in Siena, Italy. Joint with E. Speckenmeyer
(Cologne), G. Gallo (Pisa), H. K. Büning (Paderborn). Covered
most aspects of propositional satisfiability including algorithms,
probabilistic and empirical analysis, special subclasses. Selected
papers will be published in a special issue of Discrete Applied
Mathematics. See
| Announcement | for the workshop announcement including participants. |
| Schedule | for the schedule of talks. |
| Abstracts | for extended abstracts (will be continually updated). |
| Open Problems | for open problems raised at the workshop (continually updated). |
DIMACS Workshop on Satisfiability, March, 1996. Organized by
Jun Gu, Ding-Zu Du, Panos Pardalos. For more information see the
SAT Workshop Web page.
2nd Workshop on
Satisfiability. Early May, 1998 in Paderborn, Germany. Joint with
E. Speckenmeyer (Cologne), G. Gallo (Pisa), H. K. Büning
(Paderborn). Like its predecessor mentioned above, covered most
aspects of propositional satisfiability including algorithms,
probabilistic and empirical analysis, special subclasses.
3rd Workshop on
Satisfiability. Early May, 2000 in Renesse, The Netherlands.
Joint with E. Speckenmeyer (Cologne), H. van Maaren, H.K. Büning
(Paderborn). Like its two predecessors mentioned above, covered most aspects
of propositional satisfiability including algorithms, probabilistic and
empirical analysis, special subclasses.
5th International Symposium on the Theory and Applications of
Satisfiability Testing. Early May, 2002 at the University of
Cincinnati, Cincinnati, Ohio. Joint with Henry Kautz (U. Washington),
Hans Kleine Büning (U. Paderborn),
Hans van Maaren (U. Delft),
Bart Selman (Cornell),
Ewald Speckenmeyer (U. Cologne).
Like its four predecessors mentioned above, this conference will cover most
aspects of propositional satisfiability including algorithms, probabilistic
and empirical analysis, special subclasses, as well as a special mini-workshop
on quantified boolean formulas.
SIGACT Theoretical Computer Science Listing (Rolodex)
Theoretical Computer Science Genealogy
UCLID
Ohio Link
UC Libraries
Encyclopedia Britannica
Last modified: October 2, 2000
Since June 21, 1996
Counter courtesy of the Web Counter, http://www.digits.com