Gregory B. Sorkin

According to our database, Gregory B. Sorkin authored at least 56 papers between 1982 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds.

Alan M. Frieze, Pu Gao, Calum MacRury, Pawel Pralat, Gregory B. Sorkin

CoRR, 2023

2022

The Ising Antiferromagnet and Max Cut on Random Regular Graphs.

Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin

SIAM J. Discret. Math., 2022

Successive minimum spanning trees.

Svante Janson, Gregory B. Sorkin

Random Struct. Algorithms, 2022

2021

Minimum-Weight Combinatorial Structures Under Random Cost-Constraints.

Alan M. Frieze, Wesley Pegden, Gregory B. Sorkin, Tomasz Tkocz

Electron. J. Comb., 2021

2020

Successive shortest paths in complete graphs with random edge weights.

Stefanie Gerke, Balázs F. Mezei, Gregory B. Sorkin

Random Struct. Algorithms, 2020

2018

The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights.

Alan M. Frieze, Wesley Pegden, Gregory B. Sorkin

SIAM J. Discret. Math., 2018

2017

Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.

Serge Gaspers, Gregory B. Sorkin

ACM Trans. Algorithms, 2017

2016

The Satisfiability Threshold for <i>k</i>-XORSAT.

Boris G. Pittel, Gregory B. Sorkin

Comb. Probab. Comput., 2016

2015

Phase coexistence and torpid mixing in the 3-coloring model on ℤ^d.

David J. Galvin, Jeff Kahn, Dana Randall, Gregory B. Sorkin

SIAM J. Discret. Math., 2015

Efficient algorithms for three-dimensional axial and planar random assignment problems.

Alan M. Frieze, Gregory B. Sorkin

Random Struct. Algorithms, 2015

2014

Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets.

Serge Gaspers, Gregory B. Sorkin

CoRR, 2014

2013

Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331).

Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams

Dagstuhl Reports, 2013

VCG Auction Mechanism Cost Expectations and Variances.

Svante Janson, Gregory B. Sorkin

CoRR, 2013

2012

A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between.

Serge Gaspers, Gregory B. Sorkin

J. Comput. Syst. Sci., 2012

2011

First-passage percolation on a ladder graph, and the path cost in a VCG auction.

Abraham Flaxman, David Gamarnik, Gregory B. Sorkin

Random Struct. Algorithms, 2011

2010

Structure of random r-SAT below the pure literal threshold

Alexander D. Scott, Gregory B. Sorkin

CoRR, 2010

Average-case performance of heuristics for three-dimensional assignment problems

Alan M. Frieze, Gregory B. Sorkin

CoRR, 2010

Average case performance of heuristics for multi-dimensional assignment problems

Alan M. Frieze, Gregory B. Sorkin

CoRR, 2010

10441 Abstracts Collection - Exact Complexity of NP-hard Problems.

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin

Proceedings of the Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010, 2010

2009

Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function.

Alexander D. Scott, Gregory B. Sorkin

ACM Trans. Algorithms, 2009

A tight bound on the collection of edges in MSTs of induced subgraphs.

Gregory B. Sorkin, Angelika Steger, Rico Zenklusen

J. Comb. Theory, Ser. B, 2009

Conditional Probability Tree Estimation Analysis and Algorithms.

Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl

Proceedings of the UAI 2009, 2009

Average-Case Analyses of Vickrey Costs.

Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin

Proceedings of the Approximation, 2009

2008

Robust reductions from ranking to classification.

Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin

Mach. Learn., 2008

The Power of Choice in a Generalized Pólya Urn Model.

Gregory B. Sorkin

Proceedings of the Approximation, 2008

2007

The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems.

Alan M. Frieze, Gregory B. Sorkin

SIAM J. Comput., 2007

Linear-programming design and analysis of fast algorithms for Max 2-CSP.

Alexander D. Scott, Gregory B. Sorkin

Discret. Optim., 2007

Random 2-SAT with Prescribed Literal Degrees.

Colin Cooper, Alan M. Frieze, Gregory B. Sorkin

Algorithmica, 2007

2006

Vehicle Routing and Staffing for Sedan Service.

Oktay Günlük, Tracy Kimbrel, Laszlo Ladányi, Baruch Schieber, Gregory B. Sorkin

Transp. Sci., 2006

Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time.

Alexander D. Scott, Gregory B. Sorkin

Comb. Probab. Comput., 2006

Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP

Alexander D. Scott, Gregory B. Sorkin

CoRR, 2006

Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems

Alexander D. Scott, Gregory B. Sorkin

CoRR, 2006

First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction.

Abraham Flaxman, David Gamarnik, Gregory B. Sorkin

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

An LP-Designed Algorithm for Constraint Satisfaction.

Alexander D. Scott, Gregory B. Sorkin

Proceedings of the Algorithms, 2006

2005

Embracing the giant component.

Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin

Random Struct. Algorithms, 2005

2004

Random MAX SAT, random MAX CUT, and their phase transitions.

Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin

Random Struct. Algorithms, 2004

The interlace polynomial of a graph.

Richard Arratia, Béla Bollobás, Gregory B. Sorkin

J. Comb. Theory, Ser. B, 2004

Strings with Maximally Many Distinct Subsequences and Substrings.

Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin

Electron. J. Comb., 2004

A Two-Variable Interlace Polynomial.

Richard Arratia, Béla Bollobás, Gregory B. Sorkin

Comb., 2004

2003

Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances.

Alex D. Scott, Gregory B. Sorkin

Proceedings of the Approximation, 2003

2002

Exact Expectations And Distributions For The Random Assignment Problem.

Sven Erick Alm, Gregory B. Sorkin

Comb. Probab. Comput., 2002

A note on random 2-SAT with prescribed literal degrees.

Colin Cooper, Alan M. Frieze, Gregory B. Sorkin

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001

Some Notes on Random Satisfiability.

Gregory B. Sorkin

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2001

2000

Gadgets, Approximation, and Linear Programming.

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson

SIAM J. Comput., 2000

Euler circuits and DNA sequencing by hybridization.

Richard Arratia, Béla Bollobás, Don Coppersmith, Gregory B. Sorkin

Discret. Appl. Math., 2000

The interlace polynomial: a new graph polynomial.

Richard Arratia, Béla Bollobás, Gregory B. Sorkin

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Optimal myopic algorithms for random 3-SAT.

Dimitris Achlioptas, Gregory B. Sorkin

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Constructive bounds and exact expectations for the random assignment problem.

Don Coppersmith, Gregory B. Sorkin

Random Struct. Algorithms, 1999

1998

Constructing Computer Virus Phylogenies.

Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin

J. Algorithms, 1998

The Metropolis Algorithm for Graph Bisection.

Mark Jerrum, Gregory B. Sorkin

Discret. Appl. Math., 1998

1996

Gadgets, Approximation, and Linear Programming (extended abstract).

Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Biologically Inspired Defenses Against Computer Viruses.

Jeffrey O. Kephart, Gregory B. Sorkin, William C. Arnold, David M. Chess, Gerald Tesauro, Steve R. White

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995

1993

Simulated Annealing for Graph Bisection

Mark Jerrum, Gregory B. Sorkin

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1991

Efficient Simulated Annealing on Fractal Energy Landscapes.

Gregory B. Sorkin

Algorithmica, 1991

1987

Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis.

Gregory B. Sorkin

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1987

1982

The planar package planner for system designers.

William R. Heller, Gregory B. Sorkin, Klim Maling

Proceedings of the 19th Design Automation Conference, 1982