Gregory B. Sorkin

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

Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Struct. Algorithms 38(3): 350-364 (2011)

Alan M. Frieze, Gregory B. Sorkin: Average case performance of heuristics for multi-dimensional assignment problems. CoRR abs/1004.4239 (2010)

Alan M. Frieze, Gregory B. Sorkin: Average-case performance of heuristics for three-dimensional assignment problems. CoRR abs/1008.0390 (2010)

Alexander D. Scott, Gregory B. Sorkin: Structure of random r-SAT below the pure literal threshold. CoRR abs/1008.1260 (2010)

Gregory B. Sorkin, Angelika Steger, Rico Zenklusen: A tight bound on the collection of edges in MSTs of induced subgraphs. J. Comb. Theory, Ser. B 99(2): 428-435 (2009)

Alexander D. Scott, Gregory B. Sorkin: Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Transactions on Algorithms 5(4) (2009)

Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin: Average-Case Analyses of Vickrey Costs. APPROX-RANDOM 2009: 434-447

Serge Gaspers, Gregory B. Sorkin: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. SODA 2009: 606-615

Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl: Conditional Probability Tree Estimation Analysis and Algorithms. UAI 2009: 51-58

Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl: Conditional Probability Tree Estimation Analysis and Algorithms. CoRR abs/0903.4217 (2009)

Serge Gaspers, Gregory B. Sorkin: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. CoRR abs/0906.3527 (2009)

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

Gregory B. Sorkin: The Power of Choice in a Generalized Pólya Urn Model. APPROX-RANDOM 2008: 571-583

Colin Cooper, Alan M. Frieze, Gregory B. Sorkin: Random 2-SAT with Prescribed Literal Degrees. Algorithmica 48(3): 249-265 (2007)

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

Alan M. Frieze, Gregory B. Sorkin: The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. SIAM J. Comput. 36(5): 1435-1452 (2007)

Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin: Robust Reductions from Ranking to Classification. COLT 2007: 604-619

Alexander D. Scott, Gregory B. Sorkin: Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time. Combinatorics, Probability & Computing 15(1-2): 281-315 (2006)

Oktay Günlük, Tracy Kimbrel, Laszlo Ladányi, Baruch Schieber, Gregory B. Sorkin: Vehicle Routing and Staffing for Sedan Service. Transportation Science 40(3): 313-326 (2006)

Alexander D. Scott, Gregory B. Sorkin: An LP-Designed Algorithm for Constraint Satisfaction. ESA 2006: 588-599

Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. WINE 2006: 99-111

Alexander D. Scott, Gregory B. Sorkin: Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems. CoRR abs/cs/0604079 (2006)

Alexander D. Scott, Gregory B. Sorkin: Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP. CoRR abs/cs/0604080 (2006)

Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the giant component. Random Struct. Algorithms 27(3): 277-289 (2005)

Richard Arratia, Béla Bollobás, Gregory B. Sorkin: A Two-Variable Interlace Polynomial. Combinatorica 24(4): 567-584 (2004)

Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: Strings with Maximally Many Distinct Subsequences and Substrings. Electr. J. Comb. 11(1) (2004)

Richard Arratia, Béla Bollobás, Gregory B. Sorkin: The interlace polynomial of a graph. J. Comb. Theory, Ser. B 92(2): 199-233 (2004)

Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms 24(4): 502-545 (2004)

Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the Giant Component. LATIN 2004: 69-79

Alex D. Scott, Gregory B. Sorkin: Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. RANDOM-APPROX 2003: 382-395

Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. SODA 2003: 364-373

Sven Erick Alm, Gregory B. Sorkin: Exact Expectations And Distributions For The Random Assignment Problem. Combinatorics, Probability & Computing 11(3): 217-248 (2002)

Colin Cooper, Alan M. Frieze, Gregory B. Sorkin: A note on random 2-SAT with prescribed literal degrees. SODA 2002: 316-320

Gregory B. Sorkin: Some Notes on Random Satisfiability. SAGA 2001: 117-130

Alan M. Frieze, Gregory B. Sorkin: The probabilistic relationship between the assignment and asymmetric traveling salesman problems. SODA 2001: 652-660

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

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000)

Dimitris Achlioptas, Gregory B. Sorkin: Optimal myopic algorithms for random 3-SAT. FOCS 2000: 590-600

Richard Arratia, Béla Bollobás, Gregory B. Sorkin: The interlace polynomial: a new graph polynomial. SODA 2000: 237-245

Don Coppersmith, Gregory B. Sorkin: Constructive bounds and exact expectations for the random assignment problem. Random Struct. Algorithms 15(2): 113-144 (1999)

Mark Jerrum, Gregory B. Sorkin: The Metropolis Algorithm for Graph Bisection. Discrete Applied Mathematics 82(1-3): 155-175 (1998)

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin: Constructing Computer Virus Phylogenies. J. Algorithms 26(1): 188-208 (1998)

Don Coppersmith, Gregory B. Sorkin: Constructive Bounds and Exact Expectations for the Random Assignment Problem. RANDOM 1998: 319-330

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin: Constructing Computer Virus Phylogenies. CPM 1996: 253-270

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson: Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626

Jeffrey O. Kephart, Gregory B. Sorkin, William C. Arnold, David M. Chess, Gerald Tesauro, Steve R. White: Biologically Inspired Defenses Against Computer Viruses. IJCAI (1) 1995: 985-996

Mark Jerrum, Gregory B. Sorkin: Simulated Annealing for Graph Bisection. FOCS 1993: 94-103

Gregory B. Sorkin: Efficient Simulated Annealing on Fractal Energy Landscapes. Algorithmica 6(3): 367-418 (1991)

Gregory B. Sorkin: Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis. IEEE Trans. on CAD of Integrated Circuits and Systems 6(5): 820-827 (1987)

William R. Heller, Gregory B. Sorkin, Klim Maling: The planar package planner for system designers. DAC 1982: 253-260