FORRY@cs.columbia.edu (Mary Forry) (04/17/87)
- -
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"
- -