Computational complexity theory

Information-based complexity

Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems that arise in physical science, economics, engineering, and mathematical finance. IBC has studied such continuous problems as path integration, partial differential equations, systems of ordinary differential equations, nonlinear equations, integral equations, fixed points, and very-high-dimensional integration. All these problems involve functions (typically multivariate) of a real or complex variable. Since one can never obtain a closed-form solution to the problems of interest one has to settle for a numerical solution. Since a function of a real or complex variable cannot be entered into a digital computer, the solution of continuous problems involves partial information. To give a simple illustration, in the numerical approximation of an integral, only samples of the integrand at a finite number of points are available. In the numerical solution of partial differential equations the functions specifying the boundary conditions and the coefficients of the differential operator can only be sampled. Furthermore, this partial information can be expensive to obtain. Finally the information is often contaminated by noise. The goal of information-based complexity is to create a theory of computational complexity and optimal algorithms for problems with partial, contaminated and priced information, and to apply the results to answering questions in various disciplines. Examples of such disciplines include physics, economics, mathematical finance, computer vision, control theory, geophysics, medical imaging, weather forecasting and climate prediction, and statistics. The theory is developed over abstract spaces, typically Hilbert or Banach spaces, while the applications are usually for multivariate problems. Since the information is partial and contaminated, only approximate solutions can be obtained. IBC studies computational complexity and optimal algorithms for approximate solutions in various settings. Since the worst case setting often leads to negative results such as unsolvability and intractability, settings with weaker assurances such as average, probabilistic and randomized are also studied. A fairly new area of IBC research is continuous quantum computing. (Wikipedia).

Video thumbnail

(IC 1.6) A different notion of "information"

An informal discussion of the distinctions between our everyday usage of the word "information" and the information-theoretic notion of "information". A playlist of these videos is available at: http://www.youtube.com/playlist?list=PLE125425EC837021F Attribution for image of TV static:

From playlist Information theory and Coding

Video thumbnail

From information theory to learning via Statistical Physics by Florent Krzakala

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

Why do simple models work? Partial answers from information geometry (Lecture 1) by Ben Machta

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

Information processing and thermodynamics in biophysical control... by S Vaikuntanathan (Lecture 2)

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

Computational Differential Geometry, Optimization Algorithms by Mark Transtrum

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

Information Theory Meets Quantum Physics: The magic of wave dynamics by Apoorva Patel

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

From information theory to learning via Statistical Physics: Introduction: by Florent Krzakala

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

Information processing and thermodynamics in biophysical control.. by S Vaikuntanathan (Lecture 1)

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

From information theory to learning via Statistical Physics: From statistical by Florent Krzakala

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

JunJie Wee (7/27/22): Mathematical AI in Molecular Sciences

Abstract: With great accumulations in experimental data, computing power and learning models, artificial intelligence (AI) is making great advancements in molecular sciences. Recently, the breakthrough of AlphaFold 2 in protein folding herald a new era for AI-based molecular data analysis

From playlist Applied Geometry for Data Sciences 2022

Video thumbnail

The information cost of quantum memoryless protocols - M. Lauriere - Main Conference - CEB T3 2017

Mathieu Lauriere (NYU Shanghai) / 12.12.2017 Title: The information cost of quantum memoryless protocols Abstract: In this talk, we will consider memoryless quantum communication protocols, where the two parties do not possess any memory besides their classical input and they take turns

From playlist 2017 - T3 - Analysis in Quantum Information Theory - CEB Trimester

Video thumbnail

What is Life? - with Paul Nurse

Living things are extraordinary and our quest to define life is one of the most fundamental questions in biology. Subscribe for regular science videos: http://bit.ly/RiSubscRibe Watch the Q&A: https://youtu.be/mmebQGrDtvY Sir Paul Nurse is a geneticist and cell biologist whose discoverie

From playlist Ri Talks

Video thumbnail

Toward a Causal Analysis of Generalization in Deep Learning - Behnam Neyshabur

Workshop on Theory of Deep Learning: Where next? Topic: Toward a Causal Analysis of Generalization in Deep Learning Speaker: Behnam Neyshabur Affiliation:Google Date: October 18, 2019 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

The Dark Side of Events

Events are our industry’s near and dear. All technological conferences are full of talks on event sourcing, event driven architectures, or event driven integrations. So hey, why not make another one? …But a bit different: Let’s talk about the dark side of this pattern. Events, as any tool,

From playlist Microservices

Video thumbnail

Designing an ABM by Bill Rand

Program Summer Research Program on Dynamics of Complex Systems ORGANIZERS: Amit Apte, Soumitro Banerjee, Pranay Goel, Partha Guha, Neelima Gupte, Govindan Rangarajan and Somdatta Sinha DATE : 15 May 2019 to 12 July 2019 VENUE : Madhava hall for Summer School & Ramanujan hall f

From playlist Summer Research Program On Dynamics Of Complex Systems 2019

Video thumbnail

An introduction to the wavelet transform (and how to draw with them!)

The wavelet transform allows to change our point of view on a signal. The important information is condensed in a smaller space, allowing to easily compress or filter the signal. A lot of approximations are made in this video, like a lot of missing √2 factors. This choice was made to keep

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

DNA and Genetics | Astrobiology Course 5.2

Learn the foundations of astrobiology from Professor Impey, a University Distinguished Professor of Astronomy at the University of Arizona, with our Astrobiology: Exploring Other Worlds course here on YouTube. This video is part of module 5, Complex Life & Intelligence. Want to take the f

From playlist Astrobiology Course Module 5: Emerging Life & Intelligence

Video thumbnail

Information processing and thermodynamics in biophysical control.. by S Vaikuntanathan (Lecture 3)

26 December 2016 to 07 January 2017 VENUE: Madhava Lecture Hall, ICTS Bangalore Information theory and computational complexity have emerged as central concepts in the study of biological and physical systems, in both the classical and quantum realm. The low-energy landscape of classical

From playlist US-India Advanced Studies Institute: Classical and Quantum Information

Video thumbnail

An Introduction to Data Structures

Hello everyone and welcome to an Introduction to Data Structures. In this lecture-style course, I’ll be taking through the topic of Data Structures in relation to Computer Science. We’ll go over what Data Structures are, how we measure a Data Structures efficiency, and then hop into talkin

From playlist Software Development

Related pages

Numerical integration | Integer factorization | Monte Carlo method | Travelling salesman problem | Fixed point (mathematics) | Statistics | Curse of dimensionality | Banach space | Continuous-variable quantum information | Numerical weather prediction | Control theory | Real number | Low-discrepancy sequence | Path integration | Fundamental theorem of calculus | Mathematical finance | Hilbert space | Complex number | Quasi-Monte Carlo method | Analysis of algorithms