|
The Power of Recursive Embeddings for $\ell_p$ Metrics
Robert Krauthgamer, Nir Petruschka, Shay Sapir (Weizmann Institute)
|
|
Group Order is in QCMA
François Le Gall, Harumichi Nishimura, Dhara Thakkar (Nagoya University)
|
|
Maximally Extendable Product Codes are Good Coboundary Expanders
Gleb Kalachev, Pavel Panteleev (Moscow State University)
|
|
Obfuscation of Unitary Quantum Programs
Mi-Ying Huang (University of Southern California), Er-Cheng Tang (University of Washington)
|
|
Solving Linear Inequalities over Convex Sets & its Applications to Cryptography and Hydrodynamics
Saugata Basu, Hamidreza Amini Khorasgani, Hemanta K. Maji (Purdue University), Hai H. Nguyen (ETH Zurich)
|
|
Godel in Cryptography: Effectively Zero Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness
Rahul Ilango (Massachusetts Institute of Technology)
|
|
Average-Distortion Sketching
Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang (University of Pennsylvania)
|
|
Learning quantum Gibbs states locally and efficiently
Chi-Fang Chen (UC Berkeley & MIT), Anurag Anshu, Quynh T. Nguyen (Harvard University)
|
|
Computational-Statistical Tradeoffs from NP-hardness
Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan (Stanford University)
|
|
Overcomplete Tensor Decomposition via Koszul-Young Flattenings
Pravesh K Kothari (Princeton University), Ankur Moitra (Massachusetts Institute of Technology), Alexander S Wein (UC Davis)
|
|
Faster Mixing of the Jerrum-Sinclair Chain
Xiaoyu Chen (Nanjing University), Weiming Feng (The University of Hong Kong), Zhe Ju, Tianshun Miao, Yitong Yin, Xinyuan Zhang (Nanjing University)
|
|
The Proof Analysis Problem
Noel Arteche (Lund University & University of Copenhagen), Albert Atserias (Universitat Politècnica de Catalunya), Susanna F. de Rezende (Lund University), Erfan Khaniki (University of Oxford)
|
|
Embeddings into Similarity Measures for Nearest Neighbor Search
Alexandr Andoni (Columbia University, USA), Negev Shekel Nosatzki (Columbia University)
|
|
Quasipolynomial bounds for the corners theorem
Michael Jaber (University of Texas, Austin), Yang P. Liu (Carnegie Mellon University), Shachar Lovett, Anthony Ostuni (University of California, San Diego), Mehtaab Sawhney (Columbia University)
|
|
Pattern Matching under Weighted Edit Distance
Panagiotis Charalampopoulos (Birkbeck, University of London), Tomasz Kociumaka (Max Planck Institute for Informatics), Philip Wellnitz (National Institute of Informatics)
|
|
Faster logconcave sampling from a cold start in high dimension
Yunbum Kook, Santosh S. Vempala (Georgia Institute of Technology)
|
|
Rapid Mixing on Random Regular Graphs beyond Uniqueness
Xiaoyu Chen (Nanjing University), Zejia Chen (Shanghai Jiao Tong University), Zongchen Chen (Georgia Institute of Technology), Yitong Yin, Xinyuan Zhang (Nanjing University)
|
|
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
Shunhua Jiang (Columbia University), Michael Kapralov (EPFL, Switzerland), Lawrence Li Er Lu (University of Toronto), Aaron Sidford (Stanford University)
|
|
Proving Natural Distribution Properties is Harder than Testing Them
Tal Herman (Weizmann Institute of Science), Guy Rothblum (Apple)
|
|
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Benjamin Bedert, Tamio-Vesa Nakajima, Karolina Okrasa, Stanislav Zivny (University of Oxford)
|
|
On Inverse Theorems and Combinatorial Lines
Amey Bhangale (UC Riverside), Subhash Khot (NYU), Yang Liu (Carnegie Mellon University), Dor Minzer (MIT)
|
|
Adaptivity Gaps for Stochastic Probing with Subadditive Functions
Jian Li, Yinchen Liu, Yiran Zhang (Tsinghua University)
|
|
Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
Lasse Wulf (Technical University of Denmark)
|
|
The Sponge is Quantum Indifferentiable
Gorjan Alagic (University of Maryland and NIST), Joseph Carolan (University of Maryland, College Park), Christian Majenz, Saliha Tokat (Technical University of Denmark)
|
|
A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
Sanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten (University of Pennsylvania)
|
|
Adversarially robust quantum state learning
Yuhan Liu, Maryam Aliakbarpour, Nai-Hui Chia (Rice University), Vladimir Braverman (Johns Hopkins University, Google, Rice University)
|
|
On Succinct Obfuscation via Propositional Logic (or: How to use pv-IO)
Abhishek Jain (NTT Research and JHU), Zhengzhong Jin (Northeastern University), Surya Mathialagan (MIT), Omer Paneth (Tel Aviv University)
|
|
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
Shuichi Hirahara (National Institute for Informatics), Naoto Ohsaka (CyberAgent, Inc.)
|
|
Faster exact learning of k-term DNFs with membership and equivalence queries
Josh Alman (Columbia University), Shivam Nadimpalli (MIT), Shyamal Patel, Rocco A. Servedio (Columbia University)
|
|
Tight Pair Query Lower Bounds for Matching and Earth Mover’s Distance
Amir Azarmehr, Soheil Behnezhad (Northeastern University), Mohammad Roghani, Aviad Rubinstein (Stanford University)
|
|
RE-completeness of entangled constraint satisfaction problems
Eric Culf, Kieran Mastel (University of Waterloo)
|
|
Succinct Homomorphic MACs from Groups and Applications
Yuval Ishai (Technion), Hanjun Li, Huijia (Rachel) Lin (University of Washington)
|
|
Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair
Lorenzo Beretta (University of California, Santa Cruz), Vincent Cohen-Addad, Rajesh Jayaram (Google Research), Erik Waingarten (University of Pennsylvania)
|
|
Undirected Multicast Network Coding Gaps via Locally Decodable Codes
Zhongtian He, Mark Braverman (Princeton University)
|
|
Distance Approximating Minors for Planar and Minor-Free Graphs
Hsien-Chih Chang, Jonathan Conroy (Department of Computer Science, Dartmouth College)
|
|
Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
Debarati Das (Pennsylvania State University), Jacob Gilbert (University of Maryland), Tomasz Kociumaka (Max Planck Institute for Informatics), MohammadTaghi Hajiaghayi (University of Maryland), Barna Saha (University of California, San Diego)
|
|
Exponential improvements to the average-case hardness of BosonSampling
Adam Bouland, Shaun Datta (Stanford University), Bill Fefferman (University of Chicago), Felipe Hernandez (Penn State)
|
|
Radial Isotropic Position via an Implicit Newton’s Method
Arun Jambulapati (Independent), Jonathan Li, Kevin Tian (UT Austin)
|
|
Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ1-Oblivious Routings
Maximilian Probst (ETH Zürich), Rasmus Kyng, Tim Rieder (ETH Zurich)
|
|
High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich
Ruiquan Gao (Stanford University), Alexandros Hollender (University of Oxford), Aviad Rubinstein (Stanford)
|
|
Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
Timothy M. Chan (University of Illinois at Urbana-Champaign), Hsien-Chih Chang (Department of Computer Science, Dartmouth College), Jie Gao (Rutgers University), Sándor Kisfaludi-Bak (Aalto University), Hung Le (University of Massachusetts, Amherst, USA), Da Wei Zheng (University of Illinois at Urbana-Champaign)
|
|
Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics,
Hyung-Chan An (Yonsei University), Mong-Jen Kao (National Yang-Ming Chiao-Tung University), Changyeol Lee (Yonsei University), Mu-Ting Lee (National Yang-Ming Chiao-Tung University)
|
|
Rank Bounds and PIT for $\Sigma^3 \Pi \Sigma \Pi^d$ circuits via a non-linear Edelstein-Kelly theorem
Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta (University of Waterloo)
|
|
Dynamic Treewidth in Logarithmic Time
Tuukka Korhonen (University of Copenhagen)
|
|
Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
Robin Bowers (University of Colorado Boulder), Marius Garbea, Emmanouil Pountourakis (Drexel University), Samuel Taggart (Oberlin College)
|
|
Fast Algorithms for Graph Arboricity and Related Problems
Ruoxu Cen (Duke University), Henry Fleischmann, George Z. Li, Jason Li (Carnegie Mellon University), Debmalya Panigrahi (Duke University)
|
|
Collapsing Catalytic Classes
Michal Koucky (Computer Science Institute of Charles University, Prague), Edward Pyne (MIT), Ian Mertz, Sasha Sami (Charles University)
|
|
Shortest Paths on Convex Polyhedral Surfaces
Haitao Wang (University of Utah)
|
|
An Improved Bound for the Beck-Fiala Conjecture
Nikhil Bansal (University of Michigan), Haotian Jiang (University of Chicago)
|
|
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud (Weizmann Institute of Science), Rasmus Kyng (ETH Zurich), Jason Li (Carnegie Mellon University), Debmalya Panigrahi (Duke University), Maximilian Probst (ETH Zurich), Thatchaphol Saranurak (University of Michigan), Wuwei Yuan, Weixuan Yuan (ETH Zurich)
|
|
Near-Optimal Fault-Tolerant Strong Connectivity Preservers
Gary Hoppenworth, Thatchaphol Saranurak, Benyu Wang (University of Michigan)
|
|
Improved 2-Approximate Shortest Paths for close vertex pairs
Manoj Gupta (IIT Gandhinagar)
|
|
Shuffling Cards When You Are of Very Little Brain: \\Low Memory Generation of Permutations
Moni Naor (Weizmann Institue), Boaz Menuhin (Weizmann Instiute)
|
|
Improved Round-by-round Soundness IOPs via Reed-Muller Codes
Dor Minzer, Kai Zhe Zheng (MIT)
|
|
Near-Optimal Algorithms for Omniprediction
Princewill Okoroafor, Bobby Kleinberg, Michael Kim (Cornell University)
|
|
Almost Tight Additive Guarantees for $k$-Edge-Connectivity
Nikhil Kumar, Chaitanya Swamy (University of Waterloo)
|
|
On optimal distinguishers for Planted Clique,
Ansh Nagda (UC Berkeley), Prasad Raghavendra (U.C. Berkeley)
|
|
Constant Rate Codes for Adaptive Broadcasts Do Not Exist
Klim Efremenko (Ben-Gurion University), Gillat Kol, Dmitry Paramonov (Princeton University), Raghuvansh Saxena (Tata Institute of Fundamental Research)
|
|
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu (University of Waterloo), Venkatesan Guruswami (University of California, Berkeley), Euiwoong Lee (University of Michigan), Xuandi Ren (University of California, Berkeley)
|
|
Near-Optimal Property Testers for Pattern Matching
Ce Jin (MIT), Tomasz Kociumaka (Max Planck Institute for Informatics)
|
|
Deterministic factorization of constant-depth algebraic circuits in subexponential time
Somnath Bhattacharjee (University of Toronto), Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi (Tata Institute of Fundamental Research, Mumbai), Shubhangi Saraf (University of Toronto)
|
|
Integer multiplication is at least as hard as matrix transposition,
David Harvey (UNSW Sydney), Joris van der Hoeven (Ecole Polytechnique)
|
|
A k^{q/q-2} Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
Oliver Janzer (EPFL), Peter Manohar (The Institute for Advanced Study)
|
|
Online Edge Coloring: Sharp Thresholds
Joakim Blikstad (CWI), Ola Svensson, Radu Vintan (EPFL), David Wajc (Technion)
|
|
Gap-preserving reductions and RE-completeness of Independent Set Games
Laura Mančinska, Pieter Spaas, Taro Spirig (University of Copenhagen), Matthijs Vernooij (TU Delft)
|
|
On the Parallel Complexity of Finding a Matroid Basis
Sanjeev Khanna (University of Pennsylvania), Aaron Putterman (Harvard University), Junkai Song (University of Pennsylvania)
|
|
Bipartite Matching is in Catalytic Logspace
Ian Mertz (Charles University), Aryan Agarwala (Max Planck Institute for Informatics)
|
|
Distributed Triangle Detection is Hard in Few Rounds
Sepehr Assadi, Janani Sundaresan (University of Waterloo)
|
|
Weighted k-Path and Other Problems in O*(2^k) Deterministic Time via Dynamic Representative Sets
Jesper Nederlof (Utrecht University)
|
|
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein (New York University), Joakim Blikstad (CWI), Jason Li (Carnegie Mellon University), Thatchaphol Saranurak (University of Michigan), Ta-Wei Tu (Stanford University)
|
|
Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
Matan Levi, Jonathan Mosheiff (Ben-Gurion University), Nikhil Shagrithaya (University of Michigan, Ann Arbor)
|
|
Kronecker Power Circuits, Orthogonal Vectors, and the Asymptotic Spectrum
Josh Alman (Columbia University), Baitian Li (Tsinghua University)
|
|
Robust Learning of Multi-index Models via Iterative Subspace Approximation
Ilias Diakonikolas, Giannis Iakovidis (University of Wisconsin-Madison), Daniel M. Kane (University of California, San Diego), Nikos Zarifis (University of Wisconsin-Madison)
|
|
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions
Rahul Ilango (MIT), Alex Lombardi (Princeton)
|
|
Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
Ilias Diakonikolas (UW Madison), Daniel Kane (University of California, San Diego)
|
|
Sign-Rank of k-Hamming Distance is Constant
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov (EPFL)
|
|
Incompressibility and spectral gaps of random circuits
Chi-Fang Chen (MIT), Jeongwan Haah (Stanford), Jonas Haferkamp, Yunchao Liu (Harvard University), Tony Metger (ETH Zurich), Xinyu Tan (MIT)
|
|
Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes,
Sumegha Garg (Rutgers University), Akash Kumar Sengupta (University of Waterloo)
|
|
Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
Xiaolin Bu, Biaoshuai Tao (Shanghai Jiao Tong University)
|
|
How Global Calibration Strengthens Multiaccuracy
Sílvia Casacuberta (University of Oxford), Parikshit Gopalan (Apple), Varun Kanade (University of Oxford), Omer Reingold (Stanford University)
|
|
Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
Jonathan Leake (University of Waterloo), Kasper Lindberg (ETH Zurich), Shayan Oveis Gharan (University of Washington)
|
|
More efficient sifting for grid norms, and applications to multiparty communication complexity
Zander Kelley (IAS), Xin Lyu (UC berkeley)
|
|
Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
Mohsen Ghaffari (MIT), Christoph Grunau (ETH Zurich)
|
|
Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
Alberto Larrauri (Durham University)
|
|
Instance-Optimal Uniformity Testing and Tracking
Guy Blanc (Stanford University), Clément Canonne (University of Sydney), Erik Waingarten (University of Pennsylvania)
|
|
Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
George Lu (UT Austin), Jad Silbak (Northeastern University), Daniel Wichs (Northeastern University and NTT Research)
|
|
Optimal Smoothed Analysis of the Simplex Method
Eleon Bach (EPFL), Sophie Huiberts (CNRS)
|
|
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu (Princeton University), Jun-Ting Hsieh (Carnegie Mellon University), Pravesh K. Kothari (Princeton University and IAS), Andrew D. Lin (Princeton University)
|
|
Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
Vladimir Lysikov, Michael Walter (Ruhr University Bochum)
|
|
Lower Bounds for Non-adaptive Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari (Northeastern University), Madhu Sudan (Harvard)
|
|
Polynomial Bounds for the Graph Minor Structure Theorem
Maximilian Gorsky (Institute for Basic Science (IBS), Daejeon, South Korea), Michał Seweryn (Charles University, Prague, Czech Republic), Sebastian Wiederrecht (KAIST, Daejeon, South Korea)
|
|
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai (ETH Zurich), Yiding Hua (ETH Zürich), David Steurer, Andor Vári-Kakas (ETH Zurich)
|
|
Explicit Lossless Vertex Expanders
Jun-Ting Hsieh (Carnegie Mellon University), Alexander Lubotzky (Weizmann), Sidhanth Mohanty (MIT), Assaf Reiner (HUJI), Rachel Yun Zhang (MIT)
|
|
Extractors for Samplable Distribution with Polynomially Small Min-Entropy
Ronen Shaltiel (University of Haifa)
|
|
Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
Seri Khoury (INSAIT), Aaron Schild (Google Research)
|
|
Constant Approximation of Arboricity in Near-Optimal Sublinear Time
Jiangqi Dai, Mohsen Ghaffari (MIT), Julian Portmann (ETH Zurich)
|
|
Solving Zero-Sum Games with Fewer Matrix-Vector Products
Ishani Karmarkar, Liam O’Carroll, Aaron Sidford (Stanford University)
|
|
Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
Simone Di Gregorio (Sapienza), Paul Duetting (Google), Federico Fusco (Sapienza University of Rome), Chris Schwiegelshohn (Aarhus University)
|
|
Characterization of Priority-Neutral Matching Lattices
Clayton Thomas (Microsoft Research)
|
|
ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling
Nick Fischer (INSAIT), Vasileios Nakos (National and Kapodistrian University of Athens and Archimedes, Athena Research Center, Greece)
|
|
Stochastic scheduling with Bernoulli-type jobs through policy stratification
Antonios Antoniadis, Ruben Hoeksma (University of Twente), Kevin Schewior (University of Cologne), Marc Uetz (University of Twente)
|
|
Query-Efficient Fixpoints of $\ell_p$-Contractions
Sebastian Haslebacher, Jonas Lill (ETH Zürich), Patrick Schnider (University of Basel and ETH Zürich), Simon Weber (ETH Zürich)
|
|
Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi (University of Maryland)
|
|
Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
Yumou Fei, Dor Minzer, Shuo Wang (MIT)
|
|
A Little Clairvoyance Is All You Need
Anupam Gupta (New York University, USA), Haim Kaplan (Tel Aviv University), Alexander Lindermayr (University of Bremen), Jens Schlöter (CWI), Sorrachai Yingchareonthawornchai (ETH Zurich)
|
|
Cycle-factors of regular graphs via entropy
Eoin Hurley, Antonio Girao, Lukas Michel, Nemanja Draganic, Alp Müyesser (University of Oxford), Micha Christoph (ETH Zurich)
|
|
Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
Thomas Kesselheim (University of Bonn), Marco Molinaro (Microsoft Research Redmond), Kalen Patton, Sahil Singla (Georgia Institute of Technology)
|
|
Stochastic Knapsack without Relaxing the Capacity
Anindya De, Sanjeev Khanna, Nathan White (University of Pennsylvania)
|
|
Root Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
David P. Woodruff (Carnegie Mellon University), Taisuke Yasuda (The Voleon Group)
|
|
Parallel Repetition for Post-Quantum Arguments
Andrew Huang, Yael Tauman Kalai (MIT)
|
|
Perfect L_p Sampling with Polylogarithmic Update Time
William Swartworth, David P. Woodruff (Carnegie Mellon University), Samson Zhou (Texas A&M University)
|
|
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai (ETH Zurich), Jun-Ting Hsieh, Aayush Jain (Carnegie Mellon University), Pravesh Kothari (Princeton University)
|
|
Optimal 4-Approximation for the Correlated Pandora’s Problem
Nikhil Bansal (University of Michigan), Zhiyi Huang, Zixuan Zhu (The University of Hong Kong)
|
|
PTF Testing Lower Bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas (UW Madison), Daniel M. Kane (University of California, San Diego), Sihan Liu (UCSD), Thanasis Pittas (UW Madison)
|
|
Parallel $(1+\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
Bernhard Haeupler (INSAIT, Sofia University “”St. Kliment Ohridski”” & ETH Zurich), Yonggang Jiang (Max Planck Institute for Informatics and Saarland University), Yaowei Long, Thatchaphol Saranurak (University of Michigan), Shengzhe Wang (ETH Zürich)
|
|
A Finitary Chaitin Incompleteness Theorem and Unconditional Line Count Separations in Bounded Arithmetic
Isabelle Champion (McGill University), Marco Carmosino (IBM Research), Stefan Grosser, Robert Robere (McGill University)
|
|
Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses,
Mark Sellke (Harvard)
|
|
An Improved Greedy Approximation for (Metric) $k$-Means
Moses Charikar (Stanford University), Vincent Cohen-Addad (Google Research), Ruiquan Gao (Stanford University), Fabrizio Grandoni (IDSIA, USI-SUPSI), Euiwoong Lee (University of Michigan), Ernest van Wijland (Université Paris-Cité)
|
|
A distillation–teleportation protocol for fault-tolerant QRAM
Alexander Dalzell, Connor T. Hann (AWS Center for Quantum Computing), András Gilyén (HUN-REN Alfréd Rényi Institute of Mathematics, Budapest), Sam McArdle (AWS Center for Quantum Computing), Grant Salton (Amazon Quantum Solutions Lab), Quynh Nguyen (Harvard University), Aleksander Kubica (Yale), Fernando Brandao (Amazon/Caltech)
|
|
Static Retrieval Revisited: To Optimality and Beyond
Yang Hu (Tsinghua University), William Kuszmaul, Jingxun Liang (CMU), Huacheng Yu (Princeton University), Junkai Zhang (Tsinghua University), Renfei Zhou (CMU)
|
|
Beyond Regularity: Simple versus Optimal Mechanisms, Revisited
Yiding Feng (Hong Kong University of Science and Technology), Yaonan Jin (Huawei TCS Lab)
|
|
Structural properties of the factorization norm
Igor Balla (Simons Laufer Mathematical Sciences Institute), Lianna Hambardzumyan (University of Victoria), Istvan Tomon (Umea University)
|
|
On the Impossibility of SNARGs with Short CRS (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting)
Liyan Chen (Tsinghua University), Zhengzhong Jin (Northeastern)
|
|
Paths and Intersections: Exact Emulators for Planar Graphs
George Z. Li (Carnegie Mellon University), Zihan Tan (Rutgers University), Tianyi Zhang (ETH Zurich)
|
|
Ramanujan bigraphs and applications
Shai Evra (Hebrew University of Jerusalem), Brooke Feigon (CUNY), Ori Parzanchevski (Hebrew University of Jerusalem), Kathrin Maurischat (RWTH Aachen University)
|
|
Stronger Cell Probe Lower Bounds via Local PRGs
Oliver Korten, Toniann Pitassi (Columbia University), Russell Impagliazzo (University of California, San Diego)
|
|
A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
Romain Bourneuf (LaBRI), Pierre Charbit (IRIF, Paris Diderot), Stephan Thomasse (ENS Lyon)
|
|
Edge-weighted Matching in the Dark
Zhiyi Huang, Enze Sun (The University of Hong Kong), Xiaowei Wu (University of Macau), Jiahao Zhao (The University of Hong Kong)
|
|
Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
Louis Golowich, Venkatesan Guruswami (UC Berkeley)
|
|
NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions
Shuichi Hirahara (National Institute for Informatics), Rahul Ilango (Massachusetts Institute of Technology)
|
|
Density Measures for Language Generation
Jon Kleinberg (Cornell), Fan Wei (Duke University, USA)
|
|
Fingerprint Filters are Optimal
William Kuszmaul, Jingxun Liang, Renfei Zhou (Carnegie Mellon University)
|
|
Efficiently Batching Unambiguous Interactive Proofs
Bonnie Berger, Rohan Goyal, Matthew M. Hong, Yael Tauman Kalai (MIT)
|
|
Direct Product Theorems for Randomized Query Complexity
Shalev Ben-David, Eric Blais (University of Waterloo)
|
|
Deterministic counting from coupling independence
Xiaoyu Chen (Nanjing University), Weiming Feng (The University of Hong Kong), Heng Guo (University of Edinburgh), Xinyuan Zhang, Zongrui Zou (Nanjing University)
|
|
Theoretical limitations of multi-layer Transformer
Lijie Chen (University of California at Berkeley), Binghui Peng (Stanford University), Hongxun Wu (University of California at Berkeley)
|
|
High dimensional online calibration in polynomial time
Binghui Peng (Stanford)
|
|
List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
Shashank Srivastava (DIMACS (Rutgers) & IAS), Madhur Tulsiani (Toyota Technological Institute at Chicago, USA)
|
