ACM Fellow 1997, "For numerous contributions to the theory of computation, to communication theory and information theory, and to related areas of mathematics.".
IEEE Fellow 1995, "For contributions to the design of switching networks, complexity theory, parallel computing, and reliable computation.".
2023
Computation with Limited Space.
Proceedings of the Logic, 2023
2022
A Formula for the Determinant.
CoRR, 2022
2015
Asymptotic Analysis of Run-Length Encoding.
CoRR, 2015
2014
Large-Deviation Bounds for Sampling without Replacement.
Am. Math. Mon., 2014
Stochastic service systems, random interval graphs and search algorithms.
Random Struct. Algorithms, 2014
Computational Aspects of M.C. Escher's Ribbon Patterns.
Theory Comput. Syst., 2014
2013
Local versus global search in channel graphs.
Networks, 2013
Fault tolerance in cellular automata at low fault rates.
J. Comput. Syst. Sci., 2013
Gap Theorems for the Delay of Circuits Simulating Finite Automata.
CoRR, 2013
Barred Preferential Arrangements.
Electron. J. Comb., 2013
2012
Efficient Algorithms for Zeckendorf Arithmetic
CoRR, 2012
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012
2011
On-the-Fly Algorithms and Sequential Machines.
IEEE Trans. Computers, 2011
Two Extensions of Results of Archimedes.
Am. Math. Mon., 2011
Carry propagation in multiplication by constants.
ACM Trans. Algorithms, 2011
Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service
CoRR, 2011
The M/M/Infinity Service System with Ranked Servers in Heavy Traffic
CoRR, 2011
A Census of Vertices by Generations in Regular Tessellations of the Plane.
Electron. J. Comb., 2011
2010
Large deviations and moments for the Euler characteristic of a random surface.
Random Struct. Algorithms, 2010
2009
Attribute estimation and testing quasi-symmetry.
Inf. Process. Lett., 2009
2008
Fault tolerance in cellular automata at high fault rates.
J. Comput. Syst. Sci., 2008
2006
The Linking Probability of Deep Spider-Web Networks.
SIAM J. Discret. Math., 2006
Topological characteristics of random triangulated surfaces.
Random Struct. Algorithms, 2006
2005
The average amount of information lost in multiplication.
IEEE Trans. Inf. Theory, 2005
SRT Division Algorithms as Dynamical Systems.
SIAM J. Comput., 2005
2004
Entropy and expected acceptance counts for finite automata.
IEEE Trans. Inf. Theory, 2004
2003
The inequalities of quantum information theory.
IEEE Trans. Inf. Theory, 2003
The shortest disjunctive normal form of a random Boolean function.
Random Struct. Algorithms, 2003
The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function
CoRR, 2003
2002
Quantum signal propagation in depolarizing channels.
IEEE Trans. Inf. Theory, 2002
Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs.
SIAM J. Discret. Math., 2002
Characterizations of 1-Way Quantum Finite Automata.
SIAM J. Comput., 2002
Analysis of Carry Propagation in Addition: An Elementary Approach.
J. Algorithms, 2002
Galois theory for minors of finite functions.
Discret. Math., 2002
Expected Acceptance Counts for Finite Automata with Almost Uniform Input.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002
2001
Enumeration of Equicolorable Trees.
SIAM J. Discret. Math., 2001
1999
Entropy and enumeration of boolean functions.
IEEE Trans. Inf. Theory, 1999
Upper and lower bounds for the average-case complexity of path-search.
Networks, 1999
The Computational Complexity of Knot and Link Problems.
J. ACM, 1999
1998
On the Maximum Tolerable Noise for Reliable Computation by Formulas.
IEEE Trans. Inf. Theory, 1998
Average-Case Lower Bounds for Noisy Boolean Decision Trees.
SIAM J. Comput., 1998
Random Struct. Algorithms, 1998
1997
ACM Trans. Program. Lang. Syst., 1997
Regular Languages and Stone Duality.
Theory Comput. Syst., 1997
Average-case bounds for the complexity of path-search.
Proceedings of the Advances in Switching Networks, 1997
Theories of computability.
Cambridge University Press, ISBN: 978-0-521-55380-3, 1997
1996
Routing algorithms for switching networks with probabilistic traffic.
Networks, 1996
Self-Routing Superconcentrators.
J. Comput. Syst. Sci., 1996
Lower Bounds for Noisy Boolean Decision Trees.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
1995
Analysis of a Recurrence Arising from a Construction for Nonblocking Networks.
SIAM J. Discret. Math., 1995
1994
Fault-Tolerant Circuit-Switching Networks.
SIAM J. Discret. Math., 1994
Parallel Algorithms for Routing in Nonblocking Networks.
Math. Syst. Theory, 1994
Symmetry in Self-Correcting Cellular Automata.
J. Comput. Syst. Sci., 1994
Proceedings of the Parallel and Distributed Computing, 1994
1992
The Asymptotic Optimality of Spider-Web Networks.
Discret. Appl. Math., 1992
An Elementary Approach to Some Analytic Asymptotics.
Proceedings of the Algorithm Theory, 1992
Polynomial Hash Functions Are Reliable (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992
1991
On a lower bound for the redundancy of reliable networks with noisy gates.
IEEE Trans. Inf. Theory, 1991
The Expected Capacity of Concentrators.
SIAM J. Discret. Math., 1991
The Blocking Probability of Spider-Web Networks.
Random Struct. Algorithms, 1991
Parallel Algorithms for Routing in Non-Blocking Networks.
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991
1990
Discret. Appl. Math., 1990
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990
Proceedings of the Handbook of Theoretical Computer Science, 1990
1989
Random Sequential Adsorption on Graphs.
SIAM J. Discret. Math., 1989
Asymptotic behavior of the chromatic index for hypergraphs.
J. Comb. Theory, Ser. A, 1989
Invariance of complexity measures for networks with unreliable gates.
J. ACM, 1989
Discret. Appl. Math., 1989
Analysis of Error Correction by Majority Voting.
Adv. Comput. Res., 1989
1988
Reliable computation by formulas in the presence of noise.
IEEE Trans. Inf. Theory, 1988
Wide-Sense Nonblocking Networks.
SIAM J. Discret. Math., 1988
Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput., 1988
Correction to "Computational Complexity of Algebraic Functions".
J. Comput. Syst. Sci., 1988
1987
Sorting and Selecting in Rounds.
SIAM J. Comput., 1987
The Complexity of Computations by Networks.
IBM J. Res. Dev., 1987
Expanding graphs contain all small trees.
Comb., 1987
1986
Alphabetic Minimax Trees of Degree at Most t.
SIAM J. Comput., 1986
Non-Blocking Networks (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986
Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986
1985
Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions.
Theor. Comput. Sci., 1985
On Networks of Noisy Gates
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985
1984
Bounding Fan-out in Logical Networks.
J. ACM, 1984
On Monotone Formulae with Restricted Depth (Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984
Parallel Communication with Limited Buffers (Preliminary Version)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984
1983
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Inf. Control., 1983
Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983
On Determinism versus Non-Determinism and Related Problems (Preliminary Version)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
1982
Superconcentrators of Depth 2.
J. Comput. Syst. Sci., 1982
Probabilistic Simulations (Preliminary Version)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982
Advances in Pebbling (Preliminary Version).
Proceedings of the Automata, 1982
1981
Bounds on the performance of protocols for a multiple-access broadcast channel .
IEEE Trans. Inf. Theory, 1981
A Fast Parallel Algorithm for Routing in Permutation Networks.
IEEE Trans. Computers, 1981
Pebbling with an Auxiliary Pushdown.
J. Comput. Syst. Sci., 1981
Computational Complexity of Algebraic Functions.
J. Comput. Syst. Sci., 1981
Algebraic Complexity Theory.
IBM J. Res. Dev., 1981
1980
On Another Boolean Matrix.
Theor. Comput. Sci., 1980
A New Lower Bound for the Number of Switches in Rearrangeable Networks.
SIAM J. Algebraic Discret. Methods, 1980
On the Evaluation of Powers and Monomials.
SIAM J. Comput., 1980
Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980
1979
Extendible Hashing - A Fast Access Method for Dynamic Files.
ACM Trans. Database Syst., 1979
The Minimum Number of Edges in Graphs with Prescribed Paths.
Math. Syst. Theory, 1979
Relations Among Complexity Measures.
J. ACM, 1979
Communication: On the Application of Coding Theory to Hashing.
IBM J. Res. Dev., 1979
On Simultaneous Resource Bounds (Preliminary Version)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979
Computational Complexity in Algebraic Function Fields (Preliminary Version)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979
1978
An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions.
Theor. Comput. Sci., 1978
The Complexity of Monotone Boolean Functions.
Math. Syst. Theory, 1978
On Rearrangeable and Non-Blocking Switching Networks.
J. Comput. Syst. Sci., 1978
1977
Information Theory and the Complexity of Boolean Functions.
Math. Syst. Theory, 1977
An Information-Theoretic Method in Combinatorial Theory.
J. Comb. Theory, Ser. A, 1977
1976
J. Comput. Syst. Sci., 1976
Shifting Graphs and Their Applications.
J. ACM, 1976
The Realization of Monotone Boolean Functions (Preliminary Version)
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976
On the Evaluation of Powers and Related Problems (Preliminary Version)
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976
1975
On Crossbar Switching Networks.
IEEE Trans. Commun., 1975
Information Theory and the Complexity of Switching Networks (Preliminary Version)
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975
1974
On the Complexity of Strictly Nonblocking Concentration Networks.
IEEE Trans. Commun., 1974
