Computer Science and Discrete Mathematics

On Turán Numbers of hyper Graphs - Maya Sankar
Trickle-down Theorems for High-dimensional Expanders via Lorentzian Polynomials - Jonathan Leake
Linial Meshulam Complexes 2 - Michael Chapman
How Low Can We Go? Exploring Minimal Assumptions in Quantum Cryptography - Dakshita Khurana
Linial--Meshulam Complexes - Michael Chapman
Why Language Models Hallucinate - Adam Kalai
Local List Decoding from HDX II - Yotam Dikstein
Breaking the n‾√ Barrier: New Parallel Algorithms for Finding a Matroid Basis - Aaron Putterman
Hard Functions from on High: Local List Decoding from HDX - Max Hopkins
On Beck-Fiala and Komlós Conjectures - Nikhil Bansal
No Exponential Quantum Speedup for SIS^inf Anymore - Kewen Wu
New Approach to Matrix Perturbation: Beyond the Worst-Case Analysis - Van H. Vu
Aldous-type Spectral Gaps in Unitary Groups, Part II - Doron Puder
Explicit Lossless Vertex Expanders - Rachel Zhang
Aldous-type Spectral Gaps in Unitary Groups, Part I - Doron Puder
From Classical to Quantum Circuit Complexity: The Tale of (Q)AC0 - Francisca Vasconcelos
From PCPs to Parallel PCPs: Hardness of Approximation in Parameterized Complexity - Karthik C. S.
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss - Andrej Bogdanov
Algorithms for Solving Random and Semirandom Planted Constraint Satisfaction Problems- Peter Manohar
Stronger Cell Probe Lower Bounds via Local PRGs - Oliver Korten
Approximate Covers and Cocycle Expansion - Irit Dveer Dinur
Asymptotic Spectrum and Approximation Approaches to Direct-sum Problems - Jeroen Zuiddam
Simulating Time With Square-Root Space (And With Details) - Ryan Williams
Balancing Extensions in Posets of Large Width - Maxwell Aires
Combinatorial and Geometric Challenges in PAC Learning with Partial Concepts - Shay Moran
Upper Bounds for Multicolour Ramsey Numbers - Marius Tiba
Why Extension-Based Proofs Fail - Faith Ellen
The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem - Guy Blanc
Coboundary Expansion Inside Chevalley High-Dimensional Expanders - Ryan O'Donnell
Language Generation in the Limit - Jon Kleinberg
Cosystolic Expansion - Irit Dveer Dinur
Locally Testable Codes with the Multiplication Property from High-dimensional Expanders - Siqi Liu
Improved Private Information Retrieval Schemes from Matching Vectors and Deriva...- Swastik Kopparty
Sylvester, Gallai and Friends: Discrete Geometry Meets Computational Complexity - Avi Wigderson
Efficiency, Resilience, and Artificial Intelligence - Moshe Y. Vardi
Connections Between Matrix Spaces and Graphs - Youming Qiao
A Zero-Knowledge PCP Theorem - Nicholas Spooner
On the Complexity of Isomorphism Problems for Tensors, Groups, Polynomials, and...- Youming Qiao
Simulating Time With Square-Root Space - Ryan Williams
A Theory of Generalized Boosting - Nataly Brukhim
Improved Fault-Tolerant Non-Clifford Gates (or: How to Multiply Quantumly) - Louis Golowich
Independent Sets in Random Cayley Graphs - Huy Tuan Pham
Finding Regular Subgraphs - Richard Montgomery
“Sharp” Selector Processes - Huy Tuan Pham
Monochromatic Sums and Products over the Rationals - Maria-Romina Ivan
The Error Resilience of Binary Codes with Interaction - Gillat Kol
Lower Bounds for Local Codes from Induced Subgraphs of Cayley Graphs - Peter Manohar
Low-Depth Algebraic Circuit Lower Bounds Over Any Field - Michael A. Forbes
Spectral Algorithms from Induced Subgraphs of Cayley Graphs - Peter Manohar
On Approximability of Satisfiable Constraint Satisfaction Problems & Applications - Amey Bhangale
Explicit Codes Approaching the Generalized Singleton Bound Using Expanders - Shashank Srivastava
Random Matrices From GLn(q) Sampled by Words - Doron Puder
Structure and Randomness for Finite-field Polynomials are (almost) Equivalent - Guy Moshkovitz
Problems in Extremal Combinatorics and Connections with Multiparty Communication... - Zander Kelley
Grid-norm Regularity for Somewhat Dense Graphs, and Some Applications - Zander Kelley
Efficient Batch Verification: Recent Progress and Challenges - Ron Rothblum
A Review of the Notion of Graph Rigidity and Some Recent Developments - Orit Raz
QMA vs. QCMA and Pseudorandomness - Henry Yuen
Simple High Dimensional Expanders from Cayley Graphs - Yotam Dikstein
Dot-Product Proofs - Yuval Ishai
Quadratic Stability of the Brunn-Minkowski Inequality - Peter van Hintum
Induced Subgraphs and Pathwidth - Maria Chudnovsky
Linear Stability of the Brunn-Minkowski Inequality - Peter van Hintum
Quantum Locally Testable Codes and Codes with Transversal Gates - David (Ting-Chun) Lin
Fault Tolerant Routing Protocols on High-Dimensional Expanders - Mitali Bafna
Quasi-Linear Size PCPs with Small Soundness from High-Dimensional Expanders - Mitali Bafna
Sheaves on Graphs, the Hanna Neumann Conjecture, and My Debt to Number Theory and... - Joel Friedman
When and How are (promise) Constraint Satisfaction Problems Efficiently Sol...- Venkatesan Guruswami
Analytic Insights into the Zig-Zag Product and Its Friends: Part II - Gil Cohen
Subgroup Tests and the Aldous--Lyons Conjecture - Michael Chapman
Analytic Insights into the Zig-Zag Product and Its Friends: Part I - Gil Cohen
Subgroup Tests and Tailored Non-local Games - Michael Chapman
A New Approach to Strong Convergence - Ramon Van Handel
Sorting Using Partial Information - Robert Tarjan
Concentration on HDX: Derandomization Beyond Chernoff - Max Hopkins
An Improved Line-Point Low-Degree Test - Prahladh Harsha
Resolution of the Kohayakawa--Kreuter Conjecture - Raphael Steiner
Quantum Mechanics, Semidefinite Programming, and Graph Invariants - Matthew Hastings
Rounding Large Independent Sets on Expanders - Tim Hsieh
Incidence Bounds via Extremal Graph Theory - Istvan Tomon
Triangulated Surfaces in Moduli Space - Sahana Vasudevan
Lower Bounds for Set-Multilinear Branching Programs - Shubhangi Saraf
Random Cayley Graphs From a Combinatorial Perspective - Huy Tuan Pham
Additive Combinatorics Without Groups - Huy Tuan Pham
Parallel Repetition for 3-Player XOR Games - Yang Liu
Graphs, CSPs and Codes - Madhu Sudan
Avi Wigderson, 2023 Turing Award Laureate, Q&A with David Nirenberg | Institute for Advanced Study
The Method of Hypergraph Containers - Wojciech Samotij
Polynomial Capacity and its Applications: To TSP and Beyond - Jonathan Leake
New Derandomized Agreement Testers - Yotam Dikstein
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries - Huacheng Yu
Sparsification of Gaussian Processes - Anindya De
Locally Consistent Decomposition of Strings with Applications to Edit Distance Ske...- Michal Koucký
Explicit SoS Lower Bounds from High Dimensional Expanders - Max Hopkins
Computing Greatest Common Divisors of Polynomials in Parallel - Robert Andrews
Stability and Learning in Strategic Games - Éva Tardos
Analyzing the Max Entropy Algorithm for TSP - Nathan Klein
Reconstruction on Trees and Hypertrees - Yuzhou Gu
Advances in Parallel and Private Stochastic Optimization from Ball Acceleration - Kevin Tian
An Exponential Lower bound on Three Query, Linear Locally Correctable Codes - Pravesh Kothari
Expanding the Reach of P not equal to NP: the Minimum Circuit Size Problem with a... - Rahul Ilango
Omniprediction and Multigroup Fairness - Parikshit Gopalan
The Tree Evaluation Problem: Context and Recent Results - Ian Mertz
Online Discrepancy Minimization - Victor Reis
Marton's Conjecture, aka the Polynomial Freiman--Ruzsa conjecture - Frederick Manners
Online Omniprediction - Sumegha Garg
Coboundary and Cosystolic Expansion - Siqi Liu
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition - Or Meir
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting- William Hoza
Recent Progress on Derandomizing Space-Bounded Computation - William Hoza
Sparsifying Sums of Functions - Yang Liu
Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications - Nitya Mani
The Iterative Win-Win Method, and Explicit Constructions (without) Using It - Hanlin Ren
A Definition of Spectral Gap for Nonreversible Markov Chains - Sourav Chatterjee
High Dimensional Expanders and Sparsifications of the Johnson Graph - Yotam Dikstein
A High Dimensional Goldreich-Levin Theorem - Silas Richelson
An Optimization Perspective on Log-concave Sampling - Sinho Chewi
A Proof of the RM Code Capacity Conjecture - Emmanuel Abbé
Extending Generalization Theory towards addressing modern challenges in Machine Learning- Shay Moran
A Combinatorial Characterization of Minimax in Win/Lose Games - Shay Moran
Shrinkage Under Random Restrictions - Robert Andrews
Private Optimization and Statistical Physics: Low-Rank Matrix Approximation - Nisheeth Vishnoi
Learning from Dynamics - Ankur Moitra
The Diffraction Limit and Extremal Functions - Ankur Moitra
Optimization, Complexity and Math (or, can we prove P!=NP by gradient descent?) - Avi Wigderson
Using Expanders for Fast Graph Algorithms - Thatchaphol Saranurak
Graph Vertex Expansion - Theo McKenzie
Fitting Various Metrics with Minimum Disagreements - Euiwoong Lee
A Constant Lower Bound for Frankl's Union-Closed Sets Conjecture - Justin Gilmer
A Unified Approach to Discrepancy Minimization - Nikhil Bansal
Approximating Iterated Multiplication of Stochastic Matrices in Small Space - Dean Doron
Existence of Subspace Designs - Ashwin Sah
Unit and Distinct Distances in Typical Norms - Noga Alon
Updates on the Lipschitz Extension Problem - Assaf Naor
Quantum Error Correction, Systolic Geometry, and Probabilistic Embeddings - Elia Portnoy
Hausdorff Dimension Analogues of the Elekes - Ronyai Theorem and Related Problems - Orit Raz
Common Linear Patterns Are Rare - Nina Kamčev
The Lens of Abelian Embeddings - Dor Minzer
Strong Bounds for 3-Progressions: In-Depth - Zander Kelley
Extremal Problems for Uniformly Dense Hypergraphs - Mathias Schacht
Strong Bounds for 3-Progressions - Raghu Meka
Why Can’t We Classically Describe Quantum Systems? - Chinmay Nirkhe
Recent Progress in Randomness Extraction - Eshan Chattopadhyay
Two (More) Algorithms for Set Cover - Anupam Gupta
From Robust Sublinear Expanders to Additive Number Theory via Rainbow Cycles - Matija Bucic
Rainbow Matchings in Hypergraphs - Cosmin Pohoata
Efficient Verification of Computation on Untrusted Platforms - Yael Kalai
Overview and Recent Results in Combinatorial Auctions - Matt Weinberg
Smooth Coverings of Space - Oded Regev
On Matrix Multiplication and Polynomial Identity Testing - Robert Andrews
Locally Decodable Codes - Zeev Dvir
Non-measurability of the inverse theorem for the Gowers norms - Terence Tao
A Characterization of Multiclass Learnability - Nataly Brukhim
Optimization-Friendly Generic Mechanisms Without Money - Mark Braverman
Online List Labeling: Breaking the log2 n Barrier - Nicole Wein
Optimal Weak to Strong Learning - Kasper Green Larsen
Superfast Derandomization of Interactive Proof Systems - Roei Tell
The Hypergraph Container Method, Partition Containers, and Algorithmic Applications - Or Zamir
Algorithmic Stochastic Localization for the Sherrington-Kirkpatrick Model - Mark Sellke
The Polynomial Method in Communication Complexity - Pei Wu
Strong XOR Lemma for Communication with Bounded Rounds - Huacheng Yu
Additive combinatorics through the lens of communication complexity - Toniann Pitassi
Communication and Query Complexity of Bipartite Perfect Matching - Yuval Efron
Introduction to Natural Quasirandomness: Unique Colorability and Order-ability - Leonardo Coregliano
Smoothed Complexity of Local Max-Cut with Two Flips - Xi Chen
Average-Case Computational Complexity of Tensor Decomposition - Alex Wein
Almost Linear Time Algorithms for Max-flow and More - Sushant Sachdeva
The Optimal Error Resilience of Interactive Communication over the Binary Alphabet - Rachel Zhang
Is your distribution in shape? - Ronitt Rubinfeld
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Ampli... - Fernando Granha Jeronimo
Relative rank and regularity - Tamar Ziegler
Robust sublinear expanders, and an application towards the Erdos-Gallai conjecture - Matija Bucic
Making Proofs More Constructive, and Algorithms Less Random - Oliver Korten
Graphs as geometric objects - Nathan Linial
On Approximability of CSPs on Satisfiable Instances - Subhash Khot
Exact algorithms for graph coloring - Or Zamir
List decoding with double samplers - Inbal Livni-Navon
An Introduction to Binary Code Bounds - Fernando Granha Jeronimo
An Introduction to Lifted Expander Graphs - Fernando Granha Jeronimo
Norm Minimization, Invariant Theory, and the Jacobian conjecture - William Cole Franks
Reproducibility in Learning - Jessica Sorrell
Bias vs Low Rank of Polynomials with...Algebraic Geometry - Abhishek Bhowmick
Algorithmizing the Multiplicity Schwartz-Zippel Lemma - Prahladh Harsha
Random algebraic varieties and their applications to hardness of approximation - Bhargav Narayanan
Derandomization and its connections throughout complexity theory - Roei Tell
Derandomization and its connections throughout complexity theory - Liije Chen
Non-Black-Box Derandomization - Roei Tell
Refuting Smoothed k-SAT Formulas and a Proof of Feige's Conjecture - Pravesh Kothari
Association schemes and codes II: Completeness of the hierarchy of high-order...-Leonardo Coregliano
A Proof of the Kahn-Kalai Conjecture - Jinyoung Park
Association schemes and codes I: The Delsarte linear program - Leonardo Coregliano
Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs - Kunal Mittal
A Tutorial on Gaussian Elimination - John C Urschel
Set Chasing, with an application to online shortest path - Sébastien Bubeck
Multi-group fairness, loss minimization and indistinguishability - Parikshit Gopalan
A magnetic interpretation of the nodal count on graphs - Lior Alon
Many Nodal Domains in Random Regular Graphs - Nikhil Srivastava
The absorption method, and an application to an old Ramsey problem - Matija Bucic
Linear cover time is exponentially unlikely - Quentin Dubroff
Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan
Online Bipartite Matching and Adwords - Vijay V. Vazirani
Localization schemes: A framework for proving mixing bounds for Markov chains - Ronen Eldan
Multi-group learning via Outcome Indistinguishability - Gal Yona
Hardness of Easy Problems and Fine-Grained Complexity - Or Zamir
The Minimum Formula Size Problem is (ETH) Hard - Rahul Ilango
Introduction to Continuous Combinatorics II: semantic limits - Leonardo Coregliano
The Kakeya Set conjecture over Z mod N for general N - Manik Dhar
Introduction to Continuous Combinatorics I: the semidefinite method of flag... - Leonardo Coregliano
Parallel Repetition for the GHZ Game: A Simpler Proof - Uma Girish
Locally testable codes with constant rate, distance, and locality, Part II - Irit Dinur
Locally testable codes with constant rate, distance, and locality, Part I - Irit Dinur
An Introduction to Determinantal Point Processes - John C Urschel
Sharp matrix concentration inequalities - Ramon van Handel
Recent progress in query complexity I & II Part 2 - Pei Wu
The Complexity of Gradient Descent: CLS = PPAD ∩ PLS - Alexandros Hollender
Recent progress in query complexity I & II - Pei Wu
Verifying The Unseen: Interactive Proofs for Label-Invariant Distribution Properties - Guy Rothblum
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits II : A more... - Sébastien Tavenas
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits I... - Srikanth Srinivasan
Linear spaces of matrices - Avi Wigderson
Expander Random Walks: A Fourier-Analytic Approach - Gil Cohen
A Complexity-Theoretic Perspective on Fairness - Michael P. Kim
On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture... Part III - Ronen Eldan
On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan
On Chen’s recent breakthrough on the Kannan-Lovasz-Simonovits conjecture and Bourga... - Ronen Eldan
Privacy as Stability, for Generalization - Katrina Legitt
How difficult is it to certify that a random 3SAT formula is unsatisfiable? - Toniann Pitassi
Pandora's Box with Correlations: Learning and Approximation - Shuchi Chawla
Computational - Statistical gaps and the Group Testing problem - Fotis Iliopoulos
Approximating Max Cut with Subexponential Linear Programs - Tselil Schramm
Amortized circuit complexity, formal complexity measures, and catalytic algorithms - Jeroen Zuiddam
The abstract chromatic number - Leonardo Nagami Coregliano
Polynomial systems and mixed volumes - Ricky I Liu
Random k-out subgraphs - Or Zamir
Strong refutation of semi-random Boolean CSPs - Venkatesan Guruswami
Solving Laplacian Systems of Directed Graphs - John Peebles
Rainbow structures, Latin squares & graph decompositions - Benny Sudakov
Introduction to Laplacian Linear Systems for Undirected Graphs - John Peebles
Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expan - Zongchen Chen
High dimensional expanders - Part 2 - Shai Evra
Monotone Arithmetic Circuit Lower Bounds Via Communication Complexity - Arkadev Chattopadhyay
High dimensional expanders - Shai Evra
Total Functions in the Polynomial Hierarchy - Robert Kleinberg
Log-concave polynomials in theory and applications - Part 2 - Cynthia Vinzant
Graph Density Inequalities, Sums of Squares and Tropicalization - Annie Raymond
Log-concave polynomials in theory and applications - Cynthia Vinzant
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games... - Andrew Drucker
High Dimensional Expanders and Ramanujan Complexes - Alexander Lubotzky
Extractor-based Approach to Proving Memory-Sample Lower Bounds for Learning - Sumegha Garg
Getting the most from our data - Paul Valiant
Thresholds for Random Subspaces, aka, LDPC Codes Achieve List-Decoding Capacity - Mary Wootters
Factorization through L2, Rounding and Duality Part 2 - Vijay Bhattiprolu
New isoperimetric inequalities for convex bodies - Amir Yehudayoff
Factorization through L2, Rounding and Duality - Vijay Bhattiprolu
Indistinguishability Obfuscation from Well-Founded Assumptions - Huijia (Rachel) Lin
Associativity testing - Ben Green
Anti-concentration and the Gap-Hamming problem - Anup Rao
On the extension complexity of random polytopes - Lisa Sauermann
The threshold for the square of a Hamilton cycleJinyoung Park
A Parallel Repetition Theorem for the GHZ Game - Justin Holmgren
Arithmetic progressions and spectral structure - Thomas Bloom
Explicit near-fully X-Ramanujan graphs - Xinyu Wu
Splitting Necklaces: Existence, Hardness and ApproximationNoga Alon
An introductory survey on expanders and their applications - Avi Wigderson
Convex Set Disjointness, Distributed Learning of Halfspaces, and Linear Programming - Shay Moran
Using discrepancy theory to improve the design of randomized controlled trials - Daniel Spielman
Cutting Planes Proofs of Tseitin and Random Formulas - Noah Fleming
Local Statistics, Semidefinite Programming, and Community Detection - Prasad Raghavendra
A Framework for Quadratic Form Maximization over Convex Sets -Vijay Bhattiprolu
Graph and Hypergraph Sparsification - Luca Trevisan
Geodesically Convex Optimization (or, can we prove P!=NP using gradient descent) - Avi Wigderson
Structure vs Randomness in Complexity Theory - Rahul Santhanam
Legal Theorems of Privacy - Kobbi Nissim
Primality testing - Andrey Kupavskii
Borrowing memory that's being used: catalytic approaches to the Tree Evaluation Problem - James Cook
High dimensional expansion and agreement testing - Irit Dinur
CSPs with Global Modular Constraints: Algorithms and Hardness via... - Sivakanth Gopi
High dimensional expanders - Part 2 - Irit Dinur
Sharp Thresholds and Extremal Combinatorics - Dor Minzer
Feature purification: How adversarial training can perform robust deep learning - Yuanzhi Li
Introduction to high dimensional expanders - Irit Dinur
Learning from Censored and Dependent Data - Constantinos Daskalakis
An introduction to Boolean Function Analysis - Dor Minzer
An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games... - Zhao Song
Spectral Independence in High-dimensional Expanders and Applications... - Kuikui Liu
Is the variety of singular tuples of matrices a null cone? - Viswambhara Makam
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization - Lijie Chen
An invitation to invariant theory - Viswambhara Makam
Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory - Robert Robere
Paths and cycles in expanders - Michael Krivelevich
Explicit rigid matrices in P^NP via rectangular PCPs - Prahladh Harsha
Proofs, Circuits, Communication, and Lower Bounds in Complexity Theory -Robert Robere
MIP* = RE - Henry Yuen
Equality Alone Does not Simulate Randomness- Marc Vinyals
Thresholds Versus Fractional Expectation-Thresholds - Keith Frankston
Graph Sparsification via Short Cycle Decomposition - Sushant Sachdeva
Regularity lemma and its applications Part I - Fan Wei
Rainbow fractional matchings - Ron Holzman
Constraint Satisfaction Problems and Probabilistic Combinatorics II - Fotios Illiopoulos
Lifting small locally testable codes (LTCs) to large LTCs via HDXs - Prahladh Harsha
Constraint Satisfaction Problems and Probabilistic Combinatorics I - Fotios Illiopoulos
An isoperimetric inequality for the Hamming cube and some consequences - Jinyoung Park
Extremal set theory II - Andrey Kupavskii
Extremal set theory - Andrey Kupavskii
Sparse matrices in sparse analysis - Anna Gilbert
Furstenberg sets in finite fields - Zeev Dvir
Towards a theory of non-commutative optimization...… -Rafael Oliveira
Learning arithmetic circuits in the average case via lower bounds - Ankit Garg
Asymptotic spectra and Applications II - Jeroen Zuiddam
Choiceless Polynomial Time - Ben Rossman
On the possibility of an instance-based complexity theory - Boaz Barak
Collective Coin-Flipping Protocols and Influences of Coalitions - Hamed Hatami
Fooling polytopes - Li-Yang Tan
Factors of sparse polynomials: structural results and some algorithms - Shubhangi Saraf
On the Approximation Resistance of Balanced Linear Threshold Functions - Aaron Potechin
A Brief Tour of Proof Complexity: Lower Bounds and Open Problems - Toniann Pitassi
An Application of the Universality Theorem for Tverberg Partitions - Imre Barany
Halting problems for sandpiles and abelian networks - Lionel Levine
Near log-convexity of measured heat in (discrete) time and consequences - Mert Sağlam
Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes - Swastik Kopparty
Strongly log concave polynomials...Bases of Matroids - Shayan Oveis Gharan
Lorentzian Polynomials - June Huh
Why can't we prove tensor rank and Waring rank lower bounds? - Visu Makam
Non-commutative rank - Visu Makam
Near-Optimal Strong Dispersers - Dean Doron
A Regularity Lemma with Modifications - Guy Moshkovitz
PCP and Delegating Computation: A Love Story - Yael Tauman Kalai
New Results on Projections - Guy Moshkovitz
An invitation to tensor networks - Michael Walter
A matrix expander Chernoff bound - Ankit Garg
Monotone Circuit Lower Bounds from Resolution - Mika Goos
Classical Verification of Quantum Computations - Urmila Mahadev
Introduction to Query-to-Communication Lifting - Mika Goos
The GM-MDS conjecture - Shachar Lovett
Sunflowers and friends - Shachar Lovett
On the NP-hardness of 2-to-2 Games - Dor Minzer
X-Ramanujan graphs: ex uno plures - Ryan O'Donnell
2-universality of random graphs - Gal Kronenberg
Small-Set Expansion on the Grassmann Graph - Dor Minzer
Approximating the edit distance to within a constant factor in truly subquadratic time - Mike Saks
Asymptotic spectra and their applications II - Jeroen Zuiddam
Breaking the Circuit-Size Barrier in Secret Sharing - Vinod Vaikuntanathan
Tensor rank - Avi Wigderson
Asymptotic spectra and their applications I - Jeroen Zuiddam
Oracle Separation of Quantum Polynomial time and the Polynomial Hierarchy - Avishay Tal
Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem - Ehud Friedgut
A simple proof of a reverse Minkowski inequality - Noah Stephens-Davidowitz
Sums of Squares Over k-Subset Hypercubes - Annie Raymond
Explicit Binary Tree Codes with Polylogarithmic Size Alphabet - Gil Cohen
Circuit Lower Bounds for Nondeterministic Quasi-Polytime... - Cody Murray
Operator Scaling via Geodesically Convex Optimization, Invariant... (Continued) - Yuanzhi Li
Operator Scaling via Geodesically Convex Optimization, Invariant Theory... - Yuanzhi Li
Abstract Convexity, Weak Epsilon-Nets, and Radon Number - Shay Moran
Boolean function analysis: beyond the Boolean cube (continued) - Yuval Filmus
Boolean function analysis: beyond the Boolean cube - Yuval Filums
On the Communication Complexity of Classification Problems - Roi Livni
A Tight Bound for Hypergraph Regularity - Guy Moshkovitz
Some closure results for polynomial factorization - Mrinal Kumar
Nonlinear dimensionality reduction for faster kernel methods in machine learning - Christopher Musco
Outlier-Robust Estimation via Sum-of-Squares - Pravesh Kothari
Locally Repairable Codes, Storage Capacity and Index Coding - Arya Mazumdar
Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound II - Amnon Ta-Shma
Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound - Amnon Ta-Shma
A Constant-factor Approximation Algorithm for the Asymmetric Traveling Sale...- Ola Svensson
The Matching Problem in General Graphs is in Quasi-NC - Ola Svensson
A PSPACE construction of a hitting set for the closure of small algebraic circuits - Amir Shpilka
Recent advances in high dimensional robust statistics - Daniel Kane
Short proofs are hard to find (joint work w/ Toni Pitassi and Hao Wei) - Ian Mertz
General strong polarization - Madhu Sudan
Geometric complexity theory from a combinatorial viewpoint - Greta Panova
Locally testable and locally correctable codes approaching the GV bound - Shubhangi Saraf
A practical guide to deep learning - Richard Zemel
Learning models: connections between boosting...and regularity II - Russell Impagliazzo
Learning models: connections between boosting...and regularity I - Russell Impagliazzo
Pseudorandom generators for unordered branching programs - Eshan Chattopadhyay
Language edit distance, (min,+)(min,+)-matrix multiplication & beyond - Barna Saha
Cap-sets in (Fq)n(Fq)n and related problems - Zeev Dvir
Fooling intersections of low-weight halfspaces - Rocco Servedio
On the strength of comparison queries - Shay Moran
A nearly optimal lower bound on the approximate degree of AC00- Mark Bun
Structural aspects of the null-cone problem in invariant theory - Ankit Garg
Barriers for rank methods in arithmetic complexity - Rafael Oliveira
Crossing the logarithmic barrier for dynamic boolean data structure lower bounds - Omri Weinstein
Lifting theorems in communication complexity and applications - Toniann Pitassi
Rigorous RG: a provably efficient and possibly practical algorithm for... - Umesh Vazirani
The Complexity of the Non-commutative Determinant - Srikanth Srinivasan
Small-Bias Sets - Amir Yehudayoff
Existence of Small Families of t-wise Independent Permutations... - Shachar Lovett
Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Progress - Michael Forbes
Sparsity Lower Bounds for Dimensionality Reducing Maps - Jelani Nelson
Small set expander flows - Ali Kemal Sinop
Toward Better Formula Lower Bounds: An Information Complexity Approach... - Or Meir
A solution to Weaver's KS2KS2 - Adam Marcus
Polynomial Bounds for the Grid-Minor Theorem - Julia Chuzhoy
True Randomness: Its Origin and Expansion - Yaoyun Shi
Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression - Timothy Riley
Strong contraction and influences in tail spaces - Elchanan Mossel
Chernoff bounds for expander walks - Christopher Beck
Computing a categorical Gromov-Witten invariant - Andrei Căldăraru
Bounds on roots of polynomials (and applications) - Adam Marcus
Efficient empirical revenue maximization in single... - Yannai Gonczarowski
Mirror symmetry for moduli of flat bundles and non-abelian Hodge theory - Tony Pantev
Noncommutative probability for computer scientists - Adam Marcus
In pursuit of obfuscation - Allison Bishop
A time-space lower bound for a large class of learning problems - Ran Raz
Applications of monotone constraint satisfaction - Robert Robere
Approximate counting and the Lovasz local lemma - Ankur Moitra
Indistinguishability obfuscation from...to jumping pigs - Nir Bitansky
On the cryptographic hardness of finding a Nash equilibrium - Nir Bitansky
Interactive coding with...communication blowup - Yael Kalai
Structural and computational aspects of Brascamp-Lieb inequalities - Avi Wigderson
New insights on the (non)-hardness of circuit minimization and related problems - Eric Allender
A unified duality-based approach to Bayesian mechanism design - Matt Weinberg
A unified duality-based approach to Bayesian mechanism design - Matt Weinberg
Nearest neighbor search for general symmetric norms via embeddings... - Ilya Razenshteyn
Strongly Refuting Random CSPs below the spectral threshold - Prasad Raghavendra
Sketching and embedding are equivalent for norms - Alex Andoni
Quantifying tradeoffs between fairness and accuracy in online learning - Aaron Roth
Robust sensitivity - Shachar Lovett
Active learning with "simple" membership queries - Shachar Lovett
The polynomial method and the cap set problem - Jordan Ellenberg
Sum of squares lower bounds for refuting any CSP - Pravesh Kothari
On gradient complexity of measures on the discrete cube - Ronen Eldan
Approximate constraint satisfaction requires sub-exponential size linear programs - Pravesh Kothari
On the number of ordinary lines determined by sets in complex space - Shubhangi Saraf
Combinatorial rigidity of graphs embedded in R2 - Orit Raz
Stochastic block models and probabilistic reductions - Emmanuel Abbe
Theory of accelerated methods - Zeyuan Allen-Zhu
On the effect of randomness on planted 3-coloring models - Uri Feige
Non-malleable extractors for constant depth circuits, and affine functions - Eshan Chattopadhyay
Settling the complexity of computing approximate two-player Nash equilibria - Nash equilibria
Sum of squares, quantum entanglement, and log rank - David Steurer
On the query complexity of Boolean monotonicity testing - Xi Chen
Real rooted polynomials and multivariate extensions - Adam Marcus
Brains are better computers than computers - Eyal Wigderson
Happy Days - Gil Kalai joint with Einat Wigderson
Algebraic geometric codes and their applications - Gil Cohen
Fourier tails for Boolean functions and their applications - Avishay Tal
Reed-Muller codes for random erasures and errors - Amir Shpilka
A characterization of functions with vanishing averages over products of disjoint sets - Hatami
An average-case depth hierarchy theorem for Boolean - Li-Yang Tan
A local central limit theorem for triangles in a random graph - Swastik Kopparty
The Resolution proof system - Avi Wigderson
Polynomial-time tensor decompositions via sum-of-squares - Tengyu Ma
Proof complexity - an introduction - Avi Wigderson
Fast learning requires good memory - Ran Raz
Graph isomorphism in quasipolynomial time II - László Babai
Graph isomorphism in quasipolynomial time - László Babai
Minkowski sums, mixed faces and combinatorial isoperimetry - Adiparsito
The deterministic communication complexity of approximate fixed point - Weinstein
The singularity of symbolic matrices (Pt.2) - Avi Wigderson
Bipartite perfect matching is in quasi-NC - Fenner
Constant-round interactive-proofs for delegating computations (continued) - Rothblum
Constant-round interactive-proofs for delegating computations - Rothblum
Proof Complexity Lower Bounds from Algebraic Circuit Complexity - Forbes
Anti-concentration: results and applications - Nguyen
Ramanujan Coverings of Graphs - Doron Puder
Rigidity of random Toeplitz matrices with an application to depth three circuits -Tal
Lower bounds on the size of semidefinite programming relaxations - Steurer
General systems of linear forms: equidistribution and true complexity - Pooya Hatami
Advances on Ramsey numbers - Jacob Fox
Cohomology for computer science - Alex Lubotzky
Cutting plane method: A faster algorithm for many (combinatorial) optimization problems - Lee
Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II - Cohen
Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I - Cohen
Algorithmic proof of the Lovasz Local Lemma via resampling oracles -Vondrak
CSDM - Noga Alon - October 13, 2015
CSDM - Rafael Oliveira - October 12, 2015
CSDM - Chaim Even Zohar - October 6, 2015
CSDM - Elad Hazan - October 5, 2015
CSDM - Choongbum Lee - September 28, 2015
CSDM - Eshan Chattopadhyay - September 22, 2015
CSDM - Eshan Chattopadhyay - Septemeber 21, 2015