Random Structures and Algorithms

2005

The phase transition in the uniformly grown random graph has infinite order
by: Béla Bollobás, Svante Janson, Oliver Riordan v. 26 i. 1-2 p. 1 - 36
Hunting for sharp thresholds
by: Ehud Friedgut v. 26 i. 1-2 p. 37 - 51
Vertex and edge expansion properties for rapid mixing
by: Ravi Montenegro v. 26 i. 1-2 p. 52 - 68
Asymptotic degree distribution in random recursive trees
by: Svante Janson v. 26 i. 1-2 p. 69 - 83
The climbing depth of random trees
by: Alois Panholzer v. 26 i. 1-2 p. 84 - 109
Integer and fractional packing of families of graphs
by: Raphael Yuster v. 26 i. 1-2 p. 110 - 118
How complex are random graphs in first order logic?
by: Jeong Han Kim, Oleg Pikhurko, Joel H. Spencer, Oleg Verbitsky v. 26 i. 1-2 p. 119 - 145
Combinatorial dimension in fractional Cartesian products
by: Ron Blei, Fuchang Gao v. 26 i. 1-2 p. 146 - 159
Counting subgraphs in quasi-random 4-uniform hypergraphs
by: Vojtech Rödl, Jozef Skokan v. 26 i. 1-2 p. 160 - 203
Positional games on random graphs
by: Milos Stojakovic, Tibor Szabó v. 26 i. 1-2 p. 204 - 223
Concentration of vertex degrees in a scale-free random graph process
by: Jerzy Szymanski v. 26 i. 1-2 p. 224 - 236
A proof of a conjecture of Buck, Chan, and Robbins on the expected value of the minimum assignment
by: Johan Wästlund v. 26 i. 1-2 p. 237 - 251
Large Kr-free subgraphs in Ks-free graphs and some other Ramsey-type problems
by: Benny Sudakov v. 26 i. 3 p. 253 - 265
On the probability of rendezvous in graphs
by: Martin Dietzfelbinger, Hisao Tamaki v. 26 i. 3 p. 266 - 288
Testing graphs for colorability properties
by: Eldar Fischer v. 26 i. 3 p. 289 - 309
Percolation in Voronoi tilings
by: P. Balister, B. Bollobás, A. Quas v. 26 i. 3 p. 310 - 318
Perfect matchings in random bipartite graphs with minimal degree at least 2
by: Alan M. Frieze v. 26 i. 3 p. 319 - 358
Transfer theorems and asymptotic distributional results for m-ary search trees
by: James Allen Fill, Nevin Kapur v. 26 i. 4 p. 359 - 391
Continuum percolation with steps in the square or the disc
by: Paul N. Balister, Béla Bollobás, Mark Walters v. 26 i. 4 p. 392 - 403
Limit distribution of the number of consecutive records
by: Hua-Huai Chern, Hsien-Kuei Hwang v. 26 i. 4 p. 404 - 417
Coin flipping from a cosmic source: On error correction of truly random bits
by: Elchanan Mossel, Ryan O'Donnell v. 26 i. 4 p. 418 - 436
Generating random elements of abelian groups
by: András Lukács v. 26 i. 4 p. 437 - 445
Steady state analysis of balanced-allocation routing
by: Aris Anagnostopoulos, Ioannis Kontoyiannis, Eli Upfal v. 26 i. 4 p. 446 - 467

2004

