Publications
On Linear Characterizations of Combinatorial Optimization Problems.
SIAM Journal on Computing. 11(4), 620-632.
(1982).
(1982). On the security of ping-pong protocols.
55(1-3), 57-68.
(1982). Global Wire Routing in Two-Dimensional Arrays.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 453-459.
(1983). Monte-Carlo Algorithms for Enumeration and Reliability Problems.
Proceedings of the 24th Annual Symposium on Foundations of Computer Science. 56-64.
(1983). Searching for an optimal path in a tree with random costs.
Artificial Intelligence. 21(1-2), 99-116.
(1983). The complexity of parallel computation.
Proceedings of the 23rd Annual Allerton Conference on Communication, Control, and Computing. 1.
(1985). A fast parallel algorithm for the maximal independent set problem.
Journal of the Association for Computing Machinery. 32(4), 762-773.
(1985). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Proceedings of the Symposium on the Complexity of Approximately Solved Problems. 45-64.
(1985). Monte-Carlo Algorithms for the Planar Multiterminal Network Reliability Problem.
Journal of Complexity. 1,
(1985). Circuit placements and costs bounds by eigenvector decomposition.
Proceedings of the IEEE International Conference on Computer-Aided Design (ICCAD-86), A Conference for the EE CAD Professional. 414-417.
(1986). Combinatorics, Complexity, and Randomness.
Communications of the ACM. 29(2), 98-109.
(1986). Combinatorics, Complexity and Stochastic Algorithms.
Informatie. 28(9), 722-733.
(1986). The complexity of parallel computation.
Proceedings of the Fourth MIT Conference on Advanced Resarch in VLSI.
(1986). A family of simplex variants solving an m*d linear program in expected number of pivot steps depending on d only.
Mathematics of Operations Research. 11(4), 570-590.
(1986). FED bin packing for item sizes with distributions on (0,1/2).
Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 322-330.
(1986). On a Search Problem Related to Branch-and-Bound Procedures.
Proceedings of the 27th Annual Symposium on Foundations of Computer Science. 19-28.
(1986). Efficient randomized pattern-matching algorithms.
IBM Journal of Research and Development. 31(2), 249-260.
(1987). Global wire routing in two-dimensional arrays.
2(1), 113-129.
(1987). A Simplex variant solving an m*d linear program in O(min(m2, d2)) expected number of pivot steps.
Journal of Complexity. 3(4), 372-387.
(1987). The Complexity of Parallel Search.
Journal of Computer and System Sciences. 36,
(1988). The Complexity of Parallel Search.
Proceedings of the 17th Annual ACM Symposium on the Theory of Computing. 225-253.
(1988). Deferred Data Structuring.
SIAM Journal on Computing. 17(5), 883-902.
(1988). A randomized parallel branch-and-bound procedure.
Proceedings of the 20th Annual ACM Symposium on Theory of Computing. 290-300.
(1988). Subtree isomorphism is in random NC.
Proceedings of the Third Aegean Workshop on Computing, VLSI Algorithms and Architectures (AWOC 88). 43-52.
(1988).