LSE creators

Number of items: 74.
Article
  • Frieze, Alan, Gao, Pu, MacRury, Calum, Pralat, Pawel, Sorkin, Gregory B. (2025). Building Hamiltonian cycles in the semi-random graph process in less than 2 rounds. European Journal of Combinatorics, 126, https://doi.org/10.1016/j.ejc.2025.104122 picture_as_pdf
  • Molloy, Michael, Pralat, Pawel, Sorkin, Gregory B. (2025). Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model. Random Structures and Algorithms, 66(2). https://doi.org/10.1002/rsa.21270 picture_as_pdf
  • Sorkin, Gregory B. (2023). Snakes and ladders and intransitivity, or what mathematicians do in their time off. Mathematical Intelligencer, 45(4), 312 - 318. https://doi.org/10.1007/s00283-022-10250-6 picture_as_pdf
  • Janson, Svante, Sorkin, Gregory B. (2022). Successive minimum spanning trees. Random Structures and Algorithms, 61(1), 126 - 172. https://doi.org/10.1002/rsa.21047 picture_as_pdf
  • Coja-Oghlan, Amin, Loick, Philipp, Mezei, Balazs F., Sorkin, Gregory B. (2022). The ising antiferromagnet and max cut on random regular graphs. SIAM Journal on Discrete Mathematics, 36(2), 1306 - 1342. https://doi.org/10.1137/20M137999X picture_as_pdf
  • Frieze, Alan, Pegden, Wesley, Sorkin, Gregory B., Tkocz, Tomasz (2021). Minimum-weight combinatorial structures under random cost-constraints. Electronic Journal of Combinatorics, 28(1). https://doi.org/10.37236/9152 picture_as_pdf
  • Gerke, Stefanie, Mezei, Balazs F., Sorkin, Gregory (2020). Successive shortest paths in complete graphs with random edge weights. Random Structures and Algorithms, 57(4), 1205 - 1247. https://doi.org/10.1002/rsa.20962 picture_as_pdf
  • Frieze, Alan, Pegden, Wesley, Sorkin, Gregory B. (2018). The distribution of minimum-weight cliques and other subgraphs in graphs with random edge weights. SIAM Journal on Discrete Mathematics, 32(3), 2115-2133. https://doi.org/10.1137/17M1138303
  • Gaspers, Serge, Sorkin, Gregory B. (2017). Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets. ACM Transactions on Algorithms, 13(4), 1-36. https://doi.org/10.1145/3111499
  • Pittel, Boris, Sorkin, Gregory B. (2015). The satisfiability threshold for k-XORSAT. Combinatorics, Probability and Computing, 25(2), 236-268. https://doi.org/10.1017/S0963548315000097
  • Frieze, Alan, Sorkin, Gregory B. (2015). Efficient algorithms for three-dimensional axial and planar random assignment problems. Random Structures and Algorithms, 46(1), 160 - 196. https://doi.org/10.1002/rsa.20525
  • Galvin, David, Kahn, Jeff, Randall, Dana, Sorkin, Gregory B. (2015). Phase coexistence and torpid mixing in the 3-coloring model on Z^d. SIAM Journal on Discrete Mathematics, 29(3), 1223-1244. https://doi.org/10.1137/12089538X
  • Flaxman, Abraham, Gamarnik, David, Sorkin, Gregory B. (2011). First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Structures and Algorithms, 38(3), 350-364. https://doi.org/10.1002/rsa.20328
  • Gaspers, Serge, Sorkin, Gregory B. (2011). A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. Journal of Computer and System Sciences, 78(1), 305-335. https://doi.org/10.1016/j.jcss.2011.05.010
  • Scott, Alexander D., Sorkin, Gregory B. (2009). Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Transactions on Algorithms, 5(4), 45:1-27. https://doi.org/10.1145/1597036.1597049
  • Sorkin, Gregory B., Steger, Angelika, Zenklusenc, Rico (2009). A tight bound on the collection of edges in MSTs of induced subgraphs. Journal of Combinatorial Theory, Series B, 99(2), 428-435. https://doi.org/10.1016/j.jctb.2008.08.008
  • Balcan, Maria-Florina, Bansal, Nikhil, Beygelzimer, Alina, Coppersmith, Don, Langford, John, Sorkin, Gregory B. (2008). Robust reductions from ranking to classification. Machine Learning, 72(1-2), 139-153. https://doi.org/10.1007/s10994-008-5058-6
  • Scott, Alexander D., Sorkin, Gregory B. (2007). Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discrete Optimization, 4(3-4), 260-287. https://doi.org/10.1016/j.disopt.2007.08.001
  • Cooper, Colin, Frieze, Alan, Sorkin, Gregory B. (2007). Random 2-SAT with prescribed literal degrees. Algorithmica, 48(3), 249-265. https://doi.org/10.1007/s00453-007-0082-7
  • Frieze, Alan, Sorkin, Gregory B. (2006). The probabilistic relationship between the assignment and travelling salesman problems. SIAM Journal on Computing, 36(5), 1435-1452. https://doi.org/10.1137/S0097539701391518
  • Günlük, Oktay, Kimbrel, Tracy, Ladanyi, Laszlo, Schieber, Baruch, Sorkin, Gregory B. (2006). Vehicle routing and staffing for sedan service. Transportation Science, 40(3), 313-326. https://doi.org/10.1287/trsc.1050.0122
  • Scott, Alexander D., Sorkin, Gregory B. (2006). Solving sparse random instances of Max Cut and Max 2-CSP in linear expected time. Combinatorics, Probability and Computing, 15(1-2), 281-315. https://doi.org/10.1017/S096354830500725X
  • Flaxman, Abraham D., Gamarnik, David, Sorkin, Gregory B. (2005). Embracing the giant component. Random Structures and Algorithms, 27(3), 277-289. https://doi.org/10.1002/rsa.20070
  • Arratia, Richard, Bollobás, Béla, Sorkin, Gregory B. (2004). The interlace polynomial of a graph. Journal of Combinatorial Theory, Series B, 92(2), 199-233. https://doi.org/10.1016/j.jctb.2004.03.003
  • Arratia, Richard, Bollobás, Béla, Sorkin, Gregory B. (2004). A two-variable interlace polynomial. Combinatorica, 24(2), 567-584. https://doi.org/10.1007/s00493-004-0035-6
  • Flaxman, Abraham, Harrow, Aram W., Sorkin, Gregory B. (2004). Strings with maximally many distinct subsequences and substrings. Electronic Journal of Combinatorics, 11(1), 1-10.
  • Coppersmith, Don, Gamarnik, David, Taghi Hajiaghayi, Mohammad, Sorkin, Gregory B. (2004). Random MAX SAT, random MAX CUT, and their phase transitions. Random Structures and Algorithms, 24(4), 502-545. https://doi.org/10.1002/rsa.20015
  • Alm, Erik. S, Sorkin, Gregory B. (2002). Exact expectations and distributions for the random assignment problem. Combinatorics, Probability and Computing, 11(3), 217-248. https://doi.org/10.1017/S0963548302005114
  • Arratia, Richard, Bollobás, Béla, Coppersmith, Don, Sorkin, Gregory B. (2000). Euler circuits and DNA sequencing by hybridization. Discrete Applied Mathematics, 104(1-3), 63-96. https://doi.org/10.1016/S0166-218X(00)00190-6
  • Trevisan, Luca, Sorkin, Gregory B., Sudan, Madhu, Williamson, David P. (2000). Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6), 2074-2097.
  • Coppersmith, Don, Sorkin, Gregory B. (1999). Constructive bounds and exact expectations for the random assignment problem. Random Structures and Algorithms, 15(2), 113-144. https://doi.org/10.1002/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO;2-S
  • Jerrum, Mark, Sorkin, Gregory B. (1998). The Metropolis algorithm for graph bisection. Discrete Applied Mathematics, 82(1-3), 155-175. https://doi.org/10.1016/S0166-218X(97)00133-9
  • Goldberg, Leslie A., Goldberg, Paul W., Phillips, Cynthia A., Sorkin, Gregory B. (1998). Constructing computer virus phylogenies. Journal of Algorithms, 26(1), 188-208. https://doi.org/10.1006/jagm.1997.0897
  • Kephart, Jeffrey O., Sorkin, Gregory B., Chess, David M., White, Steve R. (1997). Fighting computer viruses. Scientific American, 277(5), 88-93. https://doi.org/10.1038/scientificamerican1197-88
  • Tesauro, G.J., Kephart, J.O., Sorkin, Gregory B. (1996). Neural networks for computer virus recognition. IEEE Expert, 11(4), 5-6. https://doi.org/10.1109/64.511768
  • Sorkin, Gregory B. (1991). Efficient simulated annealing on fractal energy landscapes. Algorithmica, 6(1-6), 367-418. https://doi.org/10.1007/BF01759051
  • Kundert, K.S., Sorkin, Gregory B., Sangiovanni-Vincentelli, A. (1988). Applying harmonic balance to almost-periodic circuits. IEEE Transactions on Microwave Theory and Techniques, 36(2), 366-378. https://doi.org/10.1109/22.3525
  • Sorkin, Gregory B. (1987). Asymptotically perfect trivial global routing: a stochastic analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 6(5), 820-827. https://doi.org/10.1109/TCAD.1987.1270325
    • Chapter
  • Chatterjee, Arnab, Coja-oghlan, Amin, Kang, Mihyun, Krieg, Lena, Rolvien, Maurice, Sorkin, Gregory B. (2025). Belief Propagation Guided Decimation on random 1 k-XORSAT. In Censor-Hillel, Keren, Grandoni, Fabrizio, Ouaknine, Joël, Puppis, Gabriele (Eds.), 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) . Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2025.47 picture_as_pdf
  • Gaspers, Serge, Sorkin, Gregory B. (2015). Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets. In Halldórsson, Magnús M., Iwama, Kazuo, Kobayashi, Naoki, Speckmann, Bettina (Eds.), Automata, Languages, and Programming: 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I (pp. 567-579). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_46
  • Chebolu, Prasad, Frieze, Alan, Melsted, Páll, Sorkin, Gregory B. (2009). Average-case analyses of Vickrey costs. In Dinur, Irit, Jansen, Klaus, Naor, Seffi, Rolim, José (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques:12th International Workshop, Approx 2009 (pp. 434-447). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-642-03685-9_33
  • Balcan, Maria Florina, Bansal, Nikhil, Beygelzimer, Alina, Coppersmith, Don, Langford, John, Sorkin, Gregory B. (2007). Robust reductions from ranking to classification. In Bshouty, Nader, Gentile, Claudio (Eds.), Learning Theory: 20th Annual Conference on Learning Theory, Colt 2007, San Diego, Ca, Usa, June 13-15, 2007, Proceedings (pp. 604-619). Springer Berlin / Heidelberg.
  • Flaxman, Abraham, Gamarnik, David, Sorkin, Gregory B. (2006). First-passage percolation on a width-2 strip and the path cost in a VCG auction. In Spirakis, Paul, Mavronicolas, Marios, Kontogiannis, Spyros (Eds.), Internet and Network Economics: Second International Workshop, Wine 2006, Patras, Greece, December 15-17, 2006, Proceedings (pp. 99-111). Springer Berlin / Heidelberg.
  • Scott, Alexander D., Sorkin, Gregory B. (2006). An LP-designed algorithm for constraint satisfaction. In Azar, Yossi, Erlebach, Thomas (Eds.), Algorithms - Esa 2006. 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings (pp. 588-599). Springer Berlin / Heidelberg. https://doi.org/10.1007/11841036
  • Flaxman, Abraham, Gamarnik, David, Sorkin, Gregory B. (2004). Embracing the giant component. In Farach-Colton, Martin (Ed.), Latin 2004: Theoretical Informatics. 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings (pp. 66-79). Springer Berlin / Heidelberg. https://doi.org/10.1007/978-3-540-24698-5_11
  • Scott, Alexander D., Sorkin, Gregory B. (2003). Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (Eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 6th International Workshop on Approxima (pp. 382-395). Springer Berlin / Heidelberg.
  • Coppersmith, Don, Gamarnik, David, Hajiaghayi, Mohammad, Sorkin, Gregory B. (2003). Random Max Sat, random Max Cut, and their phase transitions. In Farach-Colton, Martin (Ed.), Proceedings of the Fourteenth Aanual ACM-SIAM: Symposium on Discrete Algorithms (pp. 364-373). SIAM.
  • Coppersmith, Don, Sorkin, Gregory B. (2002). On the expected incremental cost of a minimum assignment. In Bollobás, Béla (Ed.), Contemporary Combinatorics (pp. 277-288). Springer Berlin / Heidelberg.
  • Sorkin, Gregory B. (2001). Some notes on random satisfiability. In Steinhöfel, Kathleen (Ed.), Stochastic Algorithms: Foundations and Applications: International Symposium, Saga 2001, Germany, December 2001 Proceedings (pp. 117-130). Springer Berlin / Heidelberg.
  • Coppersmith, Don, Sorkin, Gregory B. (1998). Constructive bounds and exact expectations for the random assignment problem. In Luby, Michael, Rolim, Jose, Serna, Maria J. (Eds.), Randomization and Approximation Techniques in Computer Science: Second International Workshop, Random'98, Barcelona, Spain, Octo (pp. 319-330). Springer Berlin / Heidelberg.
  • Kephart, Jeffrey O., Sorkin, Gregory B., Swimmer, Morton, White, Steve R. (1998). Blueprint for a computer immune system. In Dasgupta, Dipankar (Ed.), Artificial Immune Systems and Their Applications (pp. 242-261). Springer Berlin / Heidelberg.
  • Kephart, Jeffrey O., Sorkin, Gregory B., Arnold, William C., Chess, David M., Tesauro, Gerald J., White, Steve R. (1998). Biologically inspired defenses against computer viruses. In Michalski, Ryszad S., Bratko, Ivan, Kubat, Miroslav (Eds.), Machine Learning and Data Mining: Methods and Applications (pp. 313-334). John Wiley & Sons.
  • Goldberg, Leslie A., Goldberg, Paul W., Phillips, Cynthia A., Sorkin, Gregory B. (1996). Constructing computer virus phylogenies. In Hirschberg, Dan, Meyers, Gene (Eds.), Combinatorial Pattern Matching.7th Annual Symposium, Cpm '96, Laguna Beach, California, June 10-12, 1996. Proceedings (pp. 253-270). Springer Berlin / Heidelberg.
  • Kirkpatrick, Scott, Sorkin, Gregory B. (1995). Simulated annealing. In Arbib, Michael A. (Ed.), Handbook of Brain Theory and Neural Networks (pp. 876-879). MIT Press.
  • Solla, Sara A., Sorkin, Gregory B., White, Steve R. (1986). Configuration space analysis for optimization problems. In Bienenstock, E. (Ed.), Disordered Systems and Biological Organization (pp. 283-292). Springer Berlin / Heidelberg.
  • Sorkin, Gregory B. (1980). The enumeration of nonhomeomorphic graphs by edges. In Hammer, Peter L. (Ed.), Combinatorics 79 (pp. 249-252). Elsevier (Firm). https://doi.org/10.1016/S0167-5060(08)70075-X
    • Conference or Workshop Item
  • Janson, Svante, Sorkin, Gregory B. (2019-09-20 - 2019-09-22) Successive minimum spanning trees [Paper]. International Conference on Randomization and Computation (Random) 2019, MIT Stata Center, Cambridge, United States, USA. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.60 picture_as_pdf
  • Beygelzimer, Alina, Langford, John, Lifshits, Yuri, Sorkin, Gregory B., Strehl, Alex (2009-06-18 - 2009-06-21) Conditional probability tree estimation analysis and algorithms [Paper]. Uncertainty in artificial intelligence, QC, Canada, CAN.
  • Gaspers, Serge, Sorkin, Gregory B. (2009-01-04 - 2009-01-06) A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between [Paper]. ACM-SIAM Symposium 4-6 January hosted in New York Marriot Downtown, NY, New York NY, United States, USA.
  • Cooper, Colin, Frieze, Alan, Sorkin, Gregory B. (2002-01-06 - 2002-01-08) A note on random 2-SAT with prescribed literal degrees [Paper]. Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, CA, United States, USA.
  • Frieze, Alan, Sorkin, Gregory B. (2001-01-07 - 2001-01-09) The probabilistic relationship between the assignment and traveling salesman problems [Paper]. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, DC, United States, USA.
  • Achioptas, D., Sorkin, Gregory B. (2000-11-12 - 2000-11-14) Optimal myopic algorithms for random 3-SAT [Paper]. 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, United States, USA.
  • Arratia, Richard, Bollobás, Béla, Sorkin, Gregory B. (2000-01-09 - 2000-01-11) The interlace polynomial: a new graph polynomial [Paper]. Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, United States, USA.
  • Kephart, Jeffrey O., Sorkin, Gregory B., Swimmer, Morton, White, Steve R. (1997-10-02 - 1997-10-03) Blueprint for a computer immune system [Paper]. The Seventh International Virus Bulletin Conference, CA, United States, USA.
  • Kephart, Jeffrey O., Sorkin, Gregory B., Swimmer, Morton (1997-10-12 - 1997-10-15) An immune system for cyberspace [Paper]. IEEE International Conference on Systems, Man, and Cybernetics 'Computational Cybernetics and Simulation', Orlando Fl, United States, USA.
  • Trevisan, Luca, Sorkin, Gregory B., Sudan, Madhu, Williamson, David P. (1996-10-14 - 1996-10-16) Gadgets, approximation, and linear programming [Paper]. 37th Annual IEEE Symposium on Foundations of Computer Science, VT, United States, USA.
  • Arnold, William C., Sorkin, Gregory B. (1996-09-19 - 1996-09-20) Automated analysis of computer viruses [Paper]. 1996 Virus Bulletin International Conference, Brighton, United Kingdom, GBR.
  • Kephart, Jeffrey O., Sorkin, Gregory B., Arnold, William C., Chess, David M., Tesauro, Gerald J., White, Steve R. (1995-08-20 - 1995-08-25) Biologically inspired defenses against computer viruses [Paper]. The Fourteenth International Joint Conference on Artificial Intelligence, Quebec, Canada, CAN.
  • Jerrum, Mark, Sorkin, Gregory B. (1993-11-03 - 1993-11-05) Simulated annealing for graph bisection [Paper]. 34th Annual Symposium on Foundations of Computer Science, CA, United States, USA.
  • Sorkin, Gregory B. (1990-04-02 - 1990-04-04) Simulated annealing on fractals: theoretical analysis and relevance for combinatorial optimization [Paper]. The sixth MIT conference on advanced research in VLSI, MA, United States, USA.
  • Beardslee, Mark, Igusa, Mitch, Kramer, Alan, Sharma, Amit, Sorkin, Gregory B. (1988-01-01) ORCA: a sea-of-gates place and route system [Paper]. International Workshop on Placement and Routing MCNC.
  • Sorkin, Gregory B., Kundert, Kenneth S., Sangiovanni-Vincentelli, Alberto (1987-01-01) An almost-periodic Fourier transform for use with harmonic balance [Paper]. 1987 IEEE MTT-S International Microwave Symposium Digest.
  • Sorkin, Gregory B. (1986-01-01) Trivial global wiring of large chips: a statistical analysis [Paper]. IEEE International Conference on Computer-Aided Design (IEEE ICCAD).
  • Heller, William R., Sorkin, Gregory B., Maling, Klim (1982-06-14 - 1982-06-16) The planar package planner for system designers [Paper]. The 19th ACM/IEEE Conference on Design Automation.