Publications

This page lists journal articles, invited articles, and conference, workshop, and miscellaneous papers.  Last updated September 2013. 

(Jump to Gregory Sorkin's home page.)

Journal articles

  • Efficient algorithms for three-dimensional axial and planar random assignment problems.
    Alan Frieze and Gregory B. Sorkin.
    Random Structures Algorithms. To appear.
    [ preprint.pdf ]

  • A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.
    Serge Gaspers and Gregory B. Sorkin.
    J. Comput. Syst. Sci., 78:305-335, 2012.
    [ DOI ]

  • First-passage percolation on a ladder graph, and the path cost in a VCG auction.
    Abraham Flaxman, David Gamarnik, and Gregory B. Sorkin.
    Random Structures Algorithms, 38:350-364, May 2011.
    [ DOI ]

  • Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function.
    Alexander D. Scott and Gregory B. Sorkin.
    ACM Trans. Alg., 5(4):45:1-27, October 2009.
    [ preprint.pdf | DOI ]

  • A tight bound on the collection of edges in MSTs of induced subgraphs.
    Gregory B. Sorkin, Angelika Steger, and Rico Zenklusen.
    J. Combinatorial Theory, Series B, 99(2):428-435, March 2009.
    [ DOI ]

  • Robust reductions from ranking to classification.
    Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Gregory B. Sorkin.
    Machine Learning, 72(1-2):139-153, August 2008.
    [ DOI ]

  • Linear-programming design and analysis of fast algorithms for Max 2-CSP.
    Alexander D. Scott and Gregory B. Sorkin.
    Discrete Optimization, 4(3-4):260-287, 2007.
    [ DOI ]

  • A note on random 2-SAT with prescribed literal degrees.
    Colin Cooper, Alan Frieze, and Gregory B. Sorkin.
    Algorithmica, 48(3):249-265, July 2007.
    [ DOI ]

  • The probabilistic relationship between the assignment and traveling salesman problems.
    Alan Frieze and Gregory B. Sorkin.
    SICOMP, 36(5):1435-1452, 2007.
    [ DOI ]

  • Vehicle routing and staffing for sedan service.
    Oktay Günlük, Tracy Kimbrel, Laszlo Ladanyi, Baruch Schieber, and Gregory B. Sorkin.
    Transportation Science, 40:313-326, 2006.
    [ preprint.pdf | DOI ]

  • Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time.
    Alexander D. Scott and Gregory B. Sorkin.
    Comb. Probab. Comput., 15(1-2):281-315, 2006. ISSN 0963-5483.
    [ preprint.pdf | DOI ]

  • Embracing the giant component.
    Abraham Flaxman, David Gamarnik, and Gregory B. Sorkin.
    Random Structures Algorithms, 27(3):277-289, October 2005.
    [ preprint.ps | DOI ]

  • Strings with maximally many distinct subsequences and substrings.
    Abraham Flaxman, Aram W. Harrow, and Gregory B. Sorkin.
    Electron. J. Combin., 11:Research Paper 8, 10 pp. (electronic), 2004. ISSN 1077-8926.
    [ .html | .pdf ]

  • A two-variable interlace polynomial.
    Richard Arratia, Béla Bollobás, and Gregory B. Sorkin.
    Combinatorica, 24(4):567-584, 2004.
    [ DOI ]

  • The interlace polynomial of a graph.
    Richard Arratia, Béla Bollobás, and Gregory B. Sorkin.
    J. Combinatorial Theory, Series B, 92(2):199-233, November 2004. Special issue dedicated to Professor W.T. Tutte.
    [ DOI ]

  • Random MAX SAT, random MAX CUT, and their phase transitions.
    Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, and Gregory B. Sorkin.
    Random Structures Algorithms, 24(4):502-545, 2004. ISSN 1042-9832.
    [ preprint.pdf | preprint.html | DOI ]

  • Exact expectations and distributions for the random assignment problem.
    Sven Erick Alm and Gregory B. Sorkin.
    Combin. Probab. Comput., 11(3):217-248, 2002. ISSN 0963-5483.
    [ preprint.pdf | DOI ]

  • Gadgets, approximation, and linear programming.
    Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson.
    SIAM J. Comput., 29(6):2074-2097, 2000.
    [ DOI | .html | .pdf ]

  • Euler circuits and DNA sequencing by hybridization.
    Richard Arratia, Béla Bollobás, Don Coppersmith, and Gregory B. Sorkin.
    Discrete Applied Mathematics, 104(1-3):63-96, 2000.
    [ DOI ]

  • Constructive bounds and exact expectations for the random assignment problem.
    Don Coppersmith and Gregory B. Sorkin.
    Random Structures Algorithms, 15(2):113-144, 1999. ISSN 1042-9832.
    [ DOI ]

  • The Metropolis algorithm for graph bisection.
    Mark Jerrum and Gregory B. Sorkin.
    Discrete Applied Mathematics, 8(1-3):155-175, 1998.
    [ DOI ]

  • Constructing computer virus phylogenies.
    Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, and Gregory B. Sorkin.
    Journal of Algorithms, 26(1):188-208, 1998.
    [ DOI ]

  • Neural networks for computer virus recognition.
    Gerald J. Tesauro, Jeffrey O. Kephart, and Gregory B. Sorkin.
    IEEE Expert: Intelligent Systems and Their Applications, 11(4):5-6, 1996.
    [ DOI ]

  • Efficient simulated annealing on fractal energy landscapes.
    Gregory B. Sorkin.
    Algorithmica, 6:367-418, 1991.
    [ DOI ]

  • Applying harmonic balance to almost-periodic circuits.
    Kenneth S. Kundert, Gregory B. Sorkin, and Alberto Sangiovanni-Vincentelli.
    IEEE Transactions on Microwave Theory and Techniques, 36(2):366-378, 1988.
    [ DOI ]

  • Asymptotically perfect trivial global routing: A stochastic analysis.
    Gregory B. Sorkin.
    IEEE Transactions on Computer-Aided Design, CAD-6(5):820-827, 1987.
    [ DOI ]

  • The enumeration of nonhomeomorphic graphs by edges.
    Gregory Sorkin.
    Annals of Discrete Mathematics, 9:249-252, 1980.
    [ DOI ]


Invited articles

  • Punch-operation and die optimization for ceramic-module production.
    Gregory Sorkin.
    IBM: Innovation Matters, 2005. No longer on IBM web site; see instead here.

  • Some notes on random satisfiability.
    Gregory B. Sorkin. In Kathleen Steinhöfel, editor, Stochastic Algorithms: Foundations and Applications; Proceedings of SAGA 2001 (Berlin, 2001), Number 2264 in LNCS, pages 117-130. Springer, 2001.

  • Fighting computer viruses.
    Jeffrey O. Kephart, Gregory B. Sorkin, David M. Chess, and Steve R. White.
    Scientific American, pages 88-93, 1997.
    [ DOI | http ]

  • Simulated annealing.
    Scott Kirkpatrick and Gregory B. Sorkin. In M. Arbib, editor, Handbook of Brain Theory and Neural Networks, pages 876 - 879. MIT Press, Cambridge, MA, 1995. ISBN 0262011484.



Conference, workshop, and miscellaneous papers

  • Average-case analyses of Vickrey costs.
    Prasad Chebolu, Alan Frieze, Páll Melsted, and Gregory B. Sorkin.
    In APPROX and RANDOM 2009, volume 5687 of
    Lecture Notes in Comput. Sci., pages 434-447. Springer, Berlin, 2009. Proceedings of 13th Intl. Workshop on Randomization and Computation (RANDOM 2009), Berkeley, CA, USA, Aug 2009.

  • Conditional probability tree estimation analysis and algorithms.
    Alina Beygelzimer, John Langford, Yuri Lifshits, Gregory B. Sorkin, and Alexander L. Strehl.
    In Proceedings of Uncertainty in Artificial Intelligence (UAI 2009), 2009.
    [ preprint.pdf ]

  • A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.
    Serge Gaspers and Gregory B. Sorkin.
    In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (New York, NY, 2009), pages 606-615. ACM, New York, 2009.
    [ preprint.pdf | http ]

  • Robust reductions from ranking to classification.
    Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Gregory B. Sorkin.
    In Prooceedings of the 20th Annual Conference on Learning Theory, COLT 2007, San Diego, CA, USA, June 13-15, 2007, volume 4539 of
    Lecture Notes in Computer Science, pages 604-619. Springer, 2007. ISBN 978-3-540-72925-9.

  • First-passage percolation on a width-2 strip and the path cost in a VCG auction.
    Abraham Flaxman, David Gamarnik, and Gregory B. Sorkin.
    In Paul G. Spirakis, Marios Mavronicolas, and Spyros C. Kontogiannis, editors, Proceedings of the Second International Workshop on Internet and Network Economics, WINE 2006, Patras, Greece, December 15-17, 2006, volume 4286 of
    LNCS, pages 99-111. Springer, 2006. ISBN 3-540-68138-8.
    [ preprint.pdf | http ]

  • An LP-designed algorithm for constraint satisfaction.
    Alexander D. Scott and Gregory B. Sorkin.
    In Proc. 14th Annual European Symposium on Algorithms, ESA, (Zürich, Switzerland, 2006), volume 4168 of
    Lecture Notes in Comput. Sci., pages 588-599. Springer, September 2006. ISBN 3-540-38875-3.
    [ http ]

  • Embracing the giant component.
    Abraham Flaxman, David Gamarnik, and Gregory B. Sorkin.
    In Proceedings of LATIN 2004 (Latin American Theoretical INformatics), April 2004.

  • Random Max Sat, random Max Cut, and their phase transitions.
    Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi, and Gregory B. Sorkin.
    In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), ACM, New York, 2003.

  • Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances.
    Alexander D. Scott and Gregory B. Sorkin.
    In Approximation, randomization, and combinatorial optimization, volume 2764 of
    Lecture Notes in Comput. Sci., pages 382-395. Springer, Berlin, 2003. Proceedings of 7th International Workshop on Randomization and Approximation Techniques in Computer Science, Princeton, NJ, USA, August 2003.

  • On the expected incremental cost of a minimum assignment.
    Don Coppersmith and Gregory B. Sorkin.
    In Béla Bollobás, editor, Contemporary Combinatorics, Number 10 in Bolyai Society Mathematical Studies, chapter 8. Springer, 2002.

  • A note on random 2-SAT with prescribed literal degrees.
    Colin Cooper, Alan Frieze, and Gregory B. Sorkin.
    In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2002), pages 316-320. ACM, New York.

  • The probabilistic relationship between the assignment and traveling salesman problems.
    Alan Frieze and Gregory B. Sorkin.
    In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), pages 652-660. ACM, New York, 2001.

  • Optimal myopic algorithms for random 3-SAT.
    Dimitris Achlioptas and Gregory B. Sorkin.
    In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, (Redondo Beach, CA, 2000), pages 590-600. IEEE Comput. Soc. Press, Los Alamitos, CA, 2000.

  • The interlace polynomial: A new graph polynomial.
    Richard Arratia, Béla Bollobás, and Gregory B. Sorkin.
    In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pages 237-245. ACM, New York, 2000.

  • Constructive bounds and exact expectations for the random assignment problem.
    Don Coppersmith and Gregory B. Sorkin.
    In Randomization and approximation techniques in computer science (Barcelona, 1998), volume 1518 of
    Lecture Notes in Comput. Sci., pages 319-330. Springer, Berlin, 1998.

  • Blueprint for a computer immune system.
    Jeffrey O. Kephart, Gregory B. Sorkin, Morton Swimmer, and Steve R. White.
    In Dipankar Dasgupta, editor, Artificial Immune Systems and Their Applications, Springer, 1998. ISBN 3540643907.

  • Biologically inspired defenses against computer viruses.
    Jeffrey O. Kephart, Gregory B. Sorkin, William C. Arnold, David M. Chess, Gerald J. Tesauro, and Steve R. White.
    In R.S. Michalski, L. Bratko, and M. Kubat, editors, Machine Learning and Data Mining: Methods and Applications, chapter 13. Wiley, 1997.

  • An immune system for cyberspace.
    Jeffrey O. Kephart, Gregory B. Sorkin, and Morton Swimmer.
    In Proceedings of the 1997 IEEE International Conference on Systems, Man, and Cybernetics, 1997.

  • Blueprint for a computer immune system.
    Jeffrey O. Kephart, Gregory B. Sorkin, Morton Swimmer, and Steve R. White.
    In Proceedings of the 1997 Virus Bulletin International Conference, 1997.

  • Gadgets, approximation, and linear programming.
    Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson.
    In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages 617-626. 1996.

  • Constructing computer virus phylogenies.
    Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, and Gregory B. Sorkin.
    In Combinatorial pattern matching (Laguna Beach, CA, 1996), volume 1075 of
    Lecture Notes in Comput. Sci., pages 253-270. Springer, Berlin, 1996.

  • Automated analysis of computer viruses.
    William C. Arnold and Gregory B. Sorkin.
    In Proceedings of the 1996 Virus Bulletin International Conference, pages 149-159. 1996.

  • Biologically inspired defenses against computer viruses.
    Jeffrey O. Kephart, Gregory B. Sorkin, William C. Arnold, David M. Chess, Gerald J. Tesauro, and Steve R. White.
    In IJCAI-95: Proceedings of the International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1995.

  • Grouping related computer viruses into families.
    Gregory B. Sorkin.
    In Proceedings of the IBM Security ITS, 1994.

  • Generic disinfection of programs infected with a computer virus.
    Jeffrey O. Kephart and Gregory B. Sorkin.
    In Proceedings of the IBM Security ITS, 1994.

  • A neural network virus detector.
    Jeffrey O. Kephart, Gregory B. Sorkin, and Gerald J. Tesauro.
    In Proceedings of the IBM Security ITS, 1994.

  • Algorithmic analysis of computer viruses.
    Gregory B. Sorkin.
    In Proceedings of the IBM Security ITL, 1993.

  • Simulated annealing for graph bisection.
    Mark Jerrum and Gregory B. Sorkin.
    In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 94-103. 1993.

  • Theory and Practice of Simulated Annealing on Special Energy Landscapes.
    Gregory B. Sorkin. Ph.D. thesis, University of California at Berkeley, 1991.

  • Simulated annealing on fractals: Theoretical analysis and relevance for combinatorial optimization.
    Gregory B. Sorkin.
    In William Dally, editor, Proceedings of the 6th Annual MIT Conference on Advanced Research in VLSI, pages 331-351. MIT Press, Cambridge, MA, 1990.

  • ORCA: A sea-of-gates place and route system.
    Mark Beardslee, Mitch Igusa, Alan Kramer, Amit Sharma, Gregory Sorkin, and Alberto Sangiovanni-Vincentelli.
    In Proceedings of the International Workshop on Placement and Routing MCNC, 1988.

  • An almost-periodic Fourier transform for use with harmonic balance.
    Gregory B. Sorkin, Kenneth S. Kundert, and Alberto Sangiovanni-Vincentelli.
    In IEEE MTT-S International Microwave Symposium Digest, 1987.

  • Configuration space analysis for optimization problems.
    Sara A. Solla, Gregory B. Sorkin, and Steve R. White.
    In E. Bienenstock, F. Fogelman Soulie, and G. Weisbuch, editors, Disordered Systems and Biological Organization, NATO ASI series. Series F, Computer and System Sciences, number 20, pages 283-292. Springer-Verlag, New York, 1986.

  • Trivial global wiring of large chips: A statistical analysis.
    Gregory B. Sorkin.
    In IEEE ICCAD Conference Proceedings, pages 418-421. 1986.

  • Graph partitioning.
    Gregory Sorkin. 1983. A.B. Honors thesis, Harvard College.

  • The planar package planner for system designers.
    William R. Heller, Gregory Sorkin, and Klim Maling.
    In Proceedings of the 19th ACM/IEEE Design Automation Conference, pages 253-260. 1982.


This file has been generated by bibtex2html 1.74 ... with custom-bib, some hacking of the .bst file, a bit of scripting, and hand-editing. If you know an easy way, please tell me.