Improved Monotonicity Testers via Hypercube Embeddings

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


Duration: 26:23
62 views
0

Authors: Mark Braverman (Princeton University), Subhash Khot (NYU); Guy Kindler (Hebrew University of Jerusalem); Dor Minzer (MIT)
ITCS - Innovations in Theoretical Computer Science



Other Videos By Simons Institute for the Theory of Computing


2023-01-04Quantum space, ground space traversal, and how to embed multi-prover...
2023-01-04Necessary Conditions in Multi-Server Differential Privacy
2023-01-04Making Decisions under Outcome Performativity
2023-01-04A New Conjecture on Hardness of Low-Degree 2-CSP’s with...
2023-01-04On Interactive Proofs of Proximity with Proof-Oblivious Queries
2023-01-04Quantum algorithms and the power of forgetting
2023-01-04Exact Completeness of LP Hierarchies for Linear Codes
2023-01-04Learning versus Pseudorandom Generators in Constant Parallel Time
2023-01-04Strategyproof Scheduling with Predictions
2023-01-03Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks
2023-01-03Improved Monotonicity Testers via Hypercube Embeddings
2023-01-03Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
2023-01-03Online Learning and Bandits with Queried Hints
2023-01-03Matroid Partition Property and the Secretary Problem
2023-01-03The Time Complexity of Consensus Under Oblivious Message Adversaries
2023-01-03Learning Reserve Prices in Second-Price Auctions
2023-01-03Efficiently Testable Circuits
2023-01-03Bootstrapping Homomorphic Encryption via Functional Encryption
2023-01-03Downward self-reducibility in TFNP
2023-01-03Recovery from Non-Decomposable Distance Oracles
2023-01-03Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
ITCS - Innovations in Theoretical Computer Science