Coloring uniform hypergraphs with few colors
by: Alexandr V. Kostochka v. 24 i. 1 p. 1 - 10
Randomization helps to perform independent tasks reliably
by: Bogdan S. Chlebus, Dariusz R. Kowalski v. 24 i. 1 p. 11 - 41
The emergence of a giant component in random subgraphs of pseudo-random graphs
by: Alan M. Frieze, Michael Krivelevich, Ryan Martin v. 24 i. 1 p. 42 - 50
A stochastic model for solitons
by: Yoshiaki Itoh, Hosam M. Mahmoud, Daisuke Takahashi v. 24 i. 1 p. 51 - 64
Deviation inequality for monotonic Boolean functions with application to the number of k-cycles in a random graph
by: Dmitry Panchenko v. 24 i. 1 p. 65 - 74
General urn models with several types of balls and Gaussian limiting fields
by: Michael Drmota, Danièle Gardy, Bernhard Gittenberger v. 24 i. 1 p. 75 - 103
Adding random edges to dense graphs
by: Tom Bohman, Alan M. Frieze, Michael Krivelevich, Ryan Martin v. 24 i. 2 p. 105 - 117
The rotation correspondence is asymptotically a dilatation
by: Jean-François Marckert v. 24 i. 2 p. 118 - 132
m-ary Search trees when m ge 27: A strong asymptotics for the space requirements
by: Brigitte Chauvin, Nicolas Pouyanne v. 24 i. 2 p. 133 - 154
Counting the onion
by: Ketan Dalal v. 24 i. 2 p. 155 - 165
Divide and conquer martingales and the number of triangles in a random graph
by: Jeong Han Kim, Van H. Vu v. 24 i. 2 p. 166 - 174
Functions that have read-twice constant width branching programs are not necessarily testable
by: Eldar Fischer, Ilan Newman, Jiri Sgall v. 24 i. 2 p. 175 - 193
K5-free subgraphs of random graphs
by: Stefanie Gerke, Thomas Schickinger, Angelika Steger v. 24 i. 2 p. 194 - 232
Large deviations for sums of partly dependent random variables
by: Svante Janson v. 24 i. 3 p. 234 - 248
The vertex degree distribution of random intersection graphs
by: Dudley Stark v. 24 i. 3 p. 249 - 258
Exact and approximative algorithms for coloring G(n, p)
by: Amin Coja-Oghlan, Anusch Taraz v. 24 i. 3 p. 259 - 278
Random sampling of 3-colorings in Z2
by: Leslie Ann Goldberg, Russell A. Martin, Mike Paterson v. 24 i. 3 p. 279 - 302
A second threshold for the hard-core model on a Bethe lattice
by: Graham Brightwell, Peter Winkler v. 24 i. 3 p. 303 - 314
Phase diagram for the constrained integer partitioning problem
by: Christian Borgs, Jennifer T. Chayes, Stephan Mertens, Boris Pittel v. 24 i. 3 p. 315 - 380
Essential edges in Poisson random hypergraphs
by: Christina Goldschmidt, James Norris v. 24 i. 4 p. 381 - 396
Continuous and discontinuous phase transitions in hypergraph processes
by: R. W. R. Darling, David A. Levin, James R. Norris v. 24 i. 4 p. 397 - 419
Building uniformly random subtrees
by: Malwina Luczak, Peter Winkler v. 24 i. 4 p. 420 - 443
Negative association in uniform forests and connected graphs
by: Geoffrey R. Grimmett, S. N. Winkler v. 24 i. 4 p. 444 - 460
Mixing in time and space for lattice spin systems: A combinatorial view
by: Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz v. 24 i. 4 p. 461 - 479
Self-destructive percolation
by: J. van den Berg, Rachel Brouwer v. 24 i. 4 p. 480 - 501
Random MAX SAT, random MAX CUT, and their phase transitions
by: Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin v. 24 i. 4 p. 502 - 545
Regularity Lemma for k-uniform hypergraphs
by: Vojtech Rödl, Jozef Skokan v. 25 i. 1 p. 1 - 42
Data structures for maintaining set partitions
by: Michael A. Bender, Saurabh Sethia, Steven Skiena v. 25 i. 1 p. 43 - 67
A (1 + varepsilon )-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lova'sz Local Lemma
by: Mohammad R. Salavatipour v. 25 i. 1 p. 68 - 90
Identifying several biased coins encountered by a hidden random walk
by: David A. Levin, Yuval Peres v. 25 i. 1 p. 91 - 114
Correction: Small worlds
by: Andrew D. Barbour, Gesine Reinert v. 25 i. 1 p. 115 - 115
On the advantage over a random assignment
by: Johan Håstad, S. Venkatesh v. 25 i. 2 p. 117 - 149
Is constraint satisfaction over two variables always easy?
by: Lars Engebretsen, Venkatesan Guruswami v. 25 i. 2 p. 150 - 178
The distribution of the size of the ancestor-tree and of the induced spanning subtree for random trees
by: Alois Panholzer v. 25 i. 2 p. 179 - 207
Some bounds on the coupon collector problem
by: Servet Martínez v. 25 i. 2 p. 208 - 226
Reversible coagulation-fragmentation processes and random combinatorial structures: Asymptotics for the number of groups
by: Michael M. Erlihson, Boris L. Granovsky v. 25 i. 2 p. 227 - 245
On the number of full levels in tries
by: Charles Knessl, Wojciech Szpankowski v. 25 i. 3 p. 247 - 276
Random covering of an interval and a variation of Kingman's coalescent
by: Jean Bertoin v. 25 i. 3 p. 277 - 292
Simply generated trees, B-series and Wigner processes
by: Christian Mazza v. 25 i. 3 p. 293 - 310
The shape of large Galton-Watson trees with possibly infinite variance
by: Jochen Geiger, Lars Kauffmann v. 25 i. 3 p. 311 - 335
Random walks on the torus with several generators
by: Timothy Prescott, Francis Edward Su v. 25 i. 3 p. 336 - 345
Corrigendum: The complexity of counting graph homomorphisms
by: Martin E. Dyer, Catherine S. Greenhill v. 25 i. 3 p. 346 - 352
The cores of random hypergraphs with a given degree sequence
by: Colin Cooper v. 25 i. 4 p. 353 - 375
Directed graphs, Hamiltonicity and doubly stochastic matrices
by: Vivek S. Borkar, Vladimir Ejov, Jerzy A. Filar v. 25 i. 4 p. 376 - 395
On the clustering of independent uniform random variables
by: Sándor Csörgo, Wei Biao Wu v. 25 i. 4 p. 396 - 420
De Bruijn cycles for covering codes
by: Fan Chung, Joshua N. Cooper v. 25 i. 4 p. 421 - 431
Avoidance of a giant component in half the edge set of a random graph
by: Tom Bohman, Alan M. Frieze, Nicholas C. Wormald v. 25 i. 4 p. 432 - 449

2003

On the probability of independent sets in random graphs
by: Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald v. 22 i. 1 p. 1 - 14
Renewal processes on partially ordered sets
by: Kyle Siegrist v. 22 i. 1 p. 15 - 32
How many random edges make a dense graph hamiltonian?
by: Tom Bohman, Alan M. Frieze, Ryan Martin v. 22 i. 1 p. 33 - 42
A bounding chain for Swendsen-Wang
by: Mark Huber v. 22 i. 1 p. 43 - 59
An elementary proof of a theorem of Johnson and Lindenstrauss
by: Sanjoy Dasgupta, Anupam Gupta v. 22 i. 1 p. 60 - 65
On the swapping algorithm
by: Neal Madras, Zhongrong Zheng v. 22 i. 1 p. 66 - 97
Testing membership in parenthesis languages
by: Michal Parnas, Dana Ron, Ronitt Rubinfeld v. 22 i. 1 p. 98 - 138
Simple analysis of graph tests for linearity and PCP
by: Johan Håstad, Avi Wigderson v. 22 i. 2 p. 139 - 160
The shortest disjunctive normal form of a random Boolean function
by: Nicholas Pippenger v. 22 i. 2 p. 161 - 186
Random channel assignment in the plane
by: Colin McDiarmid v. 22 i. 2 p. 187 - 212
Minors in graphs of large girth
by: Daniela Kühn, Deryk Osthus v. 22 i. 2 p. 213 - 225
The number of k-SAT functions
by: Béla Bollobás, Graham Brightwell v. 22 i. 3 p. 227 - 247
Integer and fractional packings in dense 3-uniform hypergraphs
by: Penny E. Haxell, Brendan Nagle, Vojtech Rödl v. 22 i. 3 p. 248 - 310
A general model of web graphs
by: Colin Cooper, Alan M. Frieze v. 22 i. 3 p. 311 - 335
The Wiener Index of simply generated random trees
by: Svante Janson v. 22 i. 4 p. 337 - 358
Regular pairs in sparse random graphs I
by: Yoshiharu Kohayakawa, Vojtech Rödl v. 22 i. 4 p. 359 - 434
A note on scrambling permutations
by: Jaikumar Radhakrishnan v. 22 i. 4 p. 435 - 439
Notes on the variance of the number of maxima in three dimensions
by: Anna Carlsund v. 22 i. 4 p. 440 - 447
Deterministic approximation of the cover time
by: Uriel Feige, Yuri Rabinovich v. 23 i. 1 p. 1 - 22
Three theorems regarding testing graph properties
by: Oded Goldreich, Luca Trevisan v. 23 i. 1 p. 23 - 57
Rate of convergence of crossover operators
by: Yann Ollivier v. 23 i. 1 p. 58 - 72
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
by: Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski v. 23 i. 1 p. 73 - 91
Space complexity of random formulae in resolution
by: Eli Ben-Sasson, Nicola Galesi v. 23 i. 1 p. 92 - 109
Perfect matchings in random uniform hypergraphs
by: Jeong Han Kim v. 23 i. 2 p. 111 - 132
The computational complexity of two-state spin systems
by: Leslie Ann Goldberg, Mark Jerrum, Mike Paterson v. 23 i. 2 p. 133 - 154
Coalescing times for IID random variables with applications to population biology
by: Ilan Adler, Hyun-Soo Ahn, Richard M. Karp, Sheldon M. Ross v. 23 i. 2 p. 155 - 166
Randomly coloring graphs with lower bounds on girth and maximum degree
by: Martin E. Dyer, Alan M. Frieze v. 23 i. 2 p. 167 - 179
Proof of a tiling conjecture of Komlós
by: Ali Shokoufandeh, Yi Zhao v. 23 i. 2 p. 180 - 205
On smallest triangles
by: Geoffrey R. Grimmett, Svante Janson v. 23 i. 2 p. 206 - 223
Turán's theorem in sparse random graphs
by: Tibor Szabó, Van H. Vu v. 23 i. 3 p. 225 - 234
On the distribution of the number of roots of polynomials and explicit weak designs
by: Tzvika Hartman, Ran Raz v. 23 i. 3 p. 235 - 263
Regularity properties for triple systems
by: Brendan Nagle, Vojtech Rödl v. 23 i. 3 p. 264 - 332
On the noise sensitivity of monotone functions
by: Elchanan Mossel, Ryan O'Donnell v. 23 i. 3 p. 333 - 350
On large intersecting subfamilies of uniform setfamilies
by: Richard A. Duke, Paul Erdös, Vojtech Rödl v. 23 i. 4 p. 351 - 356
Random suffix search trees
by: Luc Devroye, Ralph Neininger v. 23 i. 4 p. 357 - 396
On restricted min-wise independence of permutations
by: Jirí Matousek, Milos Stojakovic v. 23 i. 4 p. 397 - 408
Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints
by: Noga Alon, Tao Jiang, Zevi Miller, Dan Pritikin v. 23 i. 4 p. 409 - 433
Speeding up the FMMR perfect sampling algorithm: A case study revisited
by: Robert P. Dobrow, James Allen Fill v. 23 i. 4 p. 434 - 452

