Testing Boolean Functions

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=vWxokddBUq8


Duration: 1:02:02
52 views
1

Erik Waingarten (University of Pennsylvania)
https://simons.berkeley.edu/talks/erik-waingarten-university-pennsylvania-2024-05-21
Sublinear Algorithms Boot Camp

This bootcamp talk will be an overview on testing Boolean functions. A Boolean function is a function which maps inputs of a domain to {0, 1} (in other words, encoding a subset of the domain) and the task in property testing is to approximately determine whether the function has a particular property. We aim for algorithms which are really, really efficient (think constant or poly-logarithmic queries to the function). We will cover the definitions of (standard) property testing and some variants, as well as some of the well-known algorithms and analyzes.



Other Videos By Simons Institute for the Theory of Computing


2024-05-29Adversarially Robust Streaming Algorithms
2024-05-29New Advances on Multi-Pass Graph Streaming Lower Bounds
2024-05-29Coresets and Their Applications to Design Sublinear Algorithms
2024-05-29An Overview on Data Streams Algorithms
2024-05-29Graph Coloring Through the Sublinear Lens
2024-05-29Conditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
2024-05-29Graph Algorithms in the MPC Model
2024-05-29An Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
2024-05-29Sampling Big Ideas in Sublinear Algorithms
2024-05-29Counting Subgraphs in Sublinear Time
2024-05-29Testing Boolean Functions
2024-05-29Property Testing for Graphs
2024-04-30Using chaos to characterize a programmable analog quantum simulator
2024-04-30Fundamental limits to quantum computation
2024-04-30Evidence for the utility of quantum computing before fault tolerance
2024-04-30High-fidelity and Fault-tolerant Teleportation of a Logical Qubit on a Trapped-ion Quantum Computer
2024-04-30An Overview of Quantum Algorithms
2024-04-30Certifying almost all quantum states with few single-qubit measurements
2024-04-30Learning Shallow Quantum Circuits and Quantum States Prepared by Shallow Circuits in Polynomial Time
2024-04-30A Quantum Speed-Up for Approximating the Top Eigenvector of aMatrix via Improved Tomography
2024-04-30The Virtues of the Quantum Approximate Optimization Algorithm


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Sublinear Algorithms Boot Camp
Erik Waingarten