 | 2009 |
|---|
| 104 |       | Oded Goldreich,
Michael Krivelevich,
Ilan Newman,
Eyal Rozenberg:
Hierarchy Theorems for Property Testing.
APPROX-RANDOM 2009: 504-519 |
| 103 | | Amin Coja-Oghlan,
Uriel Feige,
Alan M. Frieze,
Michael Krivelevich,
Dan Vilenchik:
On smoothed k-CNF formulas and the Walksat algorithm.
SODA 2009: 451-460 |
| 102 | | Sonny Ben-Shimon,
Michael Krivelevich:
Vertex percolation on expander graphs.
Eur. J. Comb. 30(2): 339-350 (2009) |
| 101 | | Dan Hefetz,
Michael Krivelevich,
Milos Stojakovic,
Tibor Szabó:
Fast winning strategies in Maker-Breaker games.
J. Comb. Theory, Ser. B 99(1): 39-47 (2009) |
| 100 | | Dan Hefetz,
Michael Krivelevich,
Milos Stojakovic,
Tibor Szabó:
A sharp threshold for the Hamilton cycle Maker-Breaker game.
Random Struct. Algorithms 34(1): 112-122 (2009) |
| 99 | | Michael Krivelevich,
Po-Shen Loh,
Benny Sudakov:
Avoiding small subgraphs in Achlioptas processes.
Random Struct. Algorithms 34(1): 165-195 (2009) |
| 2008 |
|---|
| 98 | | Noga Alon,
Ido Ben-Eliezer,
Michael Krivelevich:
Small Sample Spaces Cannot Fool Low Degree Polynomials.
APPROX-RANDOM 2008: 266-275 |
| 97 | | Ido Ben-Eliezer,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Comparing the strength of query types in property testing: the case of testing k-colorability.
SODA 2008: 1213-1222 |
| 96 | | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Spanning directed trees with many leaves
CoRR abs/0803.0701: (2008) |
| 95 | | Michael Krivelevich,
Benny Sudakov,
Dan Vilenchik:
On the random satisfiable process
CoRR abs/0807.4326: (2008) |
| 94 | | Noga Alon,
Sonny Ben-Shimon,
Michael Krivelevich:
A note on regular Ramsey graphs
CoRR abs/0812.2386: (2008) |
| 93 | | Ohad N. Feldheim,
Michael Krivelevich:
Winning Fast in Sparse Graph Construction Games.
Combinatorics, Probability & Computing 17(6): 781-791 (2008) |
| 92 | | Oded Goldreich,
Michael Krivelevich,
Ilan Newman,
Eyal Rozenberg:
Hierarchy Theorems for Property Testing.
Electronic Colloquium on Computational Complexity (ECCC) 15(097): (2008) |
| 91 | | Itai Benjamini,
Simi Haber,
Michael Krivelevich,
Eyal Lubetzky:
The isoperimetric constant of the random graph process.
Random Struct. Algorithms 32(1): 101-114 (2008) |
| 90 | | Simi Haber,
Michael Krivelevich:
Corrigendum: On fractional K-factors of random graphs.
Random Struct. Algorithms 33(4): 533-535 (2008) |
| 89 | | Dan Hefetz,
Michael Krivelevich,
Milos Stojakovic,
Tibor Szabó:
Planarity, Colorability, and Minor Games.
SIAM J. Discrete Math. 22(1): 194-212 (2008) |
| 88 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing Triangle-Freeness in General Graphs.
SIAM J. Discrete Math. 22(2): 786-819 (2008) |
| 2007 |
|---|
| 87 | | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems.
FSTTCS 2007: 316-327 |
| 86 | | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems.
ICALP 2007: 352-362 |
| 85 | | Amin Coja-Oghlan,
Michael Krivelevich,
Dan Vilenchik:
Why Almost All k -Colorable Graphs Are Easy.
STACS 2007: 121-132 |
| 84 | | Michael Krivelevich,
Zeev Nutov,
Mohammad R. Salavatipour,
Jacques Yuster,
Raphael Yuster:
Approximation algorithms and hardness results for cycle packing problems.
ACM Transactions on Algorithms 3(4): (2007) |
| 83 | | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Better Algorithms and Bounds for Directed Maximum Leaf Problems
CoRR abs/0707.1095: (2007) |
| 82 | | Noga Alon,
Fedor V. Fomin,
Gregory Gutin,
Michael Krivelevich,
Saket Saurabh:
Parameterized Algorithms for Directed Maximum Leaf Problems
CoRR abs/cs/0702049: (2007) |
| 81 | | Alan M. Frieze,
Michael Krivelevich,
Clifford D. Smyth:
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence.
Combinatorics, Probability & Computing 16(5): 733-746 (2007) |
| 80 | | Dan Hefetz,
Michael Krivelevich,
Milos Stojakovic,
Tibor Szabó:
Fast winning strategies in positional games.
Electronic Notes in Discrete Mathematics 29: 213-217 (2007) |
| 79 | | Dan Hefetz,
Michael Krivelevich,
Tibor Szabó:
Bart-Moe games, JumbleG and discrepancy.
Eur. J. Comb. 28(4): 1131-1143 (2007) |
| 78 | | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Addendum to "Scalable secure storage when half the system is faulty" [Inform. Comput 174 (2)(2002) 203-213].
Inf. Comput. 205(7): 1114-1116 (2007) |
| 77 | | Dan Hefetz,
Michael Krivelevich,
Tibor Szabó:
Avoider-Enforcer games.
J. Comb. Theory, Ser. A 114(5): 840-853 (2007) |
| 76 | | Simi Haber,
Michael Krivelevich:
On fractional K-factors of random graphs.
Random Struct. Algorithms 30(4): 441-463 (2007) |
| 2006 |
|---|
| 75 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Testing triangle-freeness in general graphs.
SODA 2006: 279-288 |
| 74 | | Michael Krivelevich,
Dan Vilenchik:
Solving random satisfiable 3CNF formulas in expected polynomial time.
SODA 2006: 454-463 |
| 73 | | Michael Krivelevich,
Benny Sudakov:
Preface.
Eur. J. Comb. 27(8): 1225-1226 (2006) |
| 72 | | Nurit Gazit,
Michael Krivelevich:
On the asymptotic value of the choice number of complete multi-partite graphs.
Journal of Graph Theory 52(2): 123-134 (2006) |
| 71 | | Abraham D. Flaxman,
Alan M. Frieze,
Michael Krivelevich:
On the random 2-stage minimum spanning tree.
Random Struct. Algorithms 28(1): 24-36 (2006) |
| 70 | | Alan M. Frieze,
Michael Krivelevich:
Almost universal graphs.
Random Struct. Algorithms 28(4): 499-510 (2006) |
| 69 | | Michael Krivelevich,
Benny Sudakov,
Prasad Tetali:
On smoothed analysis in dense graphs and formulas.
Random Struct. Algorithms 29(2): 180-193 (2006) |
| 68 | | Michael Krivelevich,
Asaf Nachmias:
Coloring complete bipartite graphs from random lists.
Random Struct. Algorithms 29(4): 436-449 (2006) |
| 2005 |
|---|
| 67 | | Michael Krivelevich,
Zeev Nutov,
Raphael Yuster:
Approximation algorithms for cycle packing problems.
SODA 2005: 556-561 |
| 66 | | Abraham D. Flaxman,
Alan M. Frieze,
Michael Krivelevich:
On the random 2-stage minimum spanning tree.
SODA 2005: 919-926 |
| 65 | | Noga Alon,
Michael Krivelevich,
Joel Spencer,
Tibor Szabó:
Discrepancy Games.
Electr. J. Comb. 12: (2005) |
| 64 | | Alexei E. Ashikhmin,
Gérard D. Cohen,
Michael Krivelevich,
Simon Litsyn:
Bounds on distance distributions in codes of known size.
IEEE Transactions on Information Theory 51(1): 250-258 (2005) |
| 63 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Reed-Muller codes.
IEEE Transactions on Information Theory 51(11): 4032-4039 (2005) |
| 62 | | Alan M. Frieze,
Michael Krivelevich:
On packing Hamilton cycles in ?-regular graphs.
J. Comb. Theory, Ser. B 94(1): 159-172 (2005) |
| 61 | | Joel Friedman,
Andreas Goerdt,
Michael Krivelevich:
Recognizing More Unsatisfiable Random k-SAT Instances Efficiently.
SIAM J. Comput. 35(2): 408-430 (2005) |
| 60 | | Alan M. Frieze,
Michael Krivelevich,
Benny Sudakov:
The Strong Chromatic Index of Random Graphs.
SIAM J. Discrete Math. 19(3): 719-727 (2005) |
| 2004 |
|---|
| 59 | | Michael Krivelevich,
Benny Sudakov,
Tibor Szabó:
Triangle Factors In Sparse Pseudo-Random Graphs.
Combinatorica 24(3): 403-426 (2004) |
| 58 | | Michael Krivelevich,
Asaf Nachmias:
Colouring powers of cycles from random lists.
Eur. J. Comb. 25(7): 961-968 (2004) |
| 57 | | Noga Alon,
Gregory Gutin,
Michael Krivelevich:
Algorithms with large domination ratio.
J. Algorithms 50(1): 118-131 (2004) |
| 56 | | Alan M. Frieze,
Michael Krivelevich,
Ryan Martin:
The emergence of a giant component in random subgraphs of pseudo-random graphs.
Random Struct. Algorithms 24(1): 42-50 (2004) |
| 55 | | Tom Bohman,
Alan M. Frieze,
Michael Krivelevich,
Ryan Martin:
Adding random edges to dense graphs.
Random Struct. Algorithms 24(2): 105-117 (2004) |
| 54 | | Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Tight Bounds for Testing Bipartiteness in General Graphs.
SIAM J. Comput. 33(6): 1441-1483 (2004) |
| 2003 |
|---|
| 53 | | Noga Alon,
Tali Kaufman,
Michael Krivelevich,
Simon Litsyn,
Dana Ron:
Testing Low-Degree Polynomials over GF(2(.
RANDOM-APPROX 2003: 188-199 |
| 52 | | Tali Kaufman,
Michael Krivelevich,
Dana Ron:
Tight Bounds for Testing Bipartiteness in General Graphs.
RANDOM-APPROX 2003: 341-353 |
| 51 |  | Michael Krivelevich,
Benny Sudakov:
The Largest Eigenvalue Of Sparse Random Graphs.
Combinatorics, Probability & Computing 12(1): (2003) |
| 50 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions.
Combinatorics, Probability & Computing 12(5-6): 477-494 (2003) |
| 49 | | Michael Krivelevich,
Benny Sudakov,
Van H. Vu:
Covering codes with improved density.
IEEE Transactions on Information Theory 49(7): 1812-1815 (2003) |
| 48 | | Michael Krivelevich,
Benny Sudakov:
Approximate coloring of uniform hypergraphs.
J. Algorithms 49(1): 2-12 (2003) |
| 47 | | Noga Alon,
Gérard D. Cohen,
Michael Krivelevich,
Simon Litsyn:
Generalized hashing and parent-identifying codes.
J. Comb. Theory, Ser. A 104(1): 207-215 (2003) |
| 46 | | Noga Alon,
Béla Bollobás,
Michael Krivelevich,
Benny Sudakov:
Maximum cuts and judicious partitions in graphs without short cycles.
J. Comb. Theory, Ser. B 88(2): 329-346 (2003) |
| 45 | | Michael Krivelevich,
Benny Sudakov,
Van H. Vu,
Nicholas C. Wormald:
On the probability of independent sets in random graphs.
Random Struct. Algorithms 22(1): 1-14 (2003) |
| 2002 |
|---|
| 44 | | Michael Krivelevich,
Benny Sudakov,
Van H. Vu:
A Sharp Threshold For Network Reliability.
Combinatorics, Probability & Computing 11(5): (2002) |
| 43 | | Ron Aharoni,
Ron Holzman,
Michael Krivelevich,
Roy Meshulam:
Fractional Planks.
Discrete & Computational Geometry 27(4): 585-602 (2002) |
| 42 | | Alan M. Frieze,
Michael Krivelevich:
Hamilton cycles in random subgraphs of pseudo-random graphs.
Discrete Mathematics 256(1-2): 137-150 (2002) |
| 41 | | Michael Krivelevich:
Sparse Graphs Usually Have Exponentially Many Optimal Colorings.
Electr. J. Comb. 9(1): (2002) |
| 40 | | David Burshtein,
Michael Krivelevich,
Simon Litsyn,
Gadi Miller:
Upper bounds on the rate of LDPC Codes.
IEEE Transactions on Information Theory 48(9): 2437-2449 (2002) |
| 39 | | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Scalable Secure Storage When Half the System Is Faulty.
Inf. Comput. 174(2): 203-213 (2002) |
| 38 | | Michael Krivelevich:
Deciding k-colorability in expected polynomial time.
Inf. Process. Lett. 81(1): 1-6 (2002) |
| 37 | | Michael Krivelevich,
Van H. Vu:
Approximating the Independence Number and the Chromatic Number in Expected Polynomial Time.
J. Comb. Optim. 6(2): 143-155 (2002) |
| 36 | | Dimitris Achlioptas,
Jeong Han Kim,
Michael Krivelevich,
Prasad Tetali:
Two-coloring random hypergraphs.
Random Struct. Algorithms 20(2): 249-259 (2002) |
| 35 | | Noga Alon,
Michael Krivelevich:
Testing k-colorability.
SIAM J. Discrete Math. 15(2): 211-227 (2002) |
| 2001 |
|---|
| 34 | | Michael Krivelevich,
Ram Nathaniel,
Benny Sudakov:
Approximating coloring and maximum independent sets in 3-uniform hypergraphs.
SODA 2001: 327-328 |
| 33 | | Andreas Goerdt,
Michael Krivelevich:
Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods.
STACS 2001: 294-304 |
| 32 | | Michael Krivelevich,
Ram Nathaniel,
Benny Sudakov:
Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs.
J. Algorithms 41(1): 99-113 (2001) |
| 31 | | Michael Krivelevich,
Van H. Vu:
Choosability in Random Hypergraphs.
J. Comb. Theory, Ser. B 83(2): 241-257 (2001) |
| 30 | | Michael Krivelevich,
Benny Sudakov,
Van H. Vu,
Nicholas C. Wormald:
Random regular graphs of high degree.
Random Struct. Algorithms 18(4): 346-363 (2001) |
| 2000 |
|---|
| 29 | | Michael Krivelevich,
Van H. Vu:
Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time.
ICALP 2000: 13-24 |
| 28 | | Noga Alon,
Haim Kaplan,
Michael Krivelevich,
Dahlia Malkhi,
Julien P. Stern:
Scalable Secure Storage when Half the System Is Faulty.
ICALP 2000: 576-587 |
| 27 | | Dimitris Achlioptas,
Jeong Han Kim,
Michael Krivelevich,
Prasad Tetali:
Two-coloring Random Hypergraphs.
ICALP Satellite Workshops 2000: 85-96 |
| 26 | | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
Combinatorica 20(4): 451-476 (2000) |
| 25 | | Michael Krivelevich:
The Choice Number Of Dense Random Graphs.
Combinatorics, Probability & Computing 9(1): (2000) |
| 24 | | Ehud Friedgut,
Michael Krivelevich:
Sharp thresholds for certain Ramsey properties of random graphs.
Random Struct. Algorithms 17(1): 1-19 (2000) |
| 23 | | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages are Testable with a Constant Number of Queries.
SIAM J. Comput. 30(6): 1842-1862 (2000) |
| 1999 |
|---|
| 22 | | Noga Alon,
Michael Krivelevich,
Ilan Newman,
Mario Szegedy:
Regular Languages Are Testable with a Constant Number of Queries.
FOCS 1999: 645-655 |
| 21 | | Noga Alon,
Eldar Fischer,
Michael Krivelevich,
Mario Szegedy:
Efficient Testing of Large Graphs.
FOCS 1999: 656-666 |
| 20 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
List Coloring of Random and Pseudo-Random Graphs.
Combinatorica 19(4): 453-472 (1999) |
| 19 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Coloring Graphs with Sparse Neighborhoods.
J. Comb. Theory, Ser. B 77(1): 73-82 (1999) |
| 1998 |
|---|
| 18 | | Michael Krivelevich,
Benny Sudakov:
Approximate Coloring of Uniform Hypergraphs (Extended Abstract).
ESA 1998: 477-489 |
| 17 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Finding a Large Hidden Clique in a Random Graph.
SODA 1998: 594-598 |
| 16 | | Michael Krivelevich:
A lower bound for irredundant Ramsey numbers.
Discrete Mathematics 183(1-3): 185-192 (1998) |
| 15 | | Michael Krivelevich:
An Improved Bound on the Minimal Number of Edges in Color-Critical Graphs.
Electr. J. Comb. 5: (1998) |
| 14 | | Michael Krivelevich,
Benny Sudakov:
Coloring Random Graphs.
Inf. Process. Lett. 67(2): 71-74 (1998) |
| 13 | | Michael Krivelevich,
Benny Sudakov:
The chromatic numbers of random hypergraphs.
Random Struct. Algorithms 12(4): 381-403 (1998) |
| 12 | | Noga Alon,
Michael Krivelevich,
Benny Sudakov:
Finding a large hidden clique in a random graph.
Random Struct. Algorithms 13(3-4): 457-466 (1998) |
| 1997 |
|---|
| 11 | | Noga Alon,
Michael Krivelevich:
The Concentration of the Chromatic Number of Random Graphs.
Combinatorica 17(3): 303-313 (1997) |
| 10 | | Michael Krivelevich:
On the Minimal Number of Edges in Color-Critical Graphs.
Combinatorica 17(3): 401-426 (1997) |
| 9 | | Michael Krivelevich:
Triangle Factors in Random Graphs.
Combinatorics, Probability & Computing 6(3): 337-347 (1997) |
| 8 | | Michael Krivelevich:
Almost perfect matchings in random uniform hypergraphs.
Discrete Mathematics 170(1-3): 259-263 (1997) |
| 7 | | Michael Krivelevich:
Approximate Set Covering in Uniform Hypergraphs.
J. Algorithms 25(1): 118-143 (1997) |
| 1996 |
|---|
| 6 | | Ron Aharoni,
Ron Holzman,
Michael Krivelevich:
On a Theorem of Lovász on Covers in tau-Partite Hypergraphs.
Combinatorica 16(2): 149-174 (1996) |
| 5 | | Michael Krivelevich:
Perfect fractional matchings in random hypergraphs.
Random Struct. Algorithms 9(3): 317-334 (1996) |
| 1995 |
|---|
| 4 | | Michael Krivelevich:
On a conjecture of Tuza about packing and covering of triangles.
Discrete Mathematics 142(1-3): 281-286 (1995) |
| 3 | | Michael Krivelevich:
On the Edge Distribution in Triangle-free Graphs.
J. Comb. Theory, Ser. B 63(2): 245-260 (1995) |
| 2 | | Michael Krivelevich:
Bounding Ramsey Numbers through Large Deviation Inequalities.
Random Struct. Algorithms 7(2): 145-156 (1995) |
| 1994 |
|---|
| 1 | | Michael Krivelevich:
Ks-Free Graphs Without Large Kr-Free Subgraphs.
Combinatorics, Probability & Computing 3: 349-354 (1994) |