2002

Random lifts of graphs: Independence and chromatic number
by: Alon Amit, Nathan Linial, Jirí Matousek v. 20 i. 1 p. 1 - 22
New and faster filters for multiple approximate string matching
by: Ricardo A. Baeza-Yates, Gonzalo Navarro v. 20 i. 1 p. 23 - 49
Inexpensive d-dimensional matchings
by: Bae-Shi Huang, Ljubomir Perkovic, Eric Schmutz v. 20 i. 1 p. 50 - 58
An O(n2) bound for the relaxation time of a Markov chain on cladograms
by: Jason Schweinsberg v. 20 i. 1 p. 59 - 70
Fibonacci solitaire
by: Alexander Gnedin, Sergei Kerov v. 20 i. 1 p. 71 - 88
Vertex-distinguishing edge colorings of random graphs
by: Paul Balister v. 20 i. 1 p. 89 - 97
Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs
by: Martin E. Dyer, Catherine S. Greenhill, Michael Molloy v. 20 i. 1 p. 98 - 114
Noncrossing trees are almost conditioned Galton-Watson trees
by: Jean-François Marckert, Alois Panholzer v. 20 i. 1 p. 115 - 125
Addendum to avoiding a giant component
by: Tom Bohman, Alan M. Frieze v. 20 i. 1 p. 126 - 130
Extremal problems on set systems
by: Peter Frankl, Vojtech Rödl v. 20 i. 2 p. 131 - 164
Testing the diameter of graphs
by: Michal Parnas, Dana Ron v. 20 i. 2 p. 165 - 183
Testing properties of directed graphs: acyclicity and connectivity
by: Michael A. Bender, Dana Ron v. 20 i. 2 p. 184 - 205
The average-case area of Heilbronn-type triangles
by: Tao Jiang, Ming Li, Paul M. B. Vitányi v. 20 i. 2 p. 206 - 219
Right order spectral gap estimates for generating sets of Z4
by: Matthias Löwe, Christian Meise v. 20 i. 2 p. 220 - 238
Evasive random walks and the clairvoyant demon
by: Aaron Abrams, Henry Landau, Zeph Landau, James Pommersheim, Eric Zaslow v. 20 i. 2 p. 239 - 248
Two-coloring random hypergraphs
by: Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali v. 20 i. 2 p. 249 - 259
Preface
by: Tibor Jordán, Alessandro Panconesi v. 20 i. 3 p. 261 - 261
Concentration of non-Lipschitz functions and applications
by: Van H. Vu v. 20 i. 3 p. 262 - 316
The infamous upper tail
by: Svante Janson, Andrzej Rucinski v. 20 i. 3 p. 317 - 342
Randomized metarounding
by: Robert D. Carr, Santosh Vempala v. 20 i. 3 p. 343 - 352
The Random-Facet simplex algorithm on combinatorial cubes
by: Bernd Gärtner v. 20 i. 3 p. 353 - 381
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
by: Eran Halperin, Uri Zwick v. 20 i. 3 p. 382 - 402
On the optimality of the random hyperplane rounding technique for MAX CUT
by: Uriel Feige, Gideon Schechtman v. 20 i. 3 p. 403 - 440
Linear waste of best fit bin packing on skewed distributions
by: Claire Kenyon, Michael Mitzenmacher v. 20 i. 3 p. 441 - 464
Approximation algorithms for the covering Steiner problem
by: Goran Konjevod, R. Ravi, Aravind Srinivasan v. 20 i. 3 p. 465 - 482
The phase transition in random horn satisfiability and its algorithmic implications
by: Gabriel Istrate v. 20 i. 4 p. 483 - 506
Bond percolation critical probability bounds for three Archimedean lattices
by: John C. Wierman v. 20 i. 4 p. 507 - 518
On the covariance of the level sizes in random recursive trees
by: Remco van der Hofstad, Gerard Hooghiemstra, Piet Van Mieghem v. 20 i. 4 p. 519 - 539
On mixing times for stratified walks on the d-cube
by: Nancy Garcia, José Luis Palacios v. 20 i. 4 p. 540 - 552
Gaussian averages, Bernoulli averages, and Gibbs' measures
by: Michel Talagrand v. 21 i. 3-4 p. 197 - 204
On the discrepancy of combinatorial rectangles
by: Noga Alon, Benjamin Doerr, Tomasz Luczak, Tomasz Schoen v. 21 i. 3-4 p. 205 - 215
On the asymmetry of random regular graphs and random graphs
by: Jeong Han Kim, Benny Sudakov, Van H. Vu v. 21 i. 3-4 p. 216 - 224
Random dyadic tilings of the unit square
by: Svante Janson, Dana Randall, Joel Spencer v. 21 i. 3-4 p. 225 - 251
A unified approach to the analysis of Horton-Strahler parameters of binary tree structures
by: Markus E. Nebel v. 21 i. 3-4 p. 252 - 277
The minimum expectation selection problem
by: David Eppstein, George S. Lueker v. 21 i. 3-4 p. 278 - 292
On characterizing hypergraph regularity
by: Y. Dementieva, Penny E. Haxell, Brendan Nagle, Vojtech Rödl v. 21 i. 3-4 p. 293 - 335
Nonrepetitive colorings of graphs
by: Noga Alon, Jaroslaw Grytczuk, Mariusz Haluszczak, Oliver Riordan v. 21 i. 3-4 p. 336 - 346
Crossing numbers of random graphs
by: Joel Spencer, Géza Tóth v. 21 i. 3-4 p. 347 - 358
Testing subgraphs in large graphs
by: Noga Alon v. 21 i. 3-4 p. 359 - 370
Distributed algorithms with dynamical random transitions
by: Nadine Guillotin-Plantard, René Schott v. 21 i. 3-4 p. 371 - 396
Decycling numbers of random regular graphs
by: Sheng Bau, Nicholas C. Wormald, Sanming Zhou v. 21 i. 3-4 p. 397 - 413
Problems and results on judicious partitions
by: Béla Bollobás, Alex D. Scott v. 21 i. 3-4 p. 414 - 430
The diameter of a long-range percolation graph
by: Don Coppersmith, David Gamarnik, Maxim Sviridenko v. 21 i. 1 p. 1 - 13
Property testers for dense constraint satisfaction programs on finite domains
by: Gunnar Andersson, Lars Engebretsen v. 21 i. 1 p. 14 - 32
On the expected value of the minimum assignment
by: Marshall W. Buck, Clara S. Chan, David P. Robbins v. 21 i. 1 p. 33 - 58
Asymptotic analysis of (3, 2, 1)-shell sort
by: Robert T. Smythe, J. A. Wellner v. 21 i. 1 p. 59 - 75
Phase transition for Parking blocks, Brownian excursion and coalescence
by: Philippe Chassaing, Guy Louchard v. 21 i. 1 p. 76 - 119
The decomposition threshold for bipartite graphs with minimum degree one
by: Raphael Yuster v. 21 i. 2 p. 121 - 134
Improved bounds for sampling contingency tables
by: Ben J. Morris v. 21 i. 2 p. 135 - 146
Minimum independent dominating sets of random cubic graphs
by: William Duckworth, Nicholas C. Wormald v. 21 i. 2 p. 147 - 161
Largest planar matching in random bipartite graphs
by: Marcos A. Kiwi, Martin Loebl v. 21 i. 2 p. 162 - 181
On the critical exponents of random k-SAT
by: David Bruce Wilson v. 21 i. 2 p. 182 - 195

