default search action
Gregory B. Sorkin
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
- [i15]Alan M. Frieze, Pu Gao, Calum MacRury, Pawel Pralat, Gregory B. Sorkin:
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds. CoRR abs/2311.05533 (2023) - 2022
- [j32]Svante Janson, Gregory B. Sorkin:
Successive minimum spanning trees. Random Struct. Algorithms 61(1): 126-172 (2022) - [j31]Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
:
The Ising Antiferromagnet and Max Cut on Random Regular Graphs. SIAM J. Discret. Math. 36(2): 1306-1342 (2022) - 2021
- [j30]Alan M. Frieze, Wesley Pegden
Minimum-Weight Combinatorial Structures Under Random Cost-Constraints. Electron. J. Comb. 28(1): 1 (2021) - 2020
- [j29]Stefanie Gerke, Balázs F. Mezei, Gregory B. Sorkin:
Successive shortest paths in complete graphs with random edge weights. Random Struct. Algorithms 57(4): 1205-1247 (2020) - [i14]Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin:
The Ising antiferromagnet and max cut on random regular graphs. CoRR abs/2009.10483 (2020)
2010 – 2019
- 2019
- [c23]Svante Janson
Successive Minimum Spanning Trees. APPROX-RANDOM 2019: 60:1-60:16 - [i13]Stefanie Gerke, Balázs Mezei, Gregory B. Sorkin:
Successive shortest paths in complete graphs with random edge weights. CoRR abs/1911.01151 (2019) - 2018
- [j28]Alan M. Frieze, Wesley Pegden
The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights. SIAM J. Discret. Math. 32(3): 2115-2133 (2018) - 2017
- [j27]Serge Gaspers
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. ACM Trans. Algorithms 13(4): 44:1-44:36 (2017) - 2016
- [j26]Boris G. Pittel, Gregory B. Sorkin
The Satisfiability Threshold for k-XORSAT. Comb. Probab. Comput. 25(2): 236-268 (2016) - 2015
- [j25]Alan M. Frieze
Efficient algorithms for three-dimensional axial and planar random assignment problems. Random Struct. Algorithms 46(1): 160-196 (2015) - [j24]David J. Galvin, Jeff Kahn, Dana Randall, Gregory B. Sorkin
Phase coexistence and torpid mixing in the 3-coloring model on ℤd. SIAM J. Discret. Math. 29(3): 1223-1244 (2015) - [c22]Serge Gaspers, Gregory B. Sorkin
Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. ICALP (1) 2015: 567-579 - 2014
- [i12]Serge Gaspers, Gregory B. Sorkin:
Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets. CoRR abs/1404.0753 (2014) - [i11]Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl:
Conditional Probability Tree Estimation Analysis and Algorithms. CoRR abs/1408.2031 (2014) - 2013
- [i10]Svante Janson, Gregory B. Sorkin:
VCG Auction Mechanism Cost Expectations and Variances. CoRR abs/1310.1777 (2013) - [i9]Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams:
Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports 3(8): 40-72 (2013) - 2012
- [j23]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) - 2011
- [j22]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) - 2010
- [e1]Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin:
Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010. Dagstuhl Seminar Proceedings 10441, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2010 [contents] - [i8]Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin:
10441 Abstracts Collection - Exact Complexity of NP-hard Problems. Exact Complexity of NP-hard Problems 2010 - [i7]Alan M. Frieze, Gregory B. Sorkin:
Average case performance of heuristics for multi-dimensional assignment problems. CoRR abs/1004.4239 (2010) - [i6]Alan M. Frieze, Gregory B. Sorkin:
Average-case performance of heuristics for three-dimensional assignment problems. CoRR abs/1008.0390 (2010) - [i5]Alexander D. Scott, Gregory B. Sorkin:
Structure of random r-SAT below the pure literal threshold. CoRR abs/1008.1260 (2010)
2000 – 2009
- 2009
- [j21]Gregory B. Sorkin
A tight bound on the collection of edges in MSTs of induced subgraphs. J. Comb. Theory B 99(2): 428-435 (2009) - [j20]Alexander D. Scott, Gregory B. Sorkin
Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Trans. Algorithms 5(4): 45:1-45:27 (2009) - [c21]Prasad Chebolu, Alan M. Frieze, Páll Melsted
Average-Case Analyses of Vickrey Costs. APPROX-RANDOM 2009: 434-447 - [c20]Serge Gaspers, Gregory B. Sorkin
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. SODA 2009: 606-615 - [c19]Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl:
Conditional Probability Tree Estimation Analysis and Algorithms. UAI 2009: 51-58 - [i4]Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl:
Conditional Probability Tree Estimation Analysis and Algorithms. CoRR abs/0903.4217 (2009) - [i3]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) - 2008
- [j19]Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
Robust reductions from ranking to classification. Mach. Learn. 72(1-2): 139-153 (2008) - [c18]Gregory B. Sorkin
The Power of Choice in a Generalized Pólya Urn Model. APPROX-RANDOM 2008: 571-583 - 2007
- [j18]Colin Cooper, Alan M. Frieze
Random 2-SAT with Prescribed Literal Degrees. Algorithmica 48(3): 249-265 (2007) - [j17]Alexander D. Scott, Gregory B. Sorkin
Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discret. Optim. 4(3-4): 260-287 (2007) - [j16]Alan M. Frieze
The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. SIAM J. Comput. 36(5): 1435-1452 (2007) - [c17]Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
Robust Reductions from Ranking to Classification. COLT 2007: 604-619 - 2006
- [j15]Alexander D. Scott, Gregory B. Sorkin
Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time. Comb. Probab. Comput. 15(1-2): 281-315 (2006) - [j14]Oktay Günlük
Vehicle Routing and Staffing for Sedan Service. Transp. Sci. 40(3): 313-326 (2006) - [c16]Alexander D. Scott, Gregory B. Sorkin
An LP-Designed Algorithm for Constraint Satisfaction. ESA 2006: 588-599 - [c15]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 - [i2]Alexander D. Scott, Gregory B. Sorkin:
Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems. CoRR abs/cs/0604079 (2006) - [i1]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) - 2005
- [j13]Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin
Embracing the giant component. Random Struct. Algorithms 27(3): 277-289 (2005) - 2004
- [j12]Richard Arratia, Béla Bollobás, Gregory B. Sorkin
A Two-Variable Interlace Polynomial. Comb. 24(4): 567-584 (2004) - [j11]Abraham Flaxman, Aram W. Harrow
Strings with Maximally Many Distinct Subsequences and Substrings. Electron. J. Comb. 11(1) (2004) - [j10]Richard Arratia, Béla Bollobás, Gregory B. Sorkin
The interlace polynomial of a graph. J. Comb. Theory B 92(2): 199-233 (2004) - [j9]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) - [c14]Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
Embracing the Giant Component. LATIN 2004: 69-79 - 2003
- [c13]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 - [c12]Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin:
Random MAX SAT, random MAX CUT, and their phase transitions. SODA 2003: 364-373 - 2002
- [j8]Sven Erick Alm, Gregory B. Sorkin
Exact Expectations And Distributions For The Random Assignment Problem. Comb. Probab. Comput. 11(3): 217-248 (2002) - [c11]Colin Cooper, Alan M. Frieze, Gregory B. Sorkin:
A note on random 2-SAT with prescribed literal degrees. SODA 2002: 316-320 - 2001
- [c10]Gregory B. Sorkin
Some Notes on Random Satisfiability. SAGA 2001: 117-130 - [c9]Alan M. Frieze, Gregory B. Sorkin:
The probabilistic relationship between the assignment and asymmetric traveling salesman problems. SODA 2001: 652-660 - 2000
- [j7]Richard Arratia, Béla Bollobás, Don Coppersmith, Gregory B. Sorkin
Euler circuits and DNA sequencing by hybridization. Discret. Appl. Math. 104(1-3): 63-96 (2000) - [j6]Luca Trevisan
Gadgets, Approximation, and Linear Programming. SIAM J. Comput. 29(6): 2074-2097 (2000) - [c8]Dimitris Achlioptas, Gregory B. Sorkin
Optimal myopic algorithms for random 3-SAT. FOCS 2000: 590-600 - [c7]Richard Arratia, Béla Bollobás, Gregory B. Sorkin:
The interlace polynomial: a new graph polynomial. SODA 2000: 237-245
1990 – 1999
- 1999
- [j5]Don Coppersmith, Gregory B. Sorkin:
Constructive bounds and exact expectations for the random assignment problem. Random Struct. Algorithms 15(2): 113-144 (1999) - 1998
- [j4]Mark Jerrum, Gregory B. Sorkin
The Metropolis Algorithm for Graph Bisection. Discret. Appl. Math. 82(1-3): 155-175 (1998) - [j3]Leslie Ann Goldberg, Paul W. Goldberg
Constructing Computer Virus Phylogenies. J. Algorithms 26(1): 188-208 (1998) - [c6]Don Coppersmith, Gregory B. Sorkin
Constructive Bounds and Exact Expectations for the Random Assignment Problem. RANDOM 1998: 319-330 - 1996
- [c5]Leslie Ann Goldberg, Paul W. Goldberg
Constructing Computer Virus Phylogenies. CPM 1996: 253-270 - [c4]Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson:
Gadgets, Approximation, and Linear Programming (extended abstract). FOCS 1996: 617-626 - 1995
- [c3]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 - 1993
- [c2]Mark Jerrum, Gregory B. Sorkin:
Simulated Annealing for Graph Bisection. FOCS 1993: 94-103 - 1991
- [j2]Gregory B. Sorkin
Efficient Simulated Annealing on Fractal Energy Landscapes. Algorithmica 6(3): 367-418 (1991)
1980 – 1989
- 1987
- [j1]Gregory B. Sorkin
Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 6(5): 820-827 (1987) - 1982
- [c1]William R. Heller, Gregory B. Sorkin, Klim Maling:
The planar package planner for system designers. DAC 1982: 253-260
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-06-10 21:26 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: