arvind@utcsri.UUCP (Arvind Gupta) (04/08/87)
From: Mary Forry <FORRY@cs.columbia.edu> Subject: Symposium Announcement Second Symposium on Complexity of Approximately Solved Problems April 20-24, 1987 Computer Science Department Columbia University New York, New York 10027 Support: This symposium is supported by a grant from the System Development Foundation. Location: On April 20 the symposium will be held in the Kellogg Conference Center on the 15th floor of the International Affairs Building, 118th Street and Amsterdam Avenue. On April 21 the symposium will be held in the Carleton Lounge on the 4th floor of the Engineering School Building, 500 West 120th Street (at Amsterdam Avenue). On April 22-24 it will be held in the Kellogg Conference Center on the Fifteenth floor of the International Affairs building. Registration will start at 9:00am. There is no registration fee. Information: Contact the Computer Science Department, Columbia University, (212) 280-2736. Publication: Invited papers will appear in the Journal of Complexity. Program All papers are by invitation. In case of multiple authors, the speaker is indicated by an asterisk (*). April 20: Tutorial Lectures 9:00 - 10:00 Coffee and Registration 9:30 - 11:30 R. Karp, University of California, Berkeley "Probabilistic Analysis of Combinatorial Algorithms" 11:30 - 1:00 Lunch 1:00 - 3:00 S. Smale, University of California, Berkeley "On the Efficiency of Algorithms for Solving Systems of Equations" 3:00 - 3:30 Tea 3:30 - 5:30 H. Wozniakowski, Columbia University and University of Warsaw "Basic Concepts of Information-Based Complexity" April 21 9:00 - 9:30 Coffee and Registration 9:30 - 10:00 L. Valiant, Harvard University "Computationally Feasible Learning" 10:00 - 10:30 E. Coffman, M. Garey, D. Johnson*, AT&T Bell Laboratories "Bin Packing with Divisible Item Sizes" 10:30 - 11:00 V. Lumelsky, Yale University "Algorithmic and Complexity Issues of Robot Motion in an Uncertain Environment" 11:00 - 11:30 Break 11:30 - 12:00 E. Packel, Lake Forest College "The Algorithm Designer Versus Nature: A Game Theoretic Approach to Information-Based Complexity" 12:00 - 12:30 Y. Abu-Mostafa, California Institute of Technology "Statistical Computation of Low-Entropy Functions" 12:30 - 2:00 Lunch 2:00 - 2:30 G. Wahba, University of Wisconsin "Problems in Multivariate Function Estimation Given Noisy, Scattered Observational Data" 2:30 - 3:00 G. Wasilkowski, Columbia University "Randomization for Continuous Problems" 3:00 - 3:30 D. Ylvisaker, University of California, Los Angeles "Bayesian Interpolation Schemes" 3:30 - 4:00 Tea 4:00 - 4:30 A. Sukharev, Moscow State University "The Concept of Sequential Optimality for Problems in Numerical Analysis" 4:30 - 5:00 J. Demmel, New York University "The Geometry of Ill-Conditioning" April 22 9:30 - 10:00 S. Smale, University of California, Berkeley "On the Topology of Algorithms I" 10:00 - 10:30 J. Renegar, Stanford University "On the Worst-Case Arithmetic Complexity of Approximating Zeros of Polynomials" 10:30 - 11:00 K. Sikorski*, University of Utah and H. Wozniakowski, Columbia University and University of Warsaw "Complexity of Fixed Points" 11:00 - 11:30 Break 11:30 - 12:00 D. Saari, Northwestern University "Some Informational Requirements for Convergence" 12:00 - 12:30 J. Yorke, University of Maryland "Testing the Validity of Numerically Determined Trajectories of Chaotic Dynamical Systems" 12:30 - 2:00 Lunch 2:00 - 2:30 T. Boult, Columbia University "Optimal Algorithms: Tools for Mathematical Modeling" 2:30 - 3:00 T. Poggio, Massachusetts Institute of Technology "Computational Vision and Regularization Theory" 3:00 - 3:30 B. Kacewicz, University of Warsaw "Optimal Solution of Ordinary Differential Equations" 3:30 - 4:00 Tea 4:00 - 4:30 M. Sipser, Massachusetts Institute of Technology "Expanders, Randomness, or Time versus Space" 4:30 - 5:00 R. Karp, University of California, Berkeley "Simplified Probabilistic Analysis of a Variant of the Simplex Algorithm" April 23 9:30 - 10:00 I. Babuska* and M. Bieterman, University of Maryland "Computational Practice and Informational-Based Approaches" 10:00 - 10:30 A. Werschulz, Fordham University "An Information-Based Approach to Ill-Posed Problems" 10:30 - 11:00 M. Schultz, Yale University TBA 11:00 - 11:30 Break 11:30 - 12:00 T. Jackowski and H. Wozniakowski*, Columbia University and University of Warsaw "Complexity of Approximation with Relative Error Criterion in Worst, Average and Probabilistic Settings" 12:00 - 12:30 Z. Galil*, Columbia University and Tel Aviv University, and R. Giancarlo, Columbia University "Data Structures and Algorithms for Approximate String Matching" 12:30 - 2:00 Lunch 2:00 - 2:30 H. T. Kung, Carnegie-Mellon University "Trading Local Communication for Global Communication" 2:30 - 3:00 Z. Luo and J. Tsitsiklis*, Massachusetts Institute of Technology "Communication Complexity of Convex Optimization" 3:00 - 3:30 S. Micali, Massachusetts Institute of Technology "A Completeness Theorem for Distributed Protocols with Honest Majority" 3:30 - 4:00 Tea 4:00 - 4:30 L. Blum, Mills College "A New Simple Homotopy Algorithm for Linear Programming I" 4:30 - 5:00 M. Shub, IBM "The Boundary Behavior of Interior Point Algorithms in Linear Programming" April 24 9:30 - 10:00 L. Hurwicz, University of Minnesota, and T. Marschak,* University of California, Berkeley "Approximating a Function by Choosing a Covering of Its Domain and @i{k} Points From Its Range" 10:00 - 10:30 B. Bojanov, University of Sofia "@g{s}-Perfect Splines and Their Application to Optimal Recovery Problems" 10:30 - 11:00 C. Micchelli and T. Rivlin*, IBM "An Optimal Recovery View of Walsh Equiconvergence" 11:00 - 11:30 Break 11:30 - 12:00 B. Kacewicz, University of Warsaw, M. Milanese* and A. Vincino, Politechnico di Torino "Conditionally Optimal Algorithms and Estimation of Reduced Order Models" 12:00 - 12:30 D. Lee*, AT&T Bell Laboratories, T. Pavlidis, SUNY Stony Brook, and G.W. Wasilkowski, Columbia University "On Trade-Off Between Sampling and Quantization" 12:30 - 2:00 Lunch 2:00 - 2:30 Ker-I Ko, SUNY Stony Brook "On the Continued Fraction Representation of Computable Real Numbers" 2:30 - 3:00 A. Yao, Princeton University "On Computing with Unreliable Tests" 3:00 - 3:30 G. Georgakopoulos, D. Kavvadias, and C. Papadimitriou,* Stanford University and University of Athens "Probabilistic Satisfiability"