Sorkin, Gregory B.

Number of items: 74.
None
  • 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
  • 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.
  • 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
  • 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.
  • Chebolu, Prasad, Frieze, Alan, Melsted, Páll, Sorkin, Gregory B. (2009). Average-case analyses of Vickrey costs. In Dinur, I., Jansen, K., Naor, S. & Rolim, J. (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. (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
  • Balcan, Maria Florina, Bansal, Nikhil, Beygelzimer, Alina, Coppersmith, Don, Langford, John, Sorkin, Gregory B. (2007). Robust reductions from ranking to classification. In Bshouty, N. & Gentile, C. (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, P., Mavronicolas, M. & Kontogiannis, S. (Eds.), Internet and Network Economics: Second International Workshop, Wine 2006, Patras, Greece, December 15-17, 2006, Proceedings (pp. 99-111). Springer Berlin / Heidelberg.
  • 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
  • Scott, Alexander D., Sorkin, Gregory B. (2006). An LP-designed algorithm for constraint satisfaction. In Azar, Y. & Erlebach, T. (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
  • 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
  • Flaxman, Abraham, Gamarnik, David, Sorkin, Gregory B. (2004). Embracing the giant component. In Farach-Colton, M. (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
  • 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
  • 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. & 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, M. (Ed.), Proceedings of the Fourteenth Aanual ACM-SIAM: Symposium on Discrete Algorithms (pp. 364-373). SIAM.
  • 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
  • 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.
  • Coppersmith, Don, Sorkin, Gregory B. (2002). On the expected incremental cost of a minimum assignment. In Bollobás, B. (Ed.), Contemporary Combinatorics (pp. 277-288). Springer Berlin / Heidelberg.
  • Sorkin, Gregory B. (2001). Some notes on random satisfiability. In Steinhöfel, K. (Ed.), Stochastic Algorithms: Foundations and Applications: International Symposium, Saga 2001, Germany, December 2001 Proceedings (pp. 117-130). Springer Berlin / Heidelberg.
  • 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, 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
  • 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.
  • 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
  • Coppersmith, Don, Sorkin, Gregory B. (1998). Constructive bounds and exact expectations for the random assignment problem. In Luby, M., Rolim, J. & Serna, M. 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, D. (Ed.), Artificial Immune Systems and Their Applications (pp. 242-261). Springer Berlin / Heidelberg.
  • 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
  • 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, R. S., Bratko, I. & Kubat, M. (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. (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
  • 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.
  • 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
  • Goldberg, Leslie A., Goldberg, Paul W., Phillips, Cynthia A., Sorkin, Gregory B. (1996). Constructing computer virus phylogenies. In Hirschberg, D. & Meyers, G. (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, M. A. (Ed.), Handbook of Brain Theory and Neural Networks (pp. 876-879). MIT Press.
  • 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. (1991). Efficient simulated annealing on fractal energy landscapes. Algorithmica, 6(1-6), 367-418. https://doi.org/10.1007/BF01759051
  • 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.
  • 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
  • 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. (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
  • 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.
  • 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. (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.
  • Sorkin, Gregory B. (1980). The enumeration of nonhomeomorphic graphs by edges. In Hammer, P. L. (Ed.), Combinatorics 79 (pp. 249-252). Elsevier (Firm). https://doi.org/10.1016/S0167-5060(08)70075-X
    • Public
  • 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, K., Grandoni, F., Ouaknine, J. & Puppis, G. (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
  • 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
  • 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
  • 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
  • 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, M. M., Iwama, K., Kobayashi, N. & Speckmann, B. (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