2001

Coupling vs. conductance for the Jerrum-Sinclair chain
by: V. S. Anil Kumar, H. Ramesh v. 18 i. 1 p. 1 - 17
Completeness and robustness properties of min-wise independent permutations
by: Andrei Z. Broder, Michael Mitzenmacher v. 18 i. 1 p. 18 - 30
Bisecting sparse random graphs
by: Malwina J. Luczak, Colin McDiarmid v. 18 i. 1 p. 31 - 38
Compound Poisson approximations of subgraph counts in random graphs
by: Dudley Stark v. 18 i. 1 p. 39 - 60
Random maximal H-free graphs
by: Deryk Osthus, Anusch Taraz v. 18 i. 1 p. 61 - 82
Hamilton cycles in the union of random permutations
by: Alan M. Frieze v. 18 i. 1 p. 83 - 94
The union of two random permutations does not have a directed Hamilton cycle
by: Colin Cooper v. 18 i. 1 p. 95 - 98
Erratum to Bounding the Unsatisfiability Threshold of Random 3-SAT
by: Svante Janson, Yannis C. Stamatiou, Malvina Vamvakari v. 18 i. 1 p. 99 - 100
Very rapidly mixing Markov chains for 2-colorings and for independent sets in a graph with maximum degree 4
by: Michael Molloy v. 18 i. 2 p. 101 - 115
Algorithms for graph partitioning on the planted partition model
by: Anne Condon, Richard M. Karp v. 18 i. 2 p. 116 - 140
Biased positional games and the phase transition
by: Malgorzata Bednarska, Tomasz Luczak v. 18 i. 2 p. 141 - 152
The Boyer-Moore-Horspool heuristic with Markovian input
by: Robert T. Smythe v. 18 i. 2 p. 153 - 163
A phase transition phenomenon in a random directed acyclic graph
by: Boris Pittel, R. Tungol v. 18 i. 2 p. 164 - 184
On the effect of selection in genetic algorithms
by: Christian Mazza, Didier Piau v. 18 i. 2 p. 185 - 200
The scaling window of the 2-SAT transition
by: Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, David Bruce Wilson v. 18 i. 3 p. 201 - 256
Infinite paths in randomly oriented lattices
by: Geoffrey R. Grimmett v. 18 i. 3 p. 257 - 266
A note on disagreement percolation
by: Olle Häggström v. 18 i. 3 p. 267 - 278
The degree sequence of a scale-free random graph process
by: Béla Bollobás, Oliver Riordan, Joel Spencer, Gábor E. Tusnády v. 18 i. 3 p. 279 - 290
On the maximum number of Hamiltonian paths in tournaments
by: Ilan Adler, Noga Alon, Sheldon M. Ross v. 18 i. 3 p. 291 - 296
Randomized allocation processes
by: Artur Czumaj, Volker Stemann v. 18 i. 4 p. 297 - 331
On the value of the critical point in fractal percolation
by: Damien G. White v. 18 i. 4 p. 332 - 345
Random regular graphs of high degree
by: Michael Krivelevich, Benny Sudakov, Van H. Vu, Nicholas C. Wormald v. 18 i. 4 p. 346 - 363
Parking with density
by: Jean-François Marckert v. 18 i. 4 p. 364 - 380
The zeta(2) limit in the random assignment problem
by: David Aldous v. 18 i. 4 p. 381 - 418
D·E·K=(1000)8
by: Philippe Flajolet v. 19 i. 3-4 p. 150 - 162
Random maps, coalescing saddles, singularity analysis, and Airy phenomena
by: Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria v. 19 i. 3-4 p. 194 - 246
Phase transition and finite-size scaling for the integer partitioning problem
by: Christian Borgs, Jennifer T. Chayes, Boris Pittel v. 19 i. 3-4 p. 247 - 288
Size and path length of Patricia tries: Dynamical sources context
by: Jérémie Bourdon v. 19 i. 3-4 p. 289 - 315
Phase changes in random m-ary search trees and generalized quicksort
by: Hua-Huai Chern, Hsien-Kuei Hwang v. 19 i. 3-4 p. 316 - 358
Analysis of random LC tries
by: Luc Devroye v. 19 i. 3-4 p. 359 - 375
Approximating the limiting Quicksort distribution
by: James Allen Fill, Svante Janson v. 19 i. 3-4 p. 376 - 406
Distinctness of compositions of an integer: A probabilistic analysis
by: Pawel Hitczenko, Guy Louchard v. 19 i. 3-4 p. 407 - 437
Asymptotic distribution for the cost of linear probing hashing
by: Svante Janson v. 19 i. 3-4 p. 438 - 471
A generic approach for the unranking of labeled combinatorial classes
by: Conrado Martinez, Xavier Molinero v. 19 i. 3-4 p. 472 - 497
On a multivariate contraction method for random recursive structures with applications to Quicksort
by: Ralph Neininger v. 19 i. 3-4 p. 498 - 524
Analysis of Rabin's irreducibility test for polynomials over finite fields
by: Daniel Panario, Boris Pittel, Bruce Richmond, Alfredo Viola v. 19 i. 3-4 p. 525 - 551
Some applications of the q-Rice formula
by: Helmut Prodinger v. 19 i. 3-4 p. 552 - 557
On probabilistic elimination of generalized quantifiers
by: Risto Kaila v. 19 i. 1 p. 1 - 36
On the structure of clique-free graphs
by: Hans Jürgen Prömel, Thomas Schickinger, Angelika Steger v. 19 i. 1 p. 37 - 53
Small worlds
by: Andrew D. Barbour, Gesine Reinert v. 19 i. 1 p. 54 - 74
Avoiding a giant component
by: Tom Bohman, Alan M. Frieze v. 19 i. 1 p. 75 - 85
On the chromatic number of set systems
by: Alexandr V. Kostochka, Dhruv Mubayi, Vojtech Rödl, Prasad Tetali v. 19 i. 2 p. 87 - 98
Cube Ramsey numbers are polynomial
by: Shi Lingsheng v. 19 i. 2 p. 99 - 101
The diameter of long-range percolation clusters on finite cycles
by: Itai Benjamini, Noam Berger v. 19 i. 2 p. 102 - 111
Martingales and large deviations for binary search trees
by: Jean Jabbour-Hattab v. 19 i. 2 p. 112 - 127
Hamilton cycles containing randomly selected edges in random regular graphs
by: Robert W. Robinson, Nicholas C. Wormald v. 19 i. 2 p. 128 - 147

