David Gamarnik

2009
40	EE	David Gamarnik, Dmitriy Katz: Sequential cavity method for computing limits of the log-partition function for lattice models. SODA 2009: 596-605
2008
39	EE	David Gamarnik, David Goldberg: Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections CoRR abs/0807.1277: (2008)
38	EE	Antar Bandyopadhyay, David Gamarnik: Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models. Random Struct. Algorithms 33(4): 452-479 (2008)
2007
37	EE	David Gamarnik, Dmitriy Katz: Correlation decay and deterministic FPTAS for counting list-colorings of a graph. SODA 2007: 1245-1254
36	EE	Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali: Simple deterministic approximation algorithms for counting matchings. STOC 2007: 122-127
2006
35	EE	Antar Bandyopadhyay, David Gamarnik: Counting without sampling: new algorithms for enumeration problems using statistical physics. SODA 2006: 890-899
34	EE	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
33	EE	Nikhil Bansal, David Gamarnik: Handling load with less stress. Queueing Syst. 54(1): 45-54 (2006)
32	EE	David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method. Random Struct. Algorithms 28(1): 76-106 (2006)
2005
31	EE	David Gamarnik: The expected value of random minimal length spanning tree of a complete graph. SODA 2005: 700-704
30	EE	David Gamarnik, Maxim Sviridenko: Hamiltonian completions of sparse random graphs. Discrete Applied Mathematics 152(1-3): 139-158 (2005)
29	EE	David Gamarnik, Moshe Lewenstein, Maxim Sviridenko: An improved upper bound for the TSP in cubic 3-edge-connected graphs. Oper. Res. Lett. 33(5): 467-474 (2005)
28	EE	Abraham D. Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the giant component. Random Struct. Algorithms 27(3): 277-289 (2005)
2004
27	EE	David Gamarnik, Tomasz Nowicki, Grzegorz Swirszcz: Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method. APPROX-RANDOM 2004: 357-368
26	EE	Abraham Flaxman, David Gamarnik, Gregory B. Sorkin: Embracing the Giant Component. LATIN 2004: 69-79
25	EE	David Gamarnik: Linear phase transition in random linear constraint satisfaction problems. SODA 2004: 111-120
24	EE	Béla Bollobás, David Gamarnik, Oliver Riordan, Benny Sudakov: On the Value of a Random Minimum Weight Steiner Tree. Combinatorica 24(2): 187-207 (2004)
23	EE	David Gamarnik: Stochastic Bandwidth Packing Process: Stability Conditions via Lyapunov Function Technique. Queueing Syst. 48(3-4): 339-363 (2004)
22	EE	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)
21	EE	David Gamarnik, Petar Momcilovic: An asymptotic optimality of the transposition rule for linear lists. SIGMETRICS Performance Evaluation Review 32(2): 33-34 (2004)
2003
20	EE	David Gamarnik: Linear Phase Transition in Random Linear Constraint Satisfaction Problems. DRW 2003: 113-126
19	EE	Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin: Random MAX SAT, random MAX CUT, and their phase transitions. SODA 2003: 364-373
18		David Gamarnik: Extension of the PAC framework to finite and countable Markov chains. IEEE Transactions on Information Theory 49(1): 338-345 (2003)
17	EE	David Gamarnik: Stability of Adaptive and Nonadaptive Packet Routing Policies in Adversarial Queueing Networks. SIAM J. Comput. 32(2): 371-385 (2003)
16	EE	David Gamarnik, John J. Hasenbein: Weak instability in stochastic and fluid queueing networks. SIGMETRICS Performance Evaluation Review 31(2): 9-10 (2003)
2002
15	EE	Don Coppersmith, David Gamarnik, Maxim Sviridenko: The diameter of a long range percolation graph. SODA 2002: 329-337
14	EE	David Gamarnik: On Deciding Stability of Constrained Homogeneous Random Walks and Queueing Systems. Math. Oper. Res. 27(2): 272-293 (2002)
13	EE	Don Coppersmith, David Gamarnik, Maxim Sviridenko: The diameter of a long-range percolation graph. Random Struct. Algorithms 21(1): 1-13 (2002)
12	EE	David Gamarnik: Computing stationary probability distributions and large deviation rates for constrained random walks.: the undecidability results. SIGMETRICS Performance Evaluation Review 30(3): 38-40 (2002)
2001
11	EE	David Gamarnik: On deciding stability of constrained random walks and queueing systems. SIGMETRICS Performance Evaluation Review 28(4): 39-40 (2001)
10	EE	David Gamarnik: Stochastic online binpacking problem: exact conditions for bounded expected queue lengths under the best fit packing heuristic. SIGMETRICS Performance Evaluation Review 29(3): 30-31 (2001)
2000
9	EE	David Gamarnik: On deciding stability of scheduling policies in queueing systems. SODA 2000: 467-476
1999
8	EE	David Gamarnik: Extension of the PAC Framework to Finite and Countable Markov Chains. COLT 1999: 308-317
7	EE	David Gamarnik: Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. STOC 1999: 206-214
6		Dimitris Bertsimas, David Gamarnik: Asymptotically Optimal Algorithms for Job Shop Scheduling and Packet Routing. J. Algorithms 33(2): 296-318 (1999)
5		Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. Machine Learning 35(3): 225-245 (1999)
4	EE	Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Performance analysis of multiclass queueing networks. SIGMETRICS Performance Evaluation Review 27(3): 11-14 (1999)
1998
3	EE	David Gamarnik: Efficient Learning of Monotone Concepts via Quadratic Optimization. COLT 1998: 134-143
2	EE	David Gamarnik: Stability of Adversarial Queues via Fluid Models. FOCS 1998: 60-70
1997
1	EE	Dimitris Bertsimas, David Gamarnik, John N. Tsitsiklis: Estimation of Time-Varying Parameters in Statistical Models: An Optimization Approach. COLT 1997: 314-324

Coauthor Index

1	Antar Bandyopadhyay	[35] [38]
2	Nikhil Bansal	[33]
3	Mohsen Bayati	[36]
4	Dimitris Bertsimas	[1] [4] [5] [6]
5	Béla Bollobás	[24]
6	Don Coppersmith	[13] [15] [19] [22]
7	Abraham D. Flaxman (Abraham Flaxman)	[26] [28] [34]
8	David Goldberg	[39]
9	Mohammad Taghi Hajiaghayi (MohammadTaghi Hajiaghayi)	[19] [22]
10	John J. Hasenbein	[16]
11	Dimitriy A. Katz	[36]
12	Dmitriy Katz	[37] [40]
13	Moshe Lewenstein	[29]
14	Petar Momcilovic	[21]
15	Chandra Nair	[36]
16	Tomasz Nowicki	[27] [32]
17	Oliver Riordan	[24]
18	Gregory B. Sorkin	[19] [22] [26] [28] [34]
19	Benny Sudakov	[24]
20	Maxim Sviridenko	[13] [15] [29] [30]
21	Grzegorz Swirszcz	[27] [32]
22	Prasad Tetali	[36]
23	John N. Tsitsiklis	[1] [4] [5]

Colors in the list of coauthors