Quantum complexity theory | Computational complexity theory

Gap-Hamming problem

In communication complexity, the gap-Hamming problem asks, if Alice and Bob are each given a (potentially different) string, what is the minimal number of bits that they need to exchange in order for Alice to approximately compute the Hamming distance between their strings. The solution to the problem roughly states that, if Alice and Bob are each given a string, then any communication protocol used to compute the Hamming distance between their strings does (asymptotically) no better than Bob sending his whole string to Alice. More specifically, if Alice and Bob are each given -bit strings, there exists no communication protocol that lets Alice compute the hamming distance between their strings to within using less than bits. The gap-Hamming problem has applications to proving lower bounds for many streaming algorithms, including moment frequency estimation and entropy estimation. (Wikipedia).

Video thumbnail

Hamming Code - Errors

How to detect and correct an error using the Hamming Code. Hamming codes are a type of linear code, see link for intro to linear code: https://www.youtube.com/watch?v=oYONDEX2sh8 Questions? Feel free to post them in the comments and I'll do my best to answer!

From playlist Cryptography and Coding Theory

Video thumbnail

Anti-concentration and the Gap-Hamming problem - Anup Rao

Computer Science/Discrete Mathematics Seminar I Topic: Anti-concentration and the Gap-Hamming problem Speaker: Anup Rao Affiliation: University of Washington Date: November 2, 2020 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Hamming Code For Error Detection And Correction | Hamming Code Error Correction | Simplilearn

In this video on "Hamming Code for Error Detection," we will look into the introductory knowledge related to the network technique of hamming code. This network will allow us to detect and correct errors on the receiver side. Explained in the stepwise format for proper clarification. Topi

From playlist Networking

Video thumbnail

Math for Liberal Studies - Lecture 3.5.2 Hamming Distance

This is the second video for Math for Liberal Studies Section 3.5: Error-Correcting Codes. In this video, we discuss the Hamming distance between two binary messages. We also discuss the "minimum distance decoding method" for detecting and correcting errors.

From playlist Math for Liberal Studies Lectures

Video thumbnail

Error-Correcting Codes - Swastik Kopparty

Swastik Kopparty Institute for Advanced Study March 23, 2011 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Prime Gaps and The Crazy Sequences of Steps

When we try to avoid multiples of numbers using sequences we find a very unique way to create a prime list that has its own properties and curiosities. These sequences are state machines that can become very complex to generate but should be very simple to read.

From playlist Summer of Math Exposition Youtube Videos

Video thumbnail

Finding Minimum Distance

In this video I briefly explain what minimum distance is and why it is helpful. Then I explain how to find it "the long way" and the "shortcut." Also during the process, I explain what Hamming Weight and Distance are and how to find them. Codewords from Generating Matrix Video: https://w

From playlist Cryptography and Coding Theory

Video thumbnail

Physics - Optics: Diffraction Grating (2 of 7) Distances=? Between Slits

Visit http://ilectureonline.com for more math and science lectures! In this video I will find the distances between the slits of a diffraction grating. Next video in series: http://youtu.be/uSchtEB2kfg

From playlist PHYSICS 61 DIFFRACTION OF LIGHT

Video thumbnail

04 Balancing Equations to find an error

In this video we find an error in a students work

From playlist skill 8 attempt 1

Video thumbnail

Proof and Circuit Complexity - Robert Robere

Short talks by postdoctoral members Topic: Proof and Circuit Complexity Speaker: Robert Robere Affiliation: Member, School of Mathematics For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Nexus trimester - Yitong Yin (Nanjing University)

Rectangle inequalities for data structure lower bounds Yitong Yin (Nanjing University) February 23, 2016 Abstract: The richness lemma is a classic rectangle-based technique for asymmetric communication complexity and cell-probe lower bounds. The technique was enhanced by the Patrascu-Thoru

From playlist Nexus Trimester - 2016 - Fundamental Inequalities and Lower Bounds Theme

Video thumbnail

AQC 2016 - Quantum Monte Carlo vs Tunneling vs. Adiabatic Optimization

A Google TechTalk, June 27, 2016, presented by Aram Harrow (MIT) ABSTRACT: Can quantum adiabatic evolution solve optimization problems much faster than classical computers? One piece of evidence for this has been their apparent advantage in "tunneling" through barriers to escape local mi

From playlist Adiabatic Quantum Computing Conference 2016

Video thumbnail

An Isoperimetric Inequality for the Hamming Cube and Integrality Gaps in Graphs - Siavosh Benabbas

Siavosh Benabbas Institute for Advanced Study November 21, 2011 In 1970s Paul Erdos asked the following question: Consider all the boolean strings of length n. Assume that one has chosen a subset S of the strings such that no two chosen strings are different in precisely n/4 (or its closes

From playlist Mathematics

Video thumbnail

Lec 5 | MIT 6.451 Principles of Digital Communication II

Introduction to Binary Block Codes View the complete course: http://ocw.mit.edu/6-451S05 License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 6.451 Principles of Digital Communication II

Video thumbnail

The communication complexity of distributed subgraph detection - Rotem Oshman

Rotem Oshman Tel Aviv University October 6, 2014 In distributed systems, communication between the participants in the computation is usually the most expensive part of the computation. Theoretical models of distributed systems usually reflect this by neglecting the cost of local computat

From playlist Mathematics

Video thumbnail

Locally Repairable Codes, Storage Capacity and Index Coding - Arya Mazumdar

Computer Science/Discrete Mathematics Seminar I Topic: Locally Repairable Codes, Storage Capacity and Index Coding Speaker: Arya Mazumdar Affiliation: University of Massachusetts, Amherst Date: Febuary 5, 2018 For more videos, please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Stability and sofic approximations for product groups and property (tau) - Adrian Ioana

Stability and Testability Topic: Stability and sofic approximations for product groups and property (tau) Speaker: Adrian Ioana Affiliation: University of California, San Diego Date: November 4, 2020 For more video please visit http://video.ias.edu

From playlist Stability and Testability

Video thumbnail

AQC 2016 - Simulated Quantum Annealing Can Be Exponentially Faster Than Classical

A Google TechTalk, June 27, 2016, presented by Elizabeth Crosson (Caltech) ABSTRACT: Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing: Cost functions with thin, high energy barriers can exhibit exponential separations between the run-time of class

From playlist Adiabatic Quantum Computing Conference 2016

Video thumbnail

Prime Gaps As Large As You Want (and Larger!) // [NUMBER THEORY]

This is one of the most stunningly cool things I've learned about the prime numbers: it's trivial to construct infinitely large gaps between them. Subscribe: https://bit.ly/polymathematic | Enable ALL push notifications 🔔 To be sure, we want to be careful about the sense in which we're u

From playlist Math Mini

Related pages

Big O notation | Concentration inequality | Communication complexity | Hamming distance