2000

Ten Years!
by: Michal Karonski, Joel Spencer v. 16 i. 1 p. 1 - 3
Improved bounds and algorithms for hypergraph 2-coloring
by: Jaikumar Radhakrishnan, Aravind Srinivasan v. 16 i. 1 p. 4 - 32
Average-case complexity of shortest-paths problems in the vertex-potential model
by: Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe v. 16 i. 1 p. 33 - 46
Asymptotic enumeration of tournaments with a given score sequence containing a specified digraph
by: Zhicheng Gao, Brendan D. McKay, Xiaoji Wang v. 16 i. 1 p. 47 - 57
Dependent percolation and colliding random walks
by: Peter Winkler v. 16 i. 1 p. 58 - 84
Lollipop graphs are extremal for commute times
by: Johan Jonasson v. 16 i. 2 p. 131 - 142
Energy of flows on Z2 percolation clusters
by: Christopher Hoffman v. 16 i. 2 p. 143 - 155
Random intersection graphs when m=omega(n): An equivalence theorem relating the evolution of the G(n, m, p) and G(n, p) models
by: James Allen Fill, Edward R. Scheinerman, Karen B. Singer-Cohen v. 16 i. 2 p. 156 - 176
The length of random subsets of Boolean lattices
by: Yoshiharu Kohayakawa, Bernd Kreuter, Deryk Osthus v. 16 i. 2 p. 177 - 194
Finding and certifying a large hidden clique in a semirandom graph
by: Uriel Feige, Robert Krauthgamer v. 16 i. 2 p. 195 - 208
On the rank of random matrices
by: Colin Cooper v. 16 i. 2 p. 209 - 232
On random orderings of variables for parity ordered binary decision diagrams
by: Petr Savický v. 16 i. 3 p. 233 - 239
Average-case analyses of first fit and random fit bin packing
by: Susanne Albers, Michael Mitzenmacher v. 16 i. 3 p. 240 - 259
On triangle-free random graphs
by: Tomasz Luczak v. 16 i. 3 p. 260 - 276
A sharp concentration inequality with applications
by: Stéphane Boucheron, Gábor Lugosi, Pascal Massart v. 16 i. 3 p. 277 - 292
MODp-tests, almost independence and small probability spaces
by: Claudia Bertram-Kretzberg, Hanno Lefmann v. 16 i. 4 p. 293 - 313
Polynomial time approximation of dense weighted instances of MAX-CUT
by: Wenceslas Fernandez de la Vega, Marek Karpinski v. 16 i. 4 p. 314 - 332
Percolation in a dependent random environment
by: Johan Jonasson, Elchanan Mossel, Yuval Peres v. 16 i. 4 p. 333 - 343
On the concentration of multivariate polynomials with small expectation
by: Van H. Vu v. 16 i. 4 p. 344 - 363
Degrees and choice numbers
by: Noga Alon v. 16 i. 4 p. 364 - 368
Hamilton cycles in random graphs and directed graphs
by: Colin Cooper, Alan M. Frieze v. 16 i. 4 p. 369 - 401
Distribution of the number of consecutive records
by: Hua-Huai Chern, Hsien-Kuei Hwang, Yeong-Nan Yeh v. 17 i. 3-4 p. 169 - 196
On the distribution of rank of a random matrix over a finite field
by: Colin Cooper v. 17 i. 3-4 p. 197 - 212
Coloring nonuniform hypergraphs: A new algorithmic approach to the general Lovász local lemma
by: Artur Czumaj, Christian Scheideler v. 17 i. 3-4 p. 213 - 237
Delayed path coupling and generating random permutations
by: Artur Czumaj, Miroslaw Kutylowski v. 17 i. 3-4 p. 238 - 259
The complexity of counting graph homomorphisms
by: Martin E. Dyer, Catherine S. Greenhill v. 17 i. 3-4 p. 260 - 289
Extension of Fill's perfect rejection sampling algorithm to general chains
by: James Allen Fill, Motoya Machida, Duncan J. Murdoch, Jeffrey S. Rosenthal v. 17 i. 3-4 p. 290 - 316
Large components of bipartite random mappings
by: Jennie C. Hansen, Jerzy Jaworski v. 17 i. 3-4 p. 317 - 342
Growth of components in random graphs
by: Svante Janson v. 17 i. 3-4 p. 343 - 356
The strong chromatic index of C4-free graphs
by: Mohammad Mahdian v. 17 i. 3-4 p. 357 - 375
Near-optimal list colorings
by: Michael Molloy, Bruce A. Reed v. 17 i. 3-4 p. 376 - 402
Asymptotic distributions for partial match queries in K-d trees
by: Ralph Neininger v. 17 i. 3-4 p. 403 - 427
Limiting distributions for the costs of partial match retrievals in multidimensional tries
by: Werner Schachinger v. 17 i. 3-4 p. 428 - 459
Sharp thresholds for certain Ramsey properties of random graphs
by: Ehud Friedgut, Michael Krivelevich v. 17 i. 1 p. 1 - 19
Upper bounds on the height difference of the Gaussian random field and the range of random graph homomorphisms into Z
by: Itai Benjamini, Gideon Schechtman v. 17 i. 1 p. 20 - 25
Complete minors in pseudorandom graphs
by: Andrew Thomason v. 17 i. 1 p. 26 - 28
New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
by: Van H. Vu v. 17 i. 1 p. 29 - 63
Construction of expanders and superconcentrators using Kolmogorov complexity
by: Uwe Schöning v. 17 i. 1 p. 64 - 77
On a random graph with immigrating vertices: Emergence of the giant component
by: David Aldous, Boris Pittel v. 17 i. 2 p. 79 - 102
Bounding the unsatisfiability threshold of random 3-SAT
by: Svante Janson, Yannis C. Stamatiou, Malvina Vamvakari v. 17 i. 2 p. 103 - 116
Asymptotics of the list-chromatic index for multigraphs
by: Jeff Kahn v. 17 i. 2 p. 117 - 156
Permutations with roots
by: Miklós Bóna, Andrew Mclennan, Dennis White v. 17 i. 2 p. 157 - 167

