Bernard Chazelle - Publications

Affiliations: 
Computer Science Princeton University, Princeton, NJ 
Area:
Natural Algorithms, Dynamical Systems, Dynamic Networks, Computational Geometry, Discrepancy Theory.

123 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2015 Chazelle B. Diffusive influence systems Siam Journal On Computing. 44: 1403-1442. DOI: 10.1137/120882640  1
2015 Chazelle B. Algorithmic renormalization for network dynamics Ieee Transactions On Network Science and Engineering. 2: 1-16. DOI: 10.1109/Tnse.2015.2419133  1
2015 Chazelle B, Mulzer W. Data Structures on Event Graphs Algorithmica. 71: 1007-1020. DOI: 10.1007/S00453-013-9838-4  1
2015 Chazelle B. Communication, dynamics, and renormalization Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9079: 1-32. DOI: 10.1007/978-3-319-18173-8_1  1
2015 Chazelle B. Communication and dynamic networks Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 9214: 641.  1
2014 Chazelle B. The convergence of bird flocking Journal of the Acm. 61. DOI: 10.1145/2629613  1
2014 Chazelle B. An Algorithmic Approach to Collective Behavior Journal of Statistical Physics. 158: 514-548. DOI: 10.1007/S10955-014-1140-6  1
2013 Bhattacharyya A, Braverman M, Chazelle B, Nguyen HL. On the convergence of the Hegselmann-Krause system Itcs 2013 - Proceedings of the 2013 Acm Conference On Innovations in Theoretical Computer Science. 61-65. DOI: 10.1145/2422436.2422446  1
2012 Chazelle B. Natural algorithms and influence systems Communications of the Acm. 55: 101-110. DOI: 10.1145/2380656.2380679  1
2012 Chazelle B. The dynamics of influence systems Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 311-320. DOI: 10.1109/FOCS.2012.70  1
2011 Chazelle B, Seshadhri C. Online geometric reconstruction Journal of the Acm. 58. DOI: 10.1145/1989727.1989728  1
2011 Chazelle B. The total s-energy of a multiagent system Siam Journal On Control and Optimization. 49: 1680-1706. DOI: 10.1137/100791671  1
2011 Ailon N, Chazelle B, Clarkson KL, Liu D, Mulzer W, Seshadhri C. Self-improving algorithms Siam Journal On Computing. 40: 350-375. DOI: 10.1137/090766437  1
2011 Chazelle B, Mulzer W. Computing Hereditary Convex Structures Discrete and Computational Geometry. 45: 796-823. DOI: 10.1007/s00454-011-9346-8  1
2010 Chazelle B. A geometric approach to collective motion Proceedings of the Annual Symposium On Computational Geometry. 117-126. DOI: 10.1145/1810959.1810983  1
2010 Chazelle B. The geometry of flocking Proceedings of the Annual Symposium On Computational Geometry. 19-28. DOI: 10.1145/1810959.1810963  1
2010 Ailon N, Chazelle B. Faster dimension reduction Communications of the Acm. 53: 97-104. DOI: 10.1145/1646353.1646379  1
2009 Ailon N, Chazelle B. The fast johnson-lindenstrauss transform and approximate nearest neighbors Siam Journal On Computing. 39: 302-322. DOI: 10.1137/060673096  1
2009 Chazelle B, Mulzer W. Markov incremental constructions Discrete and Computational Geometry. 42: 399-420. DOI: 10.1007/s00454-009-9170-6  1
2009 Banks E, Nabieva E, Chazelle B, Peterson R, Singh M. Analyzing and interrogating biological networks (abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5462: 14-15. DOI: 10.1007/978-3-642-00727-9_2  1
2008 Banks E, Nabieva E, Chazelle B, Singh M. Organization of physical interactomes as uncovered by network schemas. Plos Computational Biology. 4: e1000203. PMID 18949022 DOI: 10.1371/Journal.Pcbi.1000203  1
2008 Chazelle B. Finding a good neighbor, near and fast Communications of the Acm. 51: 115. DOI: 10.1145/1327452.1327493  1
2008 Chazelle B, Liu D, Magen A. Approximate range searching in higher dimension Computational Geometry: Theory and Applications. 39: 24-29. DOI: 10.1016/J.Comgeo.2007.05.008  1
2008 Ailon N, Chazelle B, Comandur S, Liu D. Property-preserving data reconstruction Algorithmica (New York). 51: 160-182. DOI: 10.1007/S00453-007-9075-9  1
2007 Chazelle B. Computer science. Coding and computing join forces. Science (New York, N.Y.). 317: 1691-2. PMID 17885118 DOI: 10.1126/Science.1148064  1
2007 Chazelle B. Computing: the security of knowing nothing. Nature. 446: 992-3. PMID 17460653 DOI: 10.1038/446992A  1
2007 Ailon N, Chazelle B, Comandur S, Liu D. Estimating the distance to a monotone function Random Structures and Algorithms. 31: 371-383. DOI: 10.1002/Rsa.V31:3  1
2007 Chazelle B. Ushering in a new era of algorithm design Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4596: 1.  1
2006 Chazelle B. Mathematics: proof at a roll of the dice. Nature. 444: 1018-9. PMID 17183306 DOI: 10.1038/4441018A  1
2006 Ailon N, Chazelle B. Information theory in property testing and monotonicity testing in higher dimension Information and Computation. 204: 1704-1717. DOI: 10.1016/J.Ic.2006.06.001  1
2006 Ailon N, Chazelle B. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform Proceedings of the Annual Acm Symposium On Theory of Computing. 2006: 557-563.  1
2005 Nabieva E, Jim K, Agarwal A, Chazelle B, Singh M. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics (Oxford, England). 21: i302-10. PMID 15961472 DOI: 10.1093/Bioinformatics/Bti1054  1
2005 Kingsford CL, Chazelle B, Singh M. Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics (Oxford, England). 21: 1028-36. PMID 15546935 DOI: 10.1093/Bioinformatics/Bti144  1
2005 Arora S, Chazelle B. Is the thrill gone? Communications of the Acm. 48: 31-33. DOI: 10.1145/1076211.1076233  1
2005 Ailon N, Chazelle B. Lower bounds for linear degeneracy testing Journal of the Acm. 52: 157-171. DOI: 10.1145/1059513.1059515  1
2005 Chazelle B, Liu D, Magen A. Sublinear geometric algorithms Siam Journal On Computing. 35: 627-646. DOI: 10.1137/S009753970444572X  1
2005 Chazelle B, Rubinfeld R, Trevisan L. Approximating the minimum spanning tree weight in sublinear time Siam Journal On Computing. 34: 1370-1379. DOI: 10.1137/S0097539702403244  1
2005 Azar Y, Buchsbaum A, Chazelle B, Cole R, Fleischer L, Golin M, Goodrich M, Grossi R, Guha S, Halldorsson MM, Indyk P, Italiano GF, Kaplan H, Myrvold W, Pruhs K, et al. Proceeding of the Annual ACM-SIAM Symposium on Discrete Algorithms: Preface Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. xiii.  1
2004 Chazelle B, Kingsford C, Singh M. A semidefinite programming approach to side chain positioning with new rounding strategies Informs Journal On Computing. 16: 380-392. DOI: 10.1287/Ijoc.1040.0096  1
2004 Chazelle B, Liu D. Lower bounds for intersection searching and fractional cascading in higher dimension Journal of Computer and System Sciences. 68: 269-284. DOI: 10.1016/J.Jcss.2003.07.003  1
2004 Chazelle B. The Power of Nonmonotonicity in Geometric Searching Discrete and Computational Geometry. 31: 3-16. DOI: 10.1007/S00454-003-2946-1  1
2004 Chazelle B, Kilian J, Rubinfeld R, Tal A. The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 15: 30-39.  1
2003 Kazhdan M, Chazelle B, Dobkin D, Funkhouser T, Rusinkiewicz S. A reflective symmetry descriptor for 3D models Algorithmica (New York). 38: 201-225. DOI: 10.1007/S00453-003-1050-5  1
2003 Chazelle B. The PCP theorem [after Arora, Lund, Motwani, Safra, Sudan, Szegedy] Asterisque. 19-36.  1
2003 Chazelle B, Kingsford C, Singh M. The Side-Chain Positioning Problem: A Semidefinite Programming Formulation with New Rounding Schemes Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop. 86-94.  1
2003 Chazelle B, Liu D, Magen A. Sublinear geometrie algorithms Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 531-540.  1
2003 Chazelle B. Sublinear Computing Lecture Notes in Computer Science. 1.  1
2002 Osada R, Funkhouser T, Chazelle B, Dobkin D. Shape distributions Acm Transactions On Graphics. 21: 807-832. DOI: 10.1145/571647.571648  1
2002 Chazelle B, Devillers O, Hurtado F, Mora M, Sacristán V, Teillaud M. Splitting a delaunay triangulation in linear time Algorithmica (New York). 34: 39-46. DOI: 10.1007/S00453-002-0939-8  1
2001 Osada R, Funkhouser T, Chazelle B, Dobkin D. Matching 3D models with shape distributions Proceedings - International Conference On Shape Modeling and Applications, Smi 2001. 154-166. DOI: 10.1109/SMA.2001.923386  1
2001 Chazelle B, Lvov A. A trace bound for the hereditary discrepancy Discrete and Computational Geometry. 26: 221-231. DOI: 10.1007/S00454-001-0030-2  1
2001 Chazelle B, Lvov A. The discrepancy of boxes in higher dimension Discrete and Computational Geometry. 25: 519-524. DOI: 10.1007/S00454-001-0014-2  1
2000 Chazelle B. A minimum spanning tree algorithm with inverse-ackermann type complexity Journal of the Acm. 47: 1028-1047. DOI: 10.1145/355541.355562  1
2000 Chazelle B. The soft heap: An approximate priority queue with optimal error rate Journal of the Acm. 47: 1012-1027. DOI: 10.1145/355541.355554  1
2000 Ar S, Chazelle B, Tal A. Self-customized BSP trees for collision detection Computational Geometry: Theory and Applications. 15: 91-102. DOI: 10.1016/S0925-7721(99)00049-8  1
2000 Chazelle B. Irregularities of distribution, derandomization, and complexity theory Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1974: 46-54.  1
2000 Chazelle B, Lvov A. Trace bound for the hereditary discrepancy Proceedings of the Annual Symposium On Computational Geometry. 64-69.  1
1999 Brönnimann H, Chazelle B, Matoušek J. Product range spaces, sensitive sampling, and derandomization Siam Journal On Computing. 28: 1552-1575. DOI: 10.1137/S0097539796260321  1
1999 Chazelle B. Geometric searching over the rationals Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1643: 354-365. DOI: 10.1007/3-540-48481-7_31  1
1999 Chakrabarti A, Chazelle B, Gum B, Lvov A. Lower bound on the complexity of approximate nearest-neighbor searching on the hamming cube Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 305-311.  1
1998 Chazelle B. A spectral approach to lower bounds with applications to geometric searching Siam Journal On Computing. 27: 545-556. DOI: 10.1137/S0097539794275665  1
1998 Brönnimann H, Chazelle B. Optimal slope selection via cuttings Computational Geometry: Theory and Applications. 10: 23-29. DOI: 10.1016/S0925-7721(97)00025-4  1
1998 Chazelle B. The discrepancy method Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1533: 1-3.  1
1998 Chazelle B. Car-pooling as a data structuring device: The soft heap Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1461: 35-42.  1
1997 Chazelle B, Dobkin DP, Shouraboura N, Tal A. Strategies for polyhedral surface decomposition: An experimental study Computational Geometry: Theory and Applications. 7: 327-342. DOI: 10.1016/S0925-7721(96)00024-7  1
1997 Chazelle B. Lower bounds for off-line range searching Discrete and Computational Geometry. 17: 53-65. DOI: 10.1007/Bf02770864  1
1997 Chazelle B, Palios L. Decomposing the Boundary of a Nonconvex Polyhedron Algorithmica (New York). 17: 245-265. DOI: 10.1007/Bf02523191  1
1997 Chazelle B. Discrepancy theory and computational geometry Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1272: 1-2.  1
1997 Chazelle B. Faster deterministic algorithm for minimum spanning trees Annual Symposium On Foundations of Computer Science - Proceedings. 22-31.  1
1996 Barequet G, Chazelle B, Guibas LJ, Mitchell JSB, Tal A. BOXTREE: A hierarchical representation for surfaces in 3D Computer Graphics Forum. 15: C387-C396. DOI: 10.1111/1467-8659.1530387  1
1996 Chazelle B, Rosenberg B. Simplex range reporting on a pointer machine Computational Geometry: Theory and Applications. 5: 237-247. DOI: 10.1016/0925-7721(95)00002-X  1
1996 Chazelle B, Edelsbrunner H, Guibas LJ, Sharir M, Stolfi J. Lines in Space: Combinatorics and Algorithms Algorithmica (New York). 15: 428-447. DOI: 10.1007/Bf01955043  1
1996 Chazelle B, Matoušek J. On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension Journal of Algorithms. 21: 579-597. DOI: 10.1006/Jagm.1996.0060  1
1996 Chazelle B. The computational geometry impact task force report: An executive summary Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1148: 59-65.  1
1995 Chazelle B, Matoušek J. Derandomizing an output-sensitive convex hull algorithm in three dimensions Computational Geometry: Theory and Applications. 5: 27-32. DOI: 10.1016/0925-7721(94)00018-Q  1
1995 Chazelle B, Matoušek J, Sharir M. An elementary approach to lower bounds in geometric discrepancy Discrete & Computational Geometry. 13: 363-381. DOI: 10.1007/Bf02574050  1
1995 Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved bounds on weak ε-nets for convex sets Discrete & Computational Geometry. 13: 1-15. DOI: 10.1007/Bf02574025  1
1995 Chazelle B, Shourboura N. Bounds on the size of tetrahedralizations Discrete & Computational Geometry. 14: 429-444. DOI: 10.1007/Bf02570716  1
1994 Chazelle B, Edelsbrunner H, Guibas LJ, Hershberger JE, Seidel R, Sharir M. Selecting heavily covered points Siam Journal On Computing. 23: 1138-1151. DOI: 10.1137/S0097539790179919  1
1994 Chazelle B, Friedman J. Point location among hyperplanes and unidirectional ray-shooting Computational Geometry: Theory and Applications. 4: 53-62. DOI: 10.1016/0925-7721(94)90009-4  1
1994 Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Hershberger J, Sharir M, Snoeyink J. Ray shooting in polygons using geodesic triangulations Algorithmica. 12: 54-68. DOI: 10.1007/Bf01377183  1
1994 Chazelle B, Edelsbrunner H, Guibas LJ, Sharir M. Algorithms for bichromatic line-segment problems and polyhedral terrains Algorithmica. 11: 116-132. DOI: 10.1007/Bf01182771  1
1994 Chazelle B. Computational geometry: A retrospective Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 75-94.  1
1993 Chazelle B. An optimal convex hull algorithm in any fixed dimension Discrete & Computational Geometry. 10: 377-409. DOI: 10.1007/Bf02573985  1
1993 Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line pair, and parametric searching Discrete & Computational Geometry. 10: 183-196. DOI: 10.1007/Bf02573973  1
1993 Brönnimann H, Chazelle B, Pach J. How hard is half-space range searching? Discrete & Computational Geometry. 10: 143-155. DOI: 10.1007/Bf02573971  1
1993 Chazelle B. Cutting hyperplanes for divide-and-conquer Discrete & Computational Geometry. 9: 145-158. DOI: 10.1007/Bf02189314  1
1992 Chazelle B, Edelsbrunner H, Guibas LJ, Pollack R, Seidel R, Sharir M, Snoeyink J. Counting and cutting cycles of lines and rods in space Computational Geometry: Theory and Applications. 1: 305-323. DOI: 10.1016/0925-7721(92)90009-H  1
1992 Chazelle B, Sharir M, Welzl E. Quasi-optimal upper bounds for simplex range searching and new zone theorems Algorithmica. 8: 407-429. DOI: 10.1007/Bf01758854  1
1991 Chazelle B, Edelsbrunner H, Guibas LJ, Sharir M. A singly exponential stratification scheme for real semi-algebraic varieties and its applications Theoretical Computer Science. 84: 77-105. DOI: 10.1016/0304-3975(91)90261-Y  1
1991 Chazelle B. Triangulating a simple polygon in linear time Discrete & Computational Geometry. 6: 485-524. DOI: 10.1007/Bf02574703  1
1991 Aronov B, Chazelle B, Edelsbrunner H, Guibas LJ, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space Discrete & Computational Geometry. 6: 435-442. DOI: 10.1007/Bf02574700  1
1990 Chazelle B, Palios L. Triangulating a nonconvex polytope Discrete & Computational Geometry. 5: 505-526. DOI: 10.1007/BF02187807  1
1990 Chazelle B, Friedman J. A deterministic view of random sampling and its use in geometry Combinatorica. 10: 229-249. DOI: 10.1007/Bf02122778  1
1989 Chazelle B, Guibas LJ. Visibility and intersection problems in plane geometry Discrete & Computational Geometry. 4: 551-581. DOI: 10.1007/Bf02187747  1
1989 Chazelle B, Welzl E. Quasi-optimal range searching in spaces of finite VC-dimension Discrete & Computational Geometry. 4: 467-489. DOI: 10.1007/BF02187743  1
1989 Chazelle B, Edelsbrunner H, Guibas LJ. The complexity of cutting complexes Discrete & Computational Geometry. 4: 139-181. DOI: 10.1007/Bf02187720  1
1988 Aggarwal A, Chazelle B, Guibas L, Ó'Dúnlaing C, Yap C. Parallel computational geometry Algorithmica. 3: 293-327. DOI: 10.1007/Bf01762120  1
1988 Chazelle B. An algorithm for segment-dragging and its implementation Algorithmica. 3: 205-221. DOI: 10.1007/Bf01762115  1
1987 Chazelle B, Dobkin DP. Intersection of convex objects in two and three dimensions Journal of the Acm (Jacm). 34: 1-27. DOI: 10.1145/7531.24036  1
1987 Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search Discrete & Computational Geometry. 2: 113-126. DOI: 10.1007/Bf02187875  1
1987 Chazelle B. Computing on a free tree via complexity-preserving mappings Algorithmica. 2: 337-361. DOI: 10.1007/Bf01840366  1
1987 Chazelle B. Editor's foreword Algorithmica. 2: 135-136. DOI: 10.1007/BF01840355  1
1987 Chazelle B. Some techniques for geometric searching with implicit set representations Acta Informatica. 24: 565-582. DOI: 10.1007/Bf00263295  1
1986 Chazelle B, Drysdale RL, Lee DT. COMPUTING THE LARGEST EMPTY RECTANGLE Siam Journal On Computing. 15: 300-315. DOI: 10.1137/0215022  1
1986 Chazelle B, Cole R, Preparata FP, Yap C. New upper bounds for neighbor searching Information and Control. 68: 105-124. DOI: 10.1016/S0019-9958(86)80030-4  1
1986 Chazelle B. Reporting and counting segment intersections Journal of Computer and System Sciences. 32: 156-182. DOI: 10.1016/0022-0000(86)90025-5  1
1986 Chazelle BM, Lee DT. On a circle placement problem Computing. 36: 1-16. DOI: 10.1007/BF02238188  1
1986 Chazelle B, Preparata FP. Halfspace range search: An algorithmic application of k-sets Discrete & Computational Geometry. 1: 83-93. DOI: 10.1007/Bf02187685  1
1986 Chazelle B, Guibas LJ. Fractional cascading: II. Applications Algorithmica. 1: 163-191. DOI: 10.1007/Bf01840441  1
1986 Chazelle B, Guibas LJ. Fractional cascading: I. A data structuring technique Algorithmica. 1: 133-162. DOI: 10.1007/Bf01840440  1
1985 Chazelle B. On the Convex Layers of a Planar Set Ieee Transactions On Information Theory. 31: 509-517. DOI: 10.1109/Tit.1985.1057060  1
1985 Chazelle B, Edelsbrunner H. OPTIMAL SOLUTIONS FOR A CLASS OF POINT RETRIEVAL PROBLEMS Journal of Symbolic Computation. 1: 47-56. DOI: 10.1016/S0747-7171(85)80028-6  1
1985 Chazelle B. How to search in history Information and Control. 64: 77-99. DOI: 10.1016/S0019-9958(85)80045-0  1
1985 Chazelle B, Guibas LJ, Lee DT. The power of geometric duality Bit. 25: 76-90. DOI: 10.1007/Bf01934990  1
1984 Chazelle B, Incerpi J. Triangulation and shapecomplexity Acm Transactions On Graphics. 3: 135-152. DOI: 10.1145/357337.357340  1
1984 Chazelle B. Computational Geometry on a Systolic Chip Ieee Transactions On Computers. 774-785. DOI: 10.1109/TC.1984.1676494  1
1983 Chazelle B. The Bottom-Left Bin-Packing Heuristic: An Efficient Implementation Ieee Transactions On Computers. 697-707. DOI: 10.1109/TC.1983.1676307  1
1983 Chazelle B, Monier L. Unbounded hardware is equivalent to deterministic turing machines Theoretical Computer Science. 24: 123-130. DOI: 10.1016/0304-3975(83)90044-0  1
1983 Chazelle B. An improved algorithm for the fixed-radius neighbor problem Information Processing Letters. 16: 193-198. DOI: 10.1016/0020-0190(83)90123-0  1
1983 Chazelle B. A decision procedure for optimal polyhedron partitioning Information Processing Letters. 16: 75-78. DOI: 10.1016/0020-0190(83)90028-5  1
1983 Chazelle B, Incerpi J. TRIANGULATING A POLYGON BY DIVIDE-AND-CONQUER Proceedings - Annual Allerton Conference On Communication, Control, and Computing. 447-456.  1
1980 Chazelle B, Dobkin DP. Detection is easier than computation Proceedings of the Annual Acm Symposium On Theory of Computing. 1980: 146-153. DOI: 10.1145/800141.804662  1
Show low-probability matches.