ACM Fellow 1999, "For seminal contributions to the analysis of algorithms, in particular the worst-case analysis of heuristics, the theory of scheduling, and computational geometry.".
2022
Guessing about Guessing: Practical Strategies for Card Guessing with Feedback.
Am. Math. Mon., 2022
Card guessing with partial feedback.
Comb. Probab. Comput., 2022
2021
Permanental generating functions and sequential importance sampling.
Adv. Appl. Math., 2021
2020
Efficient Packings of Unit Squares in a Large Square.
Discret. Comput. Geom., 2020
2019
Three-dimensional Floorplan Representations by Using Corner Links and Partial Order.
ACM Trans. Design Autom. Electr. Syst., 2019
2018
Maximally Nontransitive Dice.
Am. Math. Mon., 2018
Sum sequences modulo <i>n</i>.
J. Comb. Theory, Ser. A, 2018
Tree Structures and Algorithms for Physical Design.
Proceedings of the 2018 International Symposium on Physical Design, 2018
2017
The drop polynomial of a weighted digraph.
J. Comb. Theory, Ser. B, 2017
Parking distributions on trees.
Eur. J. Comb., 2017
2016
Inserting Plus Signs and Adding.
Am. Math. Mon., 2016
The Mathematics of the Flip and Horseshoe Shuffles.
Am. Math. Mon., 2016
Anarchy Is Free in Network Creation.
ACM Trans. Algorithms, 2016
Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions.
OR Spectr., 2016
3D floorplan representations: Corner links and partial order.
Proceedings of the 2016 IEEE International 3D Systems Integration Conference, 2016
2015
Egyptian Fractions with Each Denominator Having Three Distinct Prime Divisors.
Integers, 2015
Partition and sum is fast.
CoRR, 2015
Edge flipping in the complete graph.
Adv. Appl. Math., 2015
2014
Single-processor scheduling with time restrictions.
J. Sched., 2014
De Bruijn Sequences with Varying Combs.
Integers, 2014
Unseparated pairs and fixed points in random permutations.
Adv. Appl. Math., 2014
2013
Subdivision Using Angle Bisectors Is Dense in the Space of Triangles.
Am. Math. Mon., 2013
Inversion-descent polynomials for restricted permutations.
J. Comb. Theory, Ser. A, 2013
Constructing Points through Folding and Intersection.
Int. J. Comput. Geom. Appl., 2013
Ramsey Theory in the Work of Paul Erdős.
Proceedings of the Mathematics of Paul Erdős II, 2013
2012
A note on marking lines in [k] n - In honor of Rick Wilson's 65th birthday.
Des. Codes Cryptogr., 2012
Character design and stamp algorithms for Character Projection Electron-Beam Lithography.
Proceedings of the 17th Asia and South Pacific Design Automation Conference, 2012
2011
Bus Matrix Synthesis Based on Steiner Graphs for Power Efficient System-on-Chip Communications.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2011
Hypercube orientations with only two in-degrees.
J. Comb. Theory, Ser. A, 2011
2010
Some Ramsey-type results for the n-cube.
J. Comb. Theory, Ser. A, 2010
Finding Patterns Avoiding Many Monochromatic Constellations.
Exp. Math., 2010
Descent polynomials for permutations with bounded drop size.
Eur. J. Comb., 2010
How to play the Majority game with a liar.
Discret. Math., 2010
Irreducible Apollonian Configurations and Packings.
Discret. Comput. Geom., 2010
Tiling Polygons with Lattice Triangles.
Discret. Comput. Geom., 2010
Physical synthesis of bus matrix for high bandwidth low power on-chip communications.
Proceedings of the 2010 International Symposium on Physical Design, 2010
2009
Approximately optimal trees for group key management with batch updates.
Theor. Comput. Sci., 2009
Packing equal squares into a large square.
J. Comb. Theory, Ser. A, 2009
Minimum perimeter rectangles that enclose congruent non-overlapping circles.
Discret. Math., 2009
Bubblesort and Juggling Sequences.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009
2008
Primitive Juggling Sequences.
Am. Math. Mon., 2008
Erratum: Quasi-random graphs with given degree sequences.
Random Struct. Algorithms, 2008
Quasi-random graphs with given degree sequences.
Random Struct. Algorithms, 2008
Enumerating split-pair arrangements.
J. Comb. Theory, Ser. A, 2008
Analysis of greedy approximations with nonsubmodular potential functions.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
3-D floorplanning using labeled tree and dual sequences.
Proceedings of the 2008 International Symposium on Physical Design, 2008
2007
Optimal Tree Structures for Group Key Management with Batch Updates.
SIAM J. Discret. Math., 2007
Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Algorithmica, 2007
Approximately Optimal Trees for Group Key Management with Batch Updates.
Proceedings of the Theory and Applications of Models of Computation, 2007
How to Play the Majority Game with Liars.
Proceedings of the Algorithmic Aspects in Information and Management, 2007
2006
On the construction of zero-deficiency parallel prefix circuits with minimum depth.
ACM Trans. Design Autom. Electr. Syst., 2006
Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines.
Theory Comput. Syst., 2006
Maximizing data locality in distributed systems.
J. Comput. Syst. Sci., 2006
Apollonian Circle Packings: Geometry and Group Theory III. Higher Dimensions.
Discret. Comput. Geom., 2006
Apollonian Circle Packings: Geometry and Group Theory II. Super-Apollonian Group and Integral Packings.
Discret. Comput. Geom., 2006
Timing model reduction for hierarchical timing analysis.
Proceedings of the 2006 International Conference on Computer-Aided Design, 2006
Communication latency aware low power NoC synthesis.
Proceedings of the 43rd Design Automation Conference, 2006
2005
Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group.
Discret. Comput. Geom., 2005
Constructing zero-deficiency parallel prefix adder of minimum depth.
Proceedings of the 2005 Conference on Asia South Pacific Design Automation, 2005
2004
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004
Parallelism versus memory allocation in pipelined router forwarding engines.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004
2003
Floorplan representations: Complexity and connections.
ACM Trans. Design Autom. Electr. Syst., 2003
Guessing Secrets with Inner Product Questions.
Internet Math., 2003
Electron. Colloquium Comput. Complex., 2003
A hierarchical three-way interconnect architecture for hexagonal processors.
Proceedings of the 5th International Workshop on System-Level Interconnect Prediction (SLIP 2003), 2003
2002
Ramsey Properties of Families of Graphs.
J. Comb. Theory, Ser. B, 2002
New bounds on a hypercube coloring problem.
Inf. Process. Lett., 2002
Sparse Quasi-Random Graphs.
Comb., 2002
Balancing the Interconnect Topology for Arrays of Processors between Cost and Power.
Proceedings of the 20th International Conference on Computer Design (ICCD 2002), 2002
2001
Dynamic location problems with limited look-ahead .
Theor. Comput. Sci., 2001
Distance Realization Problems with Applications to Internet Tomography.
J. Comput. Syst. Sci., 2001
On Bipartite Graphs with Linear Ramsey Numbers.
Comb., 2001
Combinatorics for the East Model.
Adv. Appl. Math., 2001
New Bounds on a Hypercube Coloring Problem and Linear Codes.
Proceedings of the 2001 International Symposium on Information Technology (ITCC 2001), 2001
Revisiting floorplan representations.
Proceedings of the 2001 International Symposium on Physical Design, 2001
2000
On graphs with linear Ramsey numbers.
J. Graph Theory, 2000
Improving Dense Packings of Equal Disks in a Square.
Electron. J. Comb., 2000
1998
Dense packings of congruent circles in a circle.
Discret. Math., 1998
Forced Convex n -Gons in the Plane.
Discret. Comput. Geom., 1998
Combinatorial Problems Arising in Massive Data Sets (Abstract).
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998
1997
Stratified random walks on the n-cube.
Random Struct. Algorithms, 1997
The Steiner ratio for the dual normed plane.
Discret. Math., 1997
Curved Hexagonal Packings of Equal Disks in a Circle.
Discret. Comput. Geom., 1997
Random walks on generating sets for finite groups.
Electron. J. Comb., 1997
1996
On sampling with Markov chains.
Random Struct. Algorithms, 1996
Repeated Patterns of Dense Packings of Equal Disks in a Square.
Electron. J. Comb., 1996
1995
On the Cover Polynomial of a Digraph.
J. Comb. Theory, Ser. B, 1995
A tight lower bound for the Steiner ratio in Minkowski planes.
Discret. Math., 1995
Dense Packings of Equal Disks in an Equilateral Triangle: from 22 to 34 and Beyond.
Electron. J. Comb., 1995
Dense Packings of 3k(k+1)+1 Equal Disks in a Circle for k=1, 2, 3, 4 and 5.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995
1994
Routing Permutations on Graphs Via Matchings.
SIAM J. Discret. Math., 1994
A Note on the Binomial Drop Polynomial of a Poset.
J. Comb. Theory, Ser. A, 1994
Recent trends in Euclidean Ramsey theory.
Discret. Math., 1994
Quasi-Random Combinatorial Structures (Abstract).
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994
Concrete mathematics - a foundation for computer science (2. ed.).
Addison-Wesley, ISBN: 978-0-201-55802-9, 1994
Concrete Mathematics: A Foundation for Computer Science, 2nd Ed.
Addison-Wesley, ISBN: 0-201-55802-5, 1994
1993
Lexicographic Ramsey Theory.
J. Comb. Theory, Ser. A, 1993
On hypergraphs having evenly distributed subhypergraphs.
Discret. Math., 1993
Minimum Steiner Trees in Normed Planes.
Discret. Comput. Geom., 1993
1992
Quasi-Random Subsets of Integer<sub>n</sub>.
J. Comb. Theory, Ser. A, 1992
Binomial coefficient codes over GF(2).
Discret. Math., 1992
Universal cycles for combinatorial structures.
Discret. Math., 1992
Bounds for arrays of dots with distinct slopes or lengths.
Comb., 1992
1991
Quasi-random tournaments.
J. Graph Theory, 1991
1990
Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions.
Random Struct. Algorithms, 1990
Quasi-Random Hypergraphs.
Random Struct. Algorithms, 1990
Iterated combinatorial density theorems.
J. Comb. Theory, Ser. A, 1990
Penny-Packing and Two-Dimensional Codes.
Discret. Comput. Geom., 1990
1989
Maximal antiramsey graphs and the strong chromatic number.
J. Graph Theory, 1989
A dynamic location problem for graphs.
Comb., 1989
On the Improbability of Reaching Byzantine Agreements (Preliminary Version)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Concrete mathematics - a foundation for computer science.
Addison-Wesley, ISBN: 978-0-201-14236-5, 1989
1988
On the Fractional Covering Number of Hypergraphs.
SIAM J. Discret. Math., 1988
Pursuit - Evasion games on graphs.
J. Graph Theory, 1988
Quantitative theorems for regular systems of equations.
J. Comb. Theory, Ser. A, 1988
On induced subgraphs of the cube.
J. Comb. Theory, Ser. A, 1988
1987
Induced restricted Ramsey theorems for spaces.
J. Comb. Theory, Ser. A, 1987
On subsets of abelian groups with no 3-term arithmetic progression.
J. Comb. Theory, Ser. A, 1987
The Radon transform on Abelian Groups.
J. Comb. Theory, Ser. A, 1987
1986
Large minimal sets which force long arithmetic progressions.
J. Comb. Theory, Ser. A, 1986
Some intersection theorems for ordered sets and graphs.
J. Comb. Theory, Ser. A, 1986
1985
On the covering radius of codes.
IEEE Trans. Inf. Theory, 1985
Classes of interval graphs under expanding length restrictions.
J. Graph Theory, 1985
Quantitative Forms of a Theorem of Hilbert.
J. Comb. Theory, Ser. A, 1985
On the addressing problem for directed graphs.
Graphs Comb., 1985
Intersection Theorems for Vector Spaces.
Eur. J. Comb., 1985
On the History of the Minimum Spanning Tree Problem.
IEEE Ann. Hist. Comput., 1985
1983
Euclidean Ramsey theorems on the <i>n</i>-sphere.
J. Graph Theory, 1983
A Canonical Partition Theorem for Equivalence Relations on Z<sup>t</sup>.
J. Comb. Theory, Ser. A, 1983
Finding the Convex Hull of a Simple Polygon.
J. Algorithms, 1983
Edge-colored complete graphs with precisely colored subgraphs.
Comb., 1983
1982
Minimal Decompositions of Hypergraphs into Mutually Isomorphic Subhypergraphs.
J. Comb. Theory, Ser. A, 1982
1981
Homogeneous Collinear Sets in Partitions of Z<sup>n</sup>.
J. Comb. Theory, Ser. A, 1981
J. Comb. Theory, Ser. B, 1981
Minimal decompositions of graphs into mutually isomorphic subgraphs.
Comb., 1981
1980
Lower bounds for constant weight codes.
IEEE Trans. Inf. Theory, 1980
Some Monotonicity Properties of Partial Orders.
SIAM J. Algebraic Discret. Methods, 1980
On Additive Bases and Harmonious Graphs.
SIAM J. Algebraic Discret. Methods, 1980
On the Structure of t-Designs.
SIAM J. Algebraic Discret. Methods, 1980
On Unimodality for Linear Extensions of Partial Orders.
SIAM J. Algebraic Discret. Methods, 1980
A Note on the Intersection Properties of Subsets of Integers.
J. Comb. Theory, Ser. A, 1980
On Partitions of E<sup>n</sup>.
J. Comb. Theory, Ser. A, 1980
Information Bounds Are Weak in the Shortest Distance Problem.
J. ACM, 1980
On a Diophantine Equation Arising in Graph Theory.
Eur. J. Comb., 1980
1979
Combinatorial designs related to the strong perfect graph conjecture.
Discret. Math., 1979
1978
On subgraph number independence in trees.
J. Comb. Theory, Ser. B, 1978
The Number of Baxter Permutations.
J. Comb. Theory, Ser. A, 1978
On graphs which contain all small trees.
J. Comb. Theory, Ser. B, 1978
Performance Guarantees for Scheduling Algorithms.
Oper. Res., 1978
Addition chains with multiplicative cost.
Discret. Math., 1978
1977
On the distance matrix of a directed graph.
J. Graph Theory, 1977
1976
Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory, Ser. A, 1976
On the distance matrix of a tree.
Discret. Math., 1976
Some NP-Complete Geometric Problems
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976
1975
Bounds for Multiprocessor Scheduling with Resource Constraints.
SIAM J. Comput., 1975
The Largest Small Hexagon.
J. Comb. Theory, Ser. A, 1975
On Packing Squares with Equal Squares.
J. Comb. Theory, Ser. A, 1975
1974
Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.
SIAM J. Comput., 1974
Performance Bounds on the Splitting Algorithm for Binary Testing.
Acta Informatica, 1974
1973
Covering the Positive Integers by Disjoint Sets of the Form {[n alpha + beta]: n = 1, 2, ...}.
J. Comb. Theory, Ser. A, 1973
Euclidean Ramsey Theorems I.
J. Comb. Theory, Ser. A, 1973
Bounds on Scheduling with Limited Resources.
Proceedings of the Fourth Symposium on Operating System Principles, 1973
1972
An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set.
Inf. Process. Lett., 1972
Complements and transitive closures.
Discret. Math., 1972
Optimal Scheduling for Two-Processor Systems.
Acta Informatica, 1972
Worst-Case Analysis of Memory Allocation Algorithms
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972
Bounds on multiprocessing anomalies and related packing algorithms.
Proceedings of the American Federation of Information Processing Societies: AFIPS Conference Proceedings: 1972 Spring Joint Computer Conference, 1972
1969
Universal Single Transition Time Asynchronous State Assignments.
IEEE Trans. Computers, 1969
Bounds on Multiprocessing Timing Anomalies.
SIAM Journal of Applied Mathematics, 1969
1968
An Upper Bound on Minimum Distance for a k-ary Code
Inf. Control., July, 1968
On Finite 0-Simple Semigroups and Graph Theory.
Math. Syst. Theory, 1968
1967
On n-Valued Functionally Complete Truth Functions.
J. Symb. Log., 1967
