Computer Science and Discrete Mathematics

Computer Science and Discrete Mathematics

Institute for Advanced Study via YouTube Direct link

Minkowski sums, mixed faces and combinatorial isoperimetry - Adiparsito

449 of 473
Previous
Next

449 of 473

Minkowski sums, mixed faces and combinatorial isoperimetry - Adiparsito

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

Computer Science and Discrete Mathematics

Automatically move to the next video in the Classroom when playback concludes
  1. 1 On Turán Numbers of hyper Graphs - Maya Sankar
  2. 2 Trickle-down Theorems for High-dimensional Expanders via Lorentzian Polynomials - Jonathan Leake
  3. 3 Linial Meshulam Complexes 2 - Michael Chapman
  4. 4 How Low Can We Go? Exploring Minimal Assumptions in Quantum Cryptography - Dakshita Khurana
  5. 5 Linial--Meshulam Complexes - Michael Chapman
  6. 6 Why Language Models Hallucinate - Adam Kalai
  7. 7 Local List Decoding from HDX II - Yotam Dikstein
  8. 8 Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis - Aaron Putterman
  9. 9 Hard Functions from on High: Local List Decoding from HDX - Max Hopkins
  10. 10 On Beck-Fiala and Komlós Conjectures - Nikhil Bansal
  11. 11 No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu
  12. 12 New Approach to Matrix Perturbation: Beyond the Worst-Case Analysis - Van H. Vu
  13. 13 Aldous-type Spectral Gaps in Unitary Groups, Part II - Doron Puder
  14. 14 Explicit Lossless Vertex Expanders - Rachel Zhang
  15. 15 Aldous-type Spectral Gaps in Unitary Groups, Part I - Doron Puder
  16. 16 From Classical to Quantum Circuit Complexity: The Tale of (Q)AC0 - Francisca Vasconcelos
  17. 17 From PCPs to Parallel PCPs: Hardness of Approximation in Parameterized Complexity - Karthik C. S.
  18. 18 Adaptive Robustness of Hypergrid Johnson-Lindenstrauss - Andrej Bogdanov
  19. 19 Algorithms for Solving Random and Semirandom Planted Constraint Satisfaction Problems- Peter Manohar
  20. 20 Stronger Cell Probe Lower Bounds via Local PRGs - Oliver Korten
  21. 21 Approximate Covers and Cocycle Expansion - Irit Dveer Dinur
  22. 22 Asymptotic Spectrum and Approximation Approaches to Direct-sum Problems - Jeroen Zuiddam
  23. 23 Simulating Time With Square-Root Space (And With Details) - Ryan Williams
  24. 24 Balancing Extensions in Posets of Large Width - Maxwell Aires
  25. 25 Combinatorial and Geometric Challenges in PAC Learning with Partial Concepts - Shay Moran
  26. 26 Upper Bounds for Multicolour Ramsey Numbers - Marius Tiba
  27. 27 Why Extension-Based Proofs Fail - Faith Ellen
  28. 28 The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem - Guy Blanc
  29. 29 Coboundary Expansion Inside Chevalley High-Dimensional Expanders - Ryan O'Donnell
  30. 30 Language Generation in the Limit - Jon Kleinberg
  31. 31 Cosystolic Expansion - Irit Dveer Dinur
  32. 32 Locally Testable Codes with the Multiplication Property from High-dimensional Expanders - Siqi Liu
  33. 33 Improved Private Information Retrieval Schemes from Matching Vectors and Deriva...- Swastik Kopparty
  34. 34 Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity - Avi Wigderson
  35. 35 Efficiency, Resilience, and Artificial Intelligence - Moshe Y. Vardi
  36. 36 Connections Between Matrix Spaces and Graphs - Youming Qiao
  37. 37 A Zero-Knowledge PCP Theorem - Nicholas Spooner
  38. 38 On the Complexity of Isomorphism Problems for Tensors, Groups, Polynomials, and...- Youming Qiao
  39. 39 Simulating Time With Square-Root Space - Ryan Williams
  40. 40 A Theory of Generalized Boosting - Nataly Brukhim
  41. 41 Improved Fault-Tolerant Non-Clifford Gates (or: How to Multiply Quantumly) - Louis Golowich
  42. 42 Independent Sets in Random Cayley Graphs - Huy Tuan Pham
  43. 43 Finding Regular Subgraphs - Richard Montgomery
  44. 44 “Sharp” Selector Processes - Huy Tuan Pham
  45. 45 Monochromatic Sums and Products over the Rationals - Maria-Romina Ivan
  46. 46 The Error Resilience of Binary Codes with Interaction - Gillat Kol
  47. 47 Lower Bounds for Local Codes from Induced Subgraphs of Cayley Graphs - Peter Manohar
  48. 48 Low-Depth Algebraic Circuit Lower Bounds Over Any Field - Michael A. Forbes
  49. 49 Spectral Algorithms from Induced Subgraphs of Cayley Graphs - Peter Manohar
  50. 50 On Approximability of Satisfiable Constraint Satisfaction Problems & Applications - Amey Bhangale
  51. 51 Explicit Codes Approaching the Generalized Singleton Bound Using Expanders - Shashank Srivastava
  52. 52 Random Matrices From GLn(q) Sampled by Words - Doron Puder
  53. 53 Structure and Randomness for Finite-field Polynomials are (almost) Equivalent - Guy Moshkovitz
  54. 54 Problems in Extremal Combinatorics and Connections with Multiparty Communication... - Zander Kelley
  55. 55 Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications - Zander Kelley
  56. 56 Efficient Batch Verification: Recent Progress and Challenges - Ron Rothblum
  57. 57 A Review of the Notion of Graph Rigidity and Some Recent Developments - Orit Raz
  58. 58 QMA vs. QCMA and Pseudorandomness - Henry Yuen
  59. 59 Simple High Dimensional Expanders from Cayley Graphs - Yotam Dikstein
  60. 60 Dot-Product Proofs - Yuval Ishai
  61. 61 Quadratic Stability of the Brunn-Minkowski Inequality - Peter van Hintum
  62. 62 Induced Subgraphs and Pathwidth - Maria Chudnovsky
  63. 63 Linear Stability of the Brunn-Minkowski Inequality - Peter van Hintum
  64. 64 Quantum Locally Testable Codes and Codes with Transversal Gates - David (Ting-Chun) Lin
  65. 65 Fault Tolerant Routing Protocols on High-Dimensional Expanders - Mitali Bafna
  66. 66 Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders - Mitali Bafna
  67. 67 Sheaves on Graphs, the Hanna Neumann Conjecture, and My Debt to Number Theory and... - Joel Friedman
  68. 68 When and How are (promise) Constraint Satisfaction Problems Efficiently Sol...- Venkatesan Guruswami
  69. 69 Analytic Insights into the Zig-Zag Product and Its Friends: Part II - Gil Cohen
  70. 70 Subgroup Tests and the Aldous--Lyons Conjecture - Michael Chapman
  71. 71 Analytic Insights into the Zig-Zag Product and Its Friends: Part I - Gil Cohen
  72. 72 Subgroup Tests and Tailored Non-local Games - Michael Chapman
  73. 73 A New Approach to Strong Convergence - Ramon Van Handel
  74. 74 Sorting Using Partial Information - Robert Tarjan
  75. 75 Concentration on HDX: Derandomization Beyond Chernoff - Max Hopkins
  76. 76 An Improved Line-Point Low-Degree Test - Prahladh Harsha
  77. 77 Resolution of the Kohayakawa--Kreuter Conjecture - Raphael Steiner
  78. 78 Quantum Mechanics, Semidefinite Programming, and Graph Invariants - Matthew Hastings
  79. 79 Rounding Large Independent Sets on Expanders - Tim Hsieh
  80. 80 Incidence Bounds via Extremal Graph Theory - Istvan Tomon
  81. 81 Triangulated Surfaces in Moduli Space - Sahana Vasudevan
  82. 82 Lower Bounds for Set-Multilinear Branching Programs - Shubhangi Saraf
  83. 83 Random Cayley Graphs From a Combinatorial Perspective - Huy Tuan Pham
  84. 84 Additive Combinatorics Without Groups - Huy Tuan Pham
  85. 85 Parallel Repetition for 3-Player XOR Games - Yang Liu
  86. 86 Graphs, CSPs and Codes - Madhu Sudan
  87. 87 Avi Wigderson, 2023 Turing Award Laureate, Q&A with David Nirenberg | Institute for Advanced Study
  88. 88 The Method of Hypergraph Containers - Wojciech Samotij
  89. 89 Polynomial Capacity and its Applications: To TSP and Beyond - Jonathan Leake
  90. 90 New Derandomized Agreement Testers - Yotam Dikstein
  91. 91 Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries - Huacheng Yu
  92. 92 Sparsification of Gaussian Processes - Anindya De
  93. 93 Locally Consistent Decomposition of Strings with Applications to Edit Distance Ske...- Michal Koucký
  94. 94 Explicit SoS Lower Bounds from High Dimensional Expanders - Max Hopkins
  95. 95 Computing Greatest Common Divisors of Polynomials in Parallel - Robert Andrews
  96. 96 Stability and Learning in Strategic Games - Éva Tardos
  97. 97 Analyzing the Max Entropy Algorithm for TSP - Nathan Klein
  98. 98 Reconstruction on Trees and Hypertrees - Yuzhou Gu
  99. 99 Advances in Parallel and Private Stochastic Optimization from Ball Acceleration - Kevin Tian
  100. 100 An Exponential Lower bound on Three Query, Linear Locally Correctable Codes - Pravesh Kothari
  101. 101 Expanding the Reach of P not equal to NP: the Minimum Circuit Size Problem with a... - Rahul Ilango
  102. 102 Omniprediction and Multigroup Fairness - Parikshit Gopalan
  103. 103 The Tree Evaluation Problem: Context and Recent Results - Ian Mertz
  104. 104 Online Discrepancy Minimization - Victor Reis
  105. 105 Marton's Conjecture, aka the Polynomial Freiman--Ruzsa conjecture - Frederick Manners
  106. 106 Online Omniprediction - Sumegha Garg
  107. 107 Coboundary and Cosystolic Expansion - Siqi Liu
  108. 108 Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition - Or Meir
  109. 109 Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting- William Hoza
  110. 110 Recent Progress on Derandomizing Space-Bounded Computation - William Hoza
  111. 111 Sparsifying Sums of Functions - Yang Liu
  112. 112 Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications - Nitya Mani
  113. 113 The Iterative Win-Win Method, and Explicit Constructions (without) Using It - Hanlin Ren
  114. 114 A Definition of Spectral Gap for Nonreversible Markov Chains - Sourav Chatterjee
  115. 115 High Dimensional Expanders and Sparsifications of the Johnson Graph - Yotam Dikstein
  116. 116 A High Dimensional Goldreich-Levin Theorem - Silas Richelson
  117. 117 An Optimization Perspective on Log-concave Sampling - Sinho Chewi
  118. 118 A Proof of the RM Code Capacity Conjecture - Emmanuel Abbé
  119. 119 Extending Generalization Theory towards addressing modern challenges in Machine Learning- Shay Moran
  120. 120 A Combinatorial Characterization of Minimax in Win/Lose Games - Shay Moran
  121. 121 Shrinkage Under Random Restrictions - Robert Andrews
  122. 122 Private Optimization and Statistical Physics: Low-Rank Matrix Approximation - Nisheeth Vishnoi
  123. 123 Learning from Dynamics - Ankur Moitra
  124. 124 The Diffraction Limit and Extremal Functions - Ankur Moitra
  125. 125 Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?) - Avi Wigderson
  126. 126 Using Expanders for Fast Graph Algorithms - Thatchaphol Saranurak
  127. 127 Graph Vertex Expansion - Theo McKenzie
  128. 128 Fitting Various Metrics with Minimum Disagreements - Euiwoong Lee
  129. 129 A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture - Justin Gilmer
  130. 130 A Unified Approach to Discrepancy Minimization - Nikhil Bansal
  131. 131 Approximating Iterated Multiplication of Stochastic Matrices in Small Space - Dean Doron
  132. 132 Existence of Subspace Designs - Ashwin Sah
  133. 133 Unit and Distinct Distances in Typical Norms - Noga Alon
  134. 134 Updates on the Lipschitz Extension Problem - Assaf Naor
  135. 135 Quantum Error Correction, Systolic Geometry, and Probabilistic Embeddings - Elia Portnoy
  136. 136 Hausdorff Dimension Analogues of the Elekes - Ronyai Theorem and Related Problems - Orit Raz
  137. 137 Common Linear Patterns Are Rare - Nina Kamčev
  138. 138 The Lens of Abelian Embeddings - Dor Minzer
  139. 139 Strong Bounds for 3-Progressions: In-Depth - Zander Kelley
  140. 140 Extremal Problems for Uniformly Dense Hypergraphs - Mathias Schacht
  141. 141 Strong Bounds for 3-Progressions - Raghu Meka
  142. 142 Why Can’t We Classically Describe Quantum Systems? - Chinmay Nirkhe
  143. 143 Recent Progress in Randomness Extraction - Eshan Chattopadhyay
  144. 144 Two (More) Algorithms for Set Cover - Anupam Gupta
  145. 145 From Robust Sublinear Expanders to Additive Number Theory via Rainbow Cycles - Matija Bucic
  146. 146 Rainbow Matchings in Hypergraphs - Cosmin Pohoata
  147. 147 Efficient Verification of Computation on Untrusted Platforms - Yael Kalai
  148. 148 Overview and Recent Results in Combinatorial Auctions - Matt Weinberg
  149. 149 Smooth Coverings of Space - Oded Regev
  150. 150 On Matrix Multiplication and Polynomial Identity Testing - Robert Andrews
  151. 151 Locally Decodable Codes - Zeev Dvir
  152. 152 Non-measurability of the inverse theorem for the Gowers norms - Terence Tao
  153. 153 A Characterization of Multiclass Learnability - Nataly Brukhim
  154. 154 Optimization-Friendly Generic Mechanisms Without Money - Mark Braverman
  155. 155 Online List Labeling: Breaking the log2 n Barrier - Nicole Wein
  156. 156 Optimal Weak to Strong Learning - Kasper Green Larsen
  157. 157 Superfast Derandomization of Interactive Proof Systems - Roei Tell
  158. 158 The Hypergraph Container Method, Partition Containers, and Algorithmic Applications - Or Zamir
  159. 159 Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model - Mark Sellke
  160. 160 The Polynomial Method in Communication Complexity - Pei Wu
  161. 161 Strong XOR Lemma for Communication with Bounded Rounds - Huacheng Yu
  162. 162 Additive combinatorics through the lens of communication complexity - Toniann Pitassi
  163. 163 Communication and Query Complexity of Bipartite Perfect Matching - Yuval Efron
  164. 164 Introduction to Natural Quasirandomness: Unique Colorability and Order-ability - Leonardo Coregliano
  165. 165 Smoothed Complexity of Local Max-Cut with Two Flips - Xi Chen
  166. 166 Average-Case Computational Complexity of Tensor Decomposition - Alex Wein
  167. 167 Almost Linear Time Algorithms for Max-flow and More - Sushant Sachdeva
  168. 168 The Optimal Error Resilience of Interactive Communication over the Binary Alphabet - Rachel Zhang
  169. 169 Is your distribution in shape? - Ronitt Rubinfeld
  170. 170 Almost Ramanujan Expanders from Arbitrary Expanders via Operator Ampli... - Fernando Granha Jeronimo
  171. 171 Relative rank and regularity - Tamar Ziegler
  172. 172 Robust sublinear expanders, and an application towards the Erdos-Gallai conjecture - Matija Bucic
  173. 173 Making Proofs More Constructive, and Algorithms Less Random - Oliver Korten
  174. 174 Graphs as geometric objects - Nathan Linial
  175. 175 On Approximability of CSPs on Satisfiable Instances - Subhash Khot
  176. 176 Exact algorithms for graph coloring - Or Zamir
  177. 177 List decoding with double samplers - Inbal Livni-Navon
  178. 178 An Introduction to Binary Code Bounds - Fernando Granha Jeronimo
  179. 179 An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo
  180. 180 Norm Minimization, Invariant Theory, and the Jacobian conjecture - William Cole Franks
  181. 181 Reproducibility in Learning - Jessica Sorrell
  182. 182 Bias vs Low Rank of Polynomials with...Algebraic Geometry - Abhishek Bhowmick
  183. 183 Algorithmizing the Multiplicity Schwartz-Zippel Lemma - Prahladh Harsha
  184. 184 Random algebraic varieties and their applications to hardness of approximation - Bhargav Narayanan
  185. 185 Derandomization and its connections throughout complexity theory - Roei Tell
  186. 186 Derandomization and its connections throughout complexity theory - Liije Chen
  187. 187 Non-Black-Box Derandomization - Roei Tell
  188. 188 Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture - Pravesh Kothari
  189. 189 Association schemes and codes II: Completeness of the hierarchy of high-order...-Leonardo Coregliano
  190. 190 A Proof of the Kahn-Kalai Conjecture - Jinyoung Park
  191. 191 Association schemes and codes I: The Delsarte linear program - Leonardo Coregliano
  192. 192 Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs - Kunal Mittal
  193. 193 A Tutorial on Gaussian Elimination - John C Urschel
  194. 194 Set Chasing, with an application to online shortest path - Sébastien Bubeck
  195. 195 Multi-group fairness, loss minimization and indistinguishability - Parikshit Gopalan
  196. 196 A magnetic interpretation of the nodal count on graphs - Lior Alon
  197. 197 Many Nodal Domains in Random Regular Graphs - Nikhil Srivastava
  198. 198 The absorption method, and an application to an old Ramsey problem - Matija Bucic
  199. 199 Linear cover time is exponentially unlikely - Quentin Dubroff
  200. 200 Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan
  201. 201 Online Bipartite Matching and Adwords - Vijay V. Vazirani
  202. 202 Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan
  203. 203 Multi-group learning via Outcome Indistinguishability - Gal Yona
  204. 204 Hardness of Easy Problems and Fine-Grained Complexity - Or Zamir
  205. 205 The Minimum Formula Size Problem is (ETH) Hard - Rahul Ilango
  206. 206 Introduction to Continuous Combinatorics II: semantic limits - Leonardo Coregliano
  207. 207 The Kakeya Set conjecture over Z mod N for general N - Manik Dhar
  208. 208 Introduction to Continuous Combinatorics I: the semidefinite method of flag... - Leonardo Coregliano
  209. 209 Parallel Repetition for the GHZ Game: A Simpler Proof - Uma Girish
  210. 210 Locally testable codes with constant rate, distance, and locality, Part II - Irit Dinur
  211. 211 Locally testable codes with constant rate, distance, and locality, Part I - Irit Dinur
  212. 212 An Introduction to Determinantal Point Processes - John C Urschel
  213. 213 Sharp matrix concentration inequalities - Ramon van Handel
  214. 214 Recent progress in query complexity I & II Part 2 - Pei Wu
  215. 215 The Complexity of Gradient Descent: CLS = PPAD ∩ PLS - Alexandros Hollender
  216. 216 Recent progress in query complexity I & II - Pei Wu
  217. 217 Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties - Guy Rothblum
  218. 218 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits II : A more... - Sébastien Tavenas
  219. 219 Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits I... - Srikanth Srinivasan
  220. 220 Linear spaces of matrices - Avi Wigderson
  221. 221 Expander Random Walks: A Fourier-Analytic Approach - Gil Cohen
  222. 222 A Complexity-Theoretic Perspective on Fairness - Michael P. Kim
  223. 223 On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture... Part III - Ronen Eldan
  224. 224 On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan
  225. 225 On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan
  226. 226 Privacy as Stability, for Generalization - Katrina Legitt
  227. 227 How difficult is it to certify that a random 3SAT formula is unsatisfiable? - Toniann Pitassi
  228. 228 Pandora's Box with Correlations: Learning and Approximation - Shuchi Chawla
  229. 229 Computational - Statistical gaps and the Group Testing problem - Fotis Iliopoulos
  230. 230 Approximating Max Cut with Subexponential Linear Programs - Tselil Schramm
  231. 231 Amortized circuit complexity, formal complexity measures, and catalytic algorithms - Jeroen Zuiddam
  232. 232 The abstract chromatic number - Leonardo Nagami Coregliano
  233. 233 Polynomial systems and mixed volumes - Ricky I Liu
  234. 234 Random k-out subgraphs - Or Zamir
  235. 235 Strong refutation of semi-random Boolean CSPs - Venkatesan Guruswami
  236. 236 Solving Laplacian Systems of Directed Graphs - John Peebles
  237. 237 Rainbow structures, Latin squares & graph decompositions - Benny Sudakov
  238. 238 Introduction to Laplacian Linear Systems for Undirected Graphs - John Peebles
  239. 239 Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expan - Zongchen Chen
  240. 240 High dimensional expanders - Part 2 - Shai Evra
  241. 241 Monotone Arithmetic Circuit Lower Bounds Via Communication Complexity - Arkadev Chattopadhyay
  242. 242 High dimensional expanders - Shai Evra
  243. 243 Total Functions in the Polynomial Hierarchy - Robert Kleinberg
  244. 244 Log-concave polynomials in theory and applications - Part 2 - Cynthia Vinzant
  245. 245 Graph Density Inequalities, Sums of Squares and Tropicalization - Annie Raymond
  246. 246 Log-concave polynomials in theory and applications - Cynthia Vinzant
  247. 247 An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games... - Andrew Drucker
  248. 248 High Dimensional Expanders and Ramanujan Complexes - Alexander Lubotzky
  249. 249 Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning - Sumegha Garg
  250. 250 Getting the most from our data - Paul Valiant
  251. 251 Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity - Mary Wootters
  252. 252 Factorization through L2, Rounding and Duality Part 2 - Vijay Bhattiprolu
  253. 253 New isoperimetric inequalities for convex bodies - Amir Yehudayoff
  254. 254 Factorization through L2, Rounding and Duality - Vijay Bhattiprolu
  255. 255 Indistinguishability Obfuscation from Well-Founded Assumptions - Huijia (Rachel) Lin
  256. 256 Associativity testing - Ben Green
  257. 257 Anti-concentration and the Gap-Hamming problem - Anup Rao
  258. 258 On the extension complexity of random polytopes - Lisa Sauermann
  259. 259 The threshold for the square of a Hamilton cycleJinyoung Park
  260. 260 A Parallel Repetition Theorem for the GHZ Game - Justin Holmgren
  261. 261 Arithmetic progressions and spectral structure - Thomas Bloom
  262. 262 Explicit near-fully X-Ramanujan graphs - Xinyu Wu
  263. 263 Splitting Necklaces: Existence, Hardness and ApproximationNoga Alon
  264. 264 An introductory survey on expanders and their applications - Avi Wigderson
  265. 265 Convex Set Disjointness, Distributed Learning of Halfspaces, and Linear Programming - Shay Moran
  266. 266 Using discrepancy theory to improve the design of randomized controlled trials - Daniel Spielman
  267. 267 Cutting Planes Proofs of Tseitin and Random Formulas - Noah Fleming
  268. 268 Local Statistics, Semidefinite Programming, and Community Detection - Prasad Raghavendra
  269. 269 A Framework for Quadratic Form Maximization over Convex Sets -Vijay Bhattiprolu
  270. 270 Graph and Hypergraph Sparsification - Luca Trevisan
  271. 271 Geodesically Convex Optimization (or, can we prove P!=NP using gradient descent) - Avi Wigderson
  272. 272 Structure vs Randomness in Complexity Theory - Rahul Santhanam
  273. 273 Legal Theorems of Privacy - Kobbi Nissim
  274. 274 Primality testing - Andrey Kupavskii
  275. 275 Borrowing memory that's being used: catalytic approaches to the Tree Evaluation Problem - James Cook
  276. 276 High dimensional expansion and agreement testing - Irit Dinur
  277. 277 CSPs with Global Modular Constraints: Algorithms and Hardness via... - Sivakanth Gopi
  278. 278 High dimensional expanders - Part 2 - Irit Dinur
  279. 279 Sharp Thresholds and Extremal Combinatorics - Dor Minzer
  280. 280 Feature purification: How adversarial training can perform robust deep learning - Yuanzhi Li
  281. 281 Introduction to high dimensional expanders - Irit Dinur
  282. 282 Learning from Censored and Dependent Data - Constantinos Daskalakis
  283. 283 An introduction to Boolean Function Analysis - Dor Minzer
  284. 284 An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games... - Zhao Song
  285. 285 Spectral Independence in High-dimensional Expanders and Applications... - Kuikui Liu
  286. 286 Is the variety of singular tuples of matrices a null cone? - Viswambhara Makam
  287. 287 Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
  288. 288 An invitation to invariant theory - Viswambhara Makam
  289. 289 Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere
  290. 290 Paths and cycles in expanders - Michael Krivelevich
  291. 291 Explicit rigid matrices in P^NP via rectangular PCPs - Prahladh Harsha
  292. 292 Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory -Robert Robere
  293. 293 MIP* = RE - Henry Yuen
  294. 294 Equality Alone Does not Simulate Randomness- Marc Vinyals
  295. 295 Thresholds Versus Fractional Expectation-Thresholds - Keith Frankston
  296. 296 Graph Sparsification via Short Cycle Decomposition - Sushant Sachdeva
  297. 297 Regularity lemma and its applications Part I - Fan Wei
  298. 298 Rainbow fractional matchings - Ron Holzman
  299. 299 Constraint Satisfaction Problems and Probabilistic Combinatorics II - Fotios Illiopoulos
  300. 300 Lifting small locally testable codes (LTCs) to large LTCs via HDXs - Prahladh Harsha
  301. 301 Constraint Satisfaction Problems and Probabilistic Combinatorics I - Fotios Illiopoulos
  302. 302 An isoperimetric inequality for the Hamming cube and some consequences - Jinyoung Park
  303. 303 Extremal set theory II - Andrey Kupavskii
  304. 304 Extremal set theory - Andrey Kupavskii
  305. 305 Sparse matrices in sparse analysis - Anna Gilbert
  306. 306 Furstenberg sets in finite fields - Zeev Dvir
  307. 307 Towards a theory of non-commutative optimization...… -Rafael Oliveira
  308. 308 Learning arithmetic circuits in the average case via lower bounds - Ankit Garg
  309. 309 Asymptotic spectra and Applications II - Jeroen Zuiddam
  310. 310 Choiceless Polynomial Time - Ben Rossman
  311. 311 On the possibility of an instance-based complexity theory - Boaz Barak
  312. 312 Collective Coin-Flipping Protocols and Influences of Coalitions - Hamed Hatami
  313. 313 Fooling polytopes - Li-Yang Tan
  314. 314 Factors of sparse polynomials: structural results and some algorithms - Shubhangi Saraf
  315. 315 On the Approximation Resistance of Balanced Linear Threshold Functions - Aaron Potechin
  316. 316 A Brief Tour of Proof Complexity: Lower Bounds and Open Problems - Toniann Pitassi
  317. 317 An Application of the Universality Theorem for Tverberg Partitions - Imre Barany
  318. 318 Halting problems for sandpiles and abelian networks - Lionel Levine
  319. 319 Near log-convexity of measured heat in (discrete) time and consequences - Mert Sağlam
  320. 320 Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes - Swastik Kopparty
  321. 321 Strongly log concave polynomials...Bases of Matroids - Shayan Oveis Gharan
  322. 322 Lorentzian Polynomials - June Huh
  323. 323 Why can't we prove tensor rank and Waring rank lower bounds? - Visu Makam
  324. 324 Non-commutative rank - Visu Makam
  325. 325 Near-Optimal Strong Dispersers - Dean Doron
  326. 326 A Regularity Lemma with Modifications - Guy Moshkovitz
  327. 327 PCP and Delegating Computation: A Love Story - Yael Tauman Kalai
  328. 328 New Results on Projections - Guy Moshkovitz
  329. 329 An invitation to tensor networks - Michael Walter
  330. 330 A matrix expander Chernoff bound - Ankit Garg
  331. 331 Monotone Circuit Lower Bounds from Resolution - Mika Goos
  332. 332 Classical Verification of Quantum Computations - Urmila Mahadev
  333. 333 Introduction to Query-to-Communication Lifting - Mika Goos
  334. 334 The GM-MDS conjecture - Shachar Lovett
  335. 335 Sunflowers and friends - Shachar Lovett
  336. 336 On the NP-hardness of 2-to-2 Games - Dor Minzer
  337. 337 X-Ramanujan graphs: ex uno plures - Ryan O'Donnell
  338. 338 2-universality of random graphs - Gal Kronenberg
  339. 339 Small-Set Expansion on the Grassmann Graph - Dor Minzer
  340. 340 Approximating the edit distance to within a constant factor in truly subquadratic time - Mike Saks
  341. 341 Asymptotic spectra and their applications II - Jeroen Zuiddam
  342. 342 Breaking the Circuit-Size Barrier in Secret Sharing - Vinod Vaikuntanathan
  343. 343 Tensor rank - Avi Wigderson
  344. 344 Asymptotic spectra and their applications I - Jeroen Zuiddam
  345. 345 Oracle Separation of Quantum Polynomial time and the Polynomial Hierarchy - Avishay Tal
  346. 346 Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem - Ehud Friedgut
  347. 347 A simple proof of a reverse Minkowski inequality - Noah Stephens-Davidowitz
  348. 348 Sums of Squares Over k-Subset Hypercubes - Annie Raymond
  349. 349 Explicit Binary Tree Codes with Polylogarithmic Size Alphabet - Gil Cohen
  350. 350 Circuit Lower Bounds for Nondeterministic Quasi-Polytime... - Cody Murray
  351. 351 Operator Scaling via Geodesically Convex Optimization, Invariant... (Continued) - Yuanzhi Li
  352. 352 Operator Scaling via Geodesically Convex Optimization, Invariant Theory... - Yuanzhi Li
  353. 353 Abstract Convexity, Weak Epsilon-Nets, and Radon Number - Shay Moran
  354. 354 Boolean function analysis: beyond the Boolean cube (continued) - Yuval Filmus
  355. 355 Boolean function analysis: beyond the Boolean cube - Yuval Filums
  356. 356 On the Communication Complexity of Classification Problems - Roi Livni
  357. 357 A Tight Bound for Hypergraph Regularity - Guy Moshkovitz
  358. 358 Some closure results for polynomial factorization - Mrinal Kumar
  359. 359 Nonlinear dimensionality reduction for faster kernel methods in machine learning - Christopher Musco
  360. 360 Outlier-Robust Estimation via Sum-of-Squares - Pravesh Kothari
  361. 361 Locally Repairable Codes, Storage Capacity and Index Coding - Arya Mazumdar
  362. 362 Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound II - Amnon Ta-Shma
  363. 363 Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound - Amnon Ta-Shma
  364. 364 A Constant-factor Approximation Algorithm for the Asymmetric Traveling Sale...- Ola Svensson
  365. 365 The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson
  366. 366 A PSPACE construction of a hitting set for the closure of small algebraic circuits - Amir Shpilka
  367. 367 Recent advances in high dimensional robust statistics - Daniel Kane
  368. 368 Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei) - Ian Mertz
  369. 369 General strong polarization - Madhu Sudan
  370. 370 Geometric complexity theory from a combinatorial viewpoint - Greta Panova
  371. 371 Locally testable and locally correctable codes approaching the GV bound - Shubhangi Saraf
  372. 372 A practical guide to deep learning - Richard Zemel
  373. 373 Learning models: connections between boosting...and regularity II - Russell Impagliazzo
  374. 374 Learning models: connections between boosting...and regularity I - Russell Impagliazzo
  375. 375 Pseudorandom generators for unordered branching programs - Eshan Chattopadhyay
  376. 376 Language edit distance, (min,+)(min,+)-matrix multiplication & beyond - Barna Saha
  377. 377 Cap-sets in (Fq)n(Fq)n and related problems - Zeev Dvir
  378. 378 Fooling intersections of low-weight halfspaces - Rocco Servedio
  379. 379 On the strength of comparison queries - Shay Moran
  380. 380 A nearly optimal lower bound on the approximate degree of AC00- Mark Bun
  381. 381 Structural aspects of the null-cone problem in invariant theory - Ankit Garg
  382. 382 Barriers for rank methods in arithmetic complexity - Rafael Oliveira
  383. 383 Crossing the logarithmic barrier for dynamic boolean data structure lower bounds - Omri Weinstein
  384. 384 Lifting theorems in communication complexity and applications - Toniann Pitassi
  385. 385 Rigorous RG: a provably efficient and possibly practical algorithm for... - Umesh Vazirani
  386. 386 The Complexity of the Non-commutative Determinant - Srikanth Srinivasan
  387. 387 Small-Bias Sets - Amir Yehudayoff
  388. 388 Existence of Small Families of t-wise Independent Permutations... - Shachar Lovett
  389. 389 Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress - Michael Forbes
  390. 390 Sparsity Lower Bounds for Dimensionality Reducing Maps - Jelani Nelson
  391. 391 Small set expander flows - Ali Kemal Sinop
  392. 392 Toward Better Formula Lower Bounds: An Information Complexity Approach... - Or Meir
  393. 393 A solution to Weaver's KS2KS2 - Adam Marcus
  394. 394 Polynomial Bounds for the Grid-Minor Theorem - Julia Chuzhoy
  395. 395 True Randomness: Its Origin and Expansion - Yaoyun Shi
  396. 396 Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression - Timothy Riley
  397. 397 Strong contraction and influences in tail spaces - Elchanan Mossel
  398. 398 Chernoff bounds for expander walks - Christopher Beck
  399. 399 Computing a categorical Gromov-Witten invariant - Andrei Căldăraru
  400. 400 Bounds on roots of polynomials (and applications) - Adam Marcus
  401. 401 Efficient empirical revenue maximization in single... - Yannai Gonczarowski
  402. 402 Mirror symmetry for moduli of flat bundles and non-abelian Hodge theory - Tony Pantev
  403. 403 Noncommutative probability for computer scientists - Adam Marcus
  404. 404 In pursuit of obfuscation - Allison Bishop
  405. 405 A time-space lower bound for a large class of learning problems - Ran Raz
  406. 406 Applications of monotone constraint satisfaction - Robert Robere
  407. 407 Approximate counting and the Lovasz local lemma - Ankur Moitra
  408. 408 Indistinguishability obfuscation from...to jumping pigs - Nir Bitansky
  409. 409 On the cryptographic hardness of finding a Nash equilibrium - Nir Bitansky
  410. 410 Interactive coding with...communication blowup - Yael Kalai
  411. 411 Structural and computational aspects of Brascamp-Lieb inequalities - Avi Wigderson
  412. 412 New insights on the (non)-hardness of circuit minimization and related problems - Eric Allender
  413. 413 A unified duality-based approach to Bayesian mechanism design - Matt Weinberg
  414. 414 A unified duality-based approach to Bayesian mechanism design - Matt Weinberg
  415. 415 Nearest neighbor search for general symmetric norms via embeddings... - Ilya Razenshteyn
  416. 416 Strongly Refuting Random CSPs below the spectral threshold - Prasad Raghavendra
  417. 417 Sketching and embedding are equivalent for norms - Alex Andoni
  418. 418 Quantifying tradeoffs between fairness and accuracy in online learning - Aaron Roth
  419. 419 Robust sensitivity - Shachar Lovett
  420. 420 Active learning with "simple" membership queries - Shachar Lovett
  421. 421 The polynomial method and the cap set problem - Jordan Ellenberg
  422. 422 Sum of squares lower bounds for refuting any CSP - Pravesh Kothari
  423. 423 On gradient complexity of measures on the discrete cube - Ronen Eldan
  424. 424 Approximate constraint satisfaction requires sub-exponential size linear programs - Pravesh Kothari
  425. 425 On the number of ordinary lines determined by sets in complex space - Shubhangi Saraf
  426. 426 Combinatorial rigidity of graphs embedded in R2 - Orit Raz
  427. 427 Stochastic block models and probabilistic reductions - Emmanuel Abbe
  428. 428 Theory of accelerated methods - Zeyuan Allen-Zhu
  429. 429 On the effect of randomness on planted 3-coloring models - Uri Feige
  430. 430 Non-malleable extractors for constant depth circuits, and affine functions - Eshan Chattopadhyay
  431. 431 Settling the complexity of computing approximate two-player Nash equilibria - Nash equilibria
  432. 432 Sum of squares, quantum entanglement, and log rank - David Steurer
  433. 433 On the query complexity of Boolean monotonicity testing - Xi Chen
  434. 434 Real rooted polynomials and multivariate extensions - Adam Marcus
  435. 435 Brains are better computers than computers - Eyal Wigderson
  436. 436 Happy Days - Gil Kalai joint with Einat Wigderson
  437. 437 Algebraic geometric codes and their applications - Gil Cohen
  438. 438 Fourier tails for Boolean functions and their applications - Avishay Tal
  439. 439 Reed-Muller codes for random erasures and errors - Amir Shpilka
  440. 440 A characterization of functions with vanishing averages over products of disjoint sets - Hatami
  441. 441 An average-case depth hierarchy theorem for Boolean - Li-Yang Tan
  442. 442 A local central limit theorem for triangles in a random graph - Swastik Kopparty
  443. 443 The Resolution proof system - Avi Wigderson
  444. 444 Polynomial-time tensor decompositions via sum-of-squares - Tengyu Ma
  445. 445 Proof complexity - an introduction - Avi Wigderson
  446. 446 Fast learning requires good memory - Ran Raz
  447. 447 Graph isomorphism in quasipolynomial time II - László Babai
  448. 448 Graph isomorphism in quasipolynomial time - László Babai
  449. 449 Minkowski sums, mixed faces and combinatorial isoperimetry - Adiparsito
  450. 450 The deterministic communication complexity of approximate fixed point - Weinstein
  451. 451 The singularity of symbolic matrices (Pt.2) - Avi Wigderson
  452. 452 Bipartite perfect matching is in quasi-NC - Fenner
  453. 453 Constant-round interactive-proofs for delegating computations (continued) - Rothblum
  454. 454 Constant-round interactive-proofs for delegating computations - Rothblum
  455. 455 Proof Complexity Lower Bounds from Algebraic Circuit Complexity - Forbes
  456. 456 Anti-concentration: results and applications - Nguyen
  457. 457 Ramanujan Coverings of Graphs - Doron Puder
  458. 458 Rigidity of random Toeplitz matrices with an application to depth three circuits -Tal
  459. 459 Lower bounds on the size of semidefinite programming relaxations - Steurer
  460. 460 General systems of linear forms: equidistribution and true complexity - Pooya Hatami
  461. 461 Advances on Ramsey numbers - Jacob Fox
  462. 462 Cohomology for computer science - Alex Lubotzky
  463. 463 Cutting plane method: A faster algorithm for many (combinatorial) optimization problems - Lee
  464. 464 Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II - Cohen
  465. 465 Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I - Cohen
  466. 466 Algorithmic proof of the Lovasz Local Lemma via resampling oracles -Vondrak
  467. 467 CSDM - Noga Alon - October 13, 2015
  468. 468 CSDM - Rafael Oliveira - October 12, 2015
  469. 469 CSDM - Chaim Even Zohar - October 6, 2015
  470. 470 CSDM - Elad Hazan - October 5, 2015
  471. 471 CSDM - Choongbum Lee - September 28, 2015
  472. 472 CSDM - Eshan Chattopadhyay - September 22, 2015
  473. 473 CSDM - Eshan Chattopadhyay - Septemeber 21, 2015

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free
Someone learning on their laptop while sitting on the floor.