Gregory B. Sorkin

75 papers A* 12A 2B 2Journal 49Unranked 9

Year	Rank	Type	Title / Venue / Authors
2025	A*	`conf`	Belief Propagation Guided Decimation on Random k-XORSAT. ICALP Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, Gregory B. Sorkin
2025	J	`jnl`	Belief Propagation Guided Decimation on Random k-XORSAT. CoRR Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, Gregory B. Sorkin
2025	J	`jnl`	Building Hamiltonian cycles in the semi-random graph process in less than 2n rounds. Eur. J. Comb. Alan M. Frieze, Pu Gao, Calum MacRury, Pawel Pralat, Gregory B. Sorkin
2025	J	`jnl`	Perfect Matchings and Loose Hamilton Cycles in the Semirandom Hypergraph Model. Random Struct. Algorithms Michael Molloy, Pawel Pralat, Gregory B. Sorkin
2023	J	`jnl`	Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than 2n Rounds. CoRR Alan M. Frieze, Pu Gao, Calum MacRury, Pawel Pralat, Gregory B. Sorkin
2022	J	`jnl`	Successive minimum spanning trees. Random Struct. Algorithms Svante Janson, Gregory B. Sorkin
2022	J	`jnl`	The Ising Antiferromagnet and Max Cut on Random Regular Graphs. SIAM J. Discret. Math. Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
2021	J	`jnl`	Minimum-Weight Combinatorial Structures Under Random Cost-Constraints. Electron. J. Comb. Alan M. Frieze, Wesley Pegden, Gregory B. Sorkin, Tomasz Tkocz
2020	J	`jnl`	Successive shortest paths in complete graphs with random edge weights. Random Struct. Algorithms Stefanie Gerke, Balázs F. Mezei, Gregory B. Sorkin
2020	J	`jnl`	The Ising antiferromagnet and max cut on random regular graphs. CoRR Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, Gregory B. Sorkin
2019	—	`conf`	Successive Minimum Spanning Trees. APPROX-RANDOM Svante Janson, Gregory B. Sorkin
2019	J	`jnl`	Successive shortest paths in complete graphs with random edge weights. CoRR Stefanie Gerke, Balázs Mezei, Gregory B. Sorkin
2018	J	`jnl`	The Distribution of Minimum-Weight Cliques and Other Subgraphs in Graphs with Random Edge Weights. SIAM J. Discret. Math. Alan M. Frieze, Wesley Pegden, Gregory B. Sorkin
2017	J	`jnl`	Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. ACM Trans. Algorithms Serge Gaspers, Gregory B. Sorkin
2016	J	`jnl`	The Satisfiability Threshold for Comb. Probab. Comput. Boris G. Pittel, Gregory B. Sorkin
2015	J	`jnl`	Efficient algorithms for three-dimensional axial and planar random assignment problems. Random Struct. Algorithms Alan M. Frieze, Gregory B. Sorkin
2015	J	`jnl`	Phase coexistence and torpid mixing in the 3-coloring model on ℤ SIAM J. Discret. Math. David J. Galvin, Jeff Kahn, Dana Randall, Gregory B. Sorkin
2015	—	`conf`	Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets. ICALP (1) Serge Gaspers, Gregory B. Sorkin
2014	J	`jnl`	Conditional Probability Tree Estimation Analysis and Algorithms. CoRR Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl
2014	J	`jnl`	Separate, Measure and Conquer: Faster Algorithms for Max 2-CSP and Counting Dominating Sets. CoRR Serge Gaspers, Gregory B. Sorkin
2013	J	`jnl`	Exponential Algorithms: Algorithms and Complexity Beyond Polynomial Time (Dagstuhl Seminar 13331). Dagstuhl Reports Thore Husfeldt, Ramamohan Paturi, Gregory B. Sorkin, Ryan Williams
2013	J	`jnl`	VCG Auction Mechanism Cost Expectations and Variances. CoRR Svante Janson, Gregory B. Sorkin
2012	J	`jnl`	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. J. Comput. Syst. Sci. Serge Gaspers, Gregory B. Sorkin
2011	J	`jnl`	First-passage percolation on a ladder graph, and the path cost in a VCG auction. Random Struct. Algorithms Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2010	—	`conf`	10441 Abstracts Collection - Exact Complexity of NP-hard Problems. Exact Complexity of NP-hard Problems Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin
2010	J	`jnl`	Average case performance of heuristics for multi-dimensional assignment problems CoRR Alan M. Frieze, Gregory B. Sorkin
2010	J	`jnl`	Average-case performance of heuristics for three-dimensional assignment problems CoRR Alan M. Frieze, Gregory B. Sorkin
2010	—	`ed.`	Exact Complexity of NP-hard Problems, 31.10. - 05.11.2010 Exact Complexity of NP-hard Problems Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, Gregory B. Sorkin
2010	J	`jnl`	Structure of random r-SAT below the pure literal threshold CoRR Alexander D. Scott, Gregory B. Sorkin
2009	J	`jnl`	A tight bound on the collection of edges in MSTs of induced subgraphs. J. Comb. Theory B Gregory B. Sorkin, Angelika Steger, Rico Zenklusen
2009	J	`jnl`	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between CoRR Serge Gaspers, Gregory B. Sorkin
2009	A*	`conf`	A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. SODA Serge Gaspers, Gregory B. Sorkin
2009	—	`conf`	Average-Case Analyses of Vickrey Costs. APPROX-RANDOM Prasad Chebolu, Alan M. Frieze, Páll Melsted, Gregory B. Sorkin
2009	J	`jnl`	Conditional Probability Tree Estimation Analysis and Algorithms CoRR Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl
2009	A	`conf`	Conditional Probability Tree Estimation Analysis and Algorithms. UAI Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl
2009	J	`jnl`	Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function. ACM Trans. Algorithms Alexander D. Scott, Gregory B. Sorkin
2008	J	`jnl`	Robust reductions from ranking to classification. Mach. Learn. Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
2008	—	`conf`	The Power of Choice in a Generalized Pólya Urn Model. APPROX-RANDOM Gregory B. Sorkin
2007	J	`jnl`	Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discret. Optim. Alexander D. Scott, Gregory B. Sorkin
2007	J	`jnl`	Random 2-SAT with Prescribed Literal Degrees. Algorithmica Colin Cooper, Alan M. Frieze, Gregory B. Sorkin
2007	A*	`conf`	Robust Reductions from Ranking to Classification. COLT Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin
2007	J	`jnl`	The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems. SIAM J. Comput. Alan M. Frieze, Gregory B. Sorkin
2006	A	`conf`	An LP-Designed Algorithm for Constraint Satisfaction. ESA Alexander D. Scott, Gregory B. Sorkin
2006	—	`conf`	First-Passage Percolation on a Width-2 Strip and the Path Cost in a VCG Auction. WINE Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2006	J	`jnl`	Linear-programming design and analysis of fast algorithms for Max 2-Sat and Max 2-CSP CoRR Alexander D. Scott, Gregory B. Sorkin
2006	J	`jnl`	Polynomial Constraint Satisfaction: A Framework for Counting and Sampling CSPs and Other Problems CoRR Alexander D. Scott, Gregory B. Sorkin
2006	J	`jnl`	Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time. Comb. Probab. Comput. Alexander D. Scott, Gregory B. Sorkin
2006	J	`jnl`	Vehicle Routing and Staffing for Sedan Service. Transp. Sci. Oktay Günlük, Tracy Kimbrel, Laszlo Ladányi, Baruch Schieber, Gregory B. Sorkin
2005	J	`jnl`	Embracing the giant component. Random Struct. Algorithms Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin
2004	J	`jnl`	A Two-Variable Interlace Polynomial. Comb. Richard Arratia, Béla Bollobás, Gregory B. Sorkin
2004	B	`conf`	Embracing the Giant Component. LATIN Abraham Flaxman, David Gamarnik, Gregory B. Sorkin
2004	J	`jnl`	Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin
2004	J	`jnl`	Strings with Maximally Many Distinct Subsequences and Substrings. Electron. J. Comb. Abraham Flaxman, Aram W. Harrow, Gregory B. Sorkin
2004	J	`jnl`	The interlace polynomial of a graph. J. Comb. Theory B Richard Arratia, Béla Bollobás, Gregory B. Sorkin
2003	—	`conf`	Faster Algorithms for MAX CUT and MAX CSP, with Polynomial Expected Time for Sparse Instances. RANDOM-APPROX Alex D. Scott, Gregory B. Sorkin
2003	A*	`conf`	Random MAX SAT, random MAX CUT, and their phase transitions. SODA Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin
2002	A*	`conf`	A note on random 2-SAT with prescribed literal degrees. SODA Colin Cooper, Alan M. Frieze, Gregory B. Sorkin
2002	J	`jnl`	Exact Expectations And Distributions For The Random Assignment Problem. Comb. Probab. Comput. Sven Erick Alm, Gregory B. Sorkin
2001	—	`conf`	Some Notes on Random Satisfiability. SAGA Gregory B. Sorkin
2001	A*	`conf`	The probabilistic relationship between the assignment and asymmetric traveling salesman problems. SODA Alan M. Frieze, Gregory B. Sorkin
2000	J	`jnl`	Euler circuits and DNA sequencing by hybridization. Discret. Appl. Math. Richard Arratia, Béla Bollobás, Don Coppersmith, Gregory B. Sorkin
2000	J	`jnl`	Gadgets, Approximation, and Linear Programming. SIAM J. Comput. Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
2000	A*	`conf`	Optimal myopic algorithms for random 3-SAT. FOCS Dimitris Achlioptas, Gregory B. Sorkin
2000	A*	`conf`	The interlace polynomial: a new graph polynomial. SODA Richard Arratia, Béla Bollobás, Gregory B. Sorkin
1999	J	`jnl`	Constructive bounds and exact expectations for the random assignment problem. Random Struct. Algorithms Don Coppersmith, Gregory B. Sorkin
1998	J	`jnl`	Constructing Computer Virus Phylogenies. J. Algorithms Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin
1998	—	`conf`	Constructive Bounds and Exact Expectations for the Random Assignment Problem. RANDOM Don Coppersmith, Gregory B. Sorkin
1998	J	`jnl`	The Metropolis Algorithm for Graph Bisection. Discret. Appl. Math. Mark Jerrum, Gregory B. Sorkin
1996	B	`conf`	Constructing Computer Virus Phylogenies. CPM Leslie Ann Goldberg, Paul W. Goldberg, Cynthia A. Phillips, Gregory B. Sorkin
1996	A*	`conf`	Gadgets, Approximation, and Linear Programming (extended abstract). FOCS Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson
1995	A*	`conf`	Biologically Inspired Defenses Against Computer Viruses. IJCAI (1) Jeffrey O. Kephart, Gregory B. Sorkin, William C. Arnold, David M. Chess, Gerald Tesauro, Steve R. White
1993	A*	`conf`	Simulated Annealing for Graph Bisection FOCS Mark Jerrum, Gregory B. Sorkin
1991	J	`jnl`	Efficient Simulated Annealing on Fractal Energy Landscapes. Algorithmica Gregory B. Sorkin
1987	J	`jnl`	Asymptotically Perfect Trivial Global Routing: A Stochastic Analysis. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. Gregory B. Sorkin
1982	A*	`conf`	The planar package planner for system designers. DAC William R. Heller, Gregory B. Sorkin, Klim Maling