1999

Counting Boundary Paths for Oriented Percolation Clusters
by: Paul Balister, Béla Bollobás, Alan Stacey v. 14 i. 1 p. 1 - 28
Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
by: Alexander I. Barvinok v. 14 i. 1 p. 29 - 61
A Sharp Threshold for k-Colorability
by: Dimitris Achlioptas, Ehud Friedgut v. 14 i. 1 p. 63 - 70
Indistinguishable Sceneries
by: Elon Lindenstrauss v. 14 i. 1 p. 71 - 86
Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach
by: Andrei Z. Broder, Alan M. Frieze, Eli Upfal v. 14 i. 1 p. 87 - 109
Techniques for bounding the convergence rate of genetic algorithms
by: Yuri Rabinovich, Avi Wigderson v. 14 i. 2 p. 111 - 138
On the variance of the random sphere of influence graph
by: Pawel Hitczenko, Svante Janson, J. E. Yukich v. 14 i. 2 p. 139 - 152
A few logs suffice to build (almost) all trees (I)
by: Péter L. Erdös, Michael Anthony Steel, László A. Székely, Tandy Warnow v. 14 i. 2 p. 153 - 184
On the multiplicity of parts in a random partition
by: Sylvie Corteel, Boris Pittel, Carla D. Savage, Herbert S. Wilf v. 14 i. 2 p. 185 - 197
Self averaging and the space of interactions in neural networks
by: Michel Talagrand v. 14 i. 3 p. 199 - 213
0-1 laws for maps
by: Edward A. Bender, Kevin J. Compton, L. Bruce Richmond v. 14 i. 3 p. 215 - 237
First order zero-one laws for random graphs on the circle
by: Gregory L. McColm v. 14 i. 3 p. 239 - 266
Asymptotics for dependent sums of random vectors
by: C. Cooper v. 14 i. 3 p. 267 - 292
Simple Markov-chain algorithms for generating bipartite graphs and tournaments
by: Ravi Kannan, Prasad Tetali, Santosh Vempala v. 14 i. 4 p. 293 - 308
On the complexity of branch-and-bound search for random trees
by: Luc Devroye, Carlos Zamora-Cura v. 14 i. 4 p. 309 - 327
Combinatorics of reliability Monte Carlo
by: Michael Lomonosov, Yoseph Shpungin v. 14 i. 4 p. 329 - 343
Learning finite binary sequences from half-space data
by: Shao C. Fang, Santosh S. Venkatesh v. 14 i. 4 p. 345 - 381
Foreword
by: Jennifer T. Chayes, Dana Randall v.