131 - 140 of 206 results for: CS

The mathematical tools needed for the geometrical aspects of computer graphics and especially for modeling smooth shapes. Fundamentals: homogeneous coordinates, transformations, and perspective. Theory of parametric and implicit curve and surface models: polar forms, Bezier arcs and de Casteljau subdivision, continuity constraints, B-splines, tensor product, and triangular patch surfaces. Subdivision surfaces and multiresolution representations of geometry. Representations of solids and conversions among them. Surface reconstruction from scattered data points. Geometry processing on meshes, including simplification. Prerequisite: linear algebra. Recommended: 164, 248.

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

An overview of circuit complexity, focusing on limitations of solving computational problems with circuits. Classical methods: diagonalization; the gate elimination method and circuit size lower bounds; the method of random restrictions and formula size lower bounds; approximating circuits with polynomials and depth-restricted lower bounds. Connections between circuit-analysis algorithms and circuit complexity: learning circuits via queries; pseudorandomness and derandomization; satisfiability algorithms. Prerequisite: CS254 or the equivalent mathematical maturity.

Topics: Pseudo randomness, multiparty computation, pairing-based and lattice-based cryptography, zero knowledge protocols, and new encryption and integrity paradigms. May be repeated for credit. Prerequisite: 255.

Topics vary annually. Possible topics include automata on infinite words, static analysis methods, runtime analysis methods, verification of real-time and hybrid systems, and formalization of middleware services. May be repeated for credit. Prerequisite: 256.

Topics of current research interest in the mathematical analysis of programming languages, structured operational semantics, domain theory, semantics of concurrency, rich type disciplines, problems of representation independence, and full abstraction. See Time Schedule or Axess for current topics. May be repeated for credit. Prerequisites: 154, 157, 258, or equivalents. (Staff)

Advanced material is often taught for the first time as a topics course, perhaps by a faculty member visiting from another institution. May be repeated for credit.

Topics: fundamental techniques used in the development of exact and approximate algorithms for combinational optimization problems such as generalized flow, multicommodity flow, sparsest cuts, generalized Steiner trees, load balancing, and scheduling. Using linear programming, emphasis is on LP duality for design and analysis of approximation algorithms; interior point methods for LP. Techniques for development of strongly polynomial algorithms. Prerequisites: 161 or 261, or equivalent.

The increasing sizes of the data sets around us have sparked an effort from the theory community to develop new frameworks for understanding algorithms. In many cases, the questions have become "What can we compute in time sub-linear in the size of data?" or "What can we compute if we are given only several passes over the data, with relatively little memory?". In a related vein, we are also facing the challenge of trying to understand extremely large, and complex objects---from social networks and gene interactions, to complex distributions over enormous domains---in these settings, we often only have access to a tiny fraction of the underlying object we hope to understand. What properties of graphs and distributions can be inferred from such sparse samples? The course will cover a variety of topics at this research frontier; topics will include the theoretical work on property testing, sampling, sketching, and streaming. Prerequisites: A good background in probability theory, linear algebra, and algorithms. A high level of mathematical maturity will be assumed.