LSE creators

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, 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. (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, 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.
  • 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, 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
  • 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, 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
  • 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.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.
  • 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é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.
  • 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, 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.
  • 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, 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. (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, 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.
  • 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, Peter 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, 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
  • 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, 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