#7 A Constant-Factor Approximation to Multidimensional Consumer Utility Kira Goldner, Taylor Lundy, Thodoris Tsilivis
#8 Linear Regression with Self-Selection Bias in Polynomial Time Felix Zhou
#9 Sketching Language Models for Context Attribution Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou
#10 On the Menu Complexity of Consumer Utility Maximization Kira Goldner, Divyarthi Mohan, Anh Phung
#11 The universal measure of nonstochastic objects Vladimir Vovk
#12 The power of time reversal in Hamiltonian property testing Richard Allen, Matthias Caro, Yanlin Chen, Tom Gur, Angus Lowe
#13 Pseudodeterminism and MA != NP^BPP in Communication Complexity Thomas Watson
#14 On the Complexity of Finding Fixed Points for Set-Valued Contractions Pucheng Xiong, Emmanouil-Vasileios Vlatakis-Gkaragkounis
#15 Random unitary circuits with constant spectral gap Tim Baer, Jeongwan Haah
#16 Breaking the √3 Barrier for Maximum Weighted 3-Set Packing Weitian Tong, Yao Xu
#17 Fair and Efficient Allocation with Comparison Queries Hirota Kinoshita
#18 The Conditional Geometry of Statistical Verification Thomas Y. Chen
#20 Graph Similarity Meets Optimal Transport Jens Breitung, Timo Gervens, Martin Grohe
#21 Using MSTs to Compute All-Pairs Mincuts and Beyond ... Surender Baswana, Anupam Roy
#22 The Online Steinitz Problem Matteo Russo, Jiaye Wei
#23 Verifiable quantum advantage based on polynomials with planted structures Markus Bläser, Michael Gullans, Dominik Hangleiter, Yuxuan Liu, Youming Qiao
#24 Subset Sum via Partial Match Baitian Li, Lixi Ye
#25 Uniform adjacency-degree probes from differential rigidity Zhipeng Lu
#26 Tangle structure trees Reinhard Diestel, Hanno von Bergen
#27 Asymptotics of Random-Lattice Enumeration: Beyond HKZ via Dense Sublattices Thijs Laarhoven
#28 The Power of Two Choices in Dynamic Pricing: As Good As Full Feedback, Instance-Wise Yan Dai, Tao Lin, Aleksandrs Slivkins
#29 Subset Sum in Almost-Linear Time Ce Jin, Xiao Mao
#30 Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction Shuchi Chawla, Trung Dang
#31 Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable Yuxuan Zhou
#32 From a finite subgroup of $SO(3)$: $C_2$ leads to a Holant dichotomy Yuxuan Zhou
#33 Testing Monotonicity of Real-Valued Functions on DAGs Yuichi Yoshida
#34 Fully Scalable MPC Algorithms for Euclidean Clustering: Constant Approximation in Constant Rounds Artur Czumaj, Shaofeng Jiang, Yaonan Jin, Jianing Lou, Weicheng Wang
#35 Nearly Linear Sample Bounds for Testing Product-State Satisfiability of Dense Quantum \(k\)-SAT Xuhong Liu, Shuai Shao, Zicheng Han, Xiande Zhang
#36 Learning Finite Gaussian Location Mixtures via Gated Moments and Posterior Covers Zhijie Zheng, Chengzhi Xie, Yucong He
#37 A Fully Polynomial Randomized Approximation Scheme for Hypergraph Unreliability Zhijie Zheng
#38 Constant-Factor Hardness of the Euclidean Lattice Covering Radius Zhijie Zheng, Yucong He, Chengzhi Xie
#39 An Exact-Radius Convex Characterization of Discrete Identity Testing Zhijie Zheng
#40 Approximation and Even Arity Hardness for Boolean Constraint Satisfaction Zhijie Zheng, Yucong He, Chengzhi Xie
#41 Optimal single-copy estimation of quantum state moments: why $\operatorname{Tr}(\rho^3)$ and $\operatorname{Tr}(\rho^4)$ are equally hard Zhenhuan Liu
#42 The Exact Welfare Guarantee of Fixed-Price Bilateral Trade Tingyi Lin, Yichen Shi, Ke Dong, Jiazhuo Li, Shawn Yu, Huanxi Zhang
#43 Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for \(\mathsf{AC}^0[2]\)-Frege Yaroslav Alekseev, Svyatoslav Gryaznov, Dmitry Itsykson, Toniann Pitassi, Robert Robere, Iddo Tzameret
#44 Moment Ambiguity and the Limits of Robust Stochastic Optimization Andrés Cristi, Matteo Russo, Jiechen Zhang
#45 Unconditional Boolean Dynamic Lower Bounds from Disjointness Young Kun Ko
#46 A Fast Lewis-weight Interior-Point Method for Linear Optimization over Product Convex Sets Peiyuan ZHANG, Stephen WRIGHT
#47 Witness Encryption via Prime-Order Generic Groups Isaac M Hair, Amit Sahai
#49 Reachability in Five-Dimensional Vector Addition Systems Is PSPACE-Complete Weijun Chen, Bo Fu, Yuxi Fu
#51 Robustly Obedient Data Driven Persuasion under State-dependent Sender Payoffs Shabab Neel
#52 From Succinct Arguments to Proofs: Lower Bounds for Obfuscation and SNARGs Abhishek Jain, Surya Mathialagan, Lawrence Roy
#53 Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling Yiming Gao, Xuyuan Han, Honggang Hu
#55 Settling Nondeterministic Communication Complexity of Graph Connectivity Zhijun Zhang
#56 Upper Bounds of Graph Hamiltonian Cycles with Arithmetic Computation Iftikhar Burhanuddin
#57 Minimax Alternating Regret for the Experts Problem and Online Convex Optimization Mengxiao Zhang
#58 Doubly-Efficient Private Information Retrieval from Modular Forms Alexandra Henzinger, Seyoon Ragavan
#59 Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors Eli Yablon
#60 How To Track Qubits Through Space and Time (Or: Sailing in a Quantum Boat) James Bartusek, Zikuan Huang, Leo Orshansky, Henry Yuen
#61 The Quantumly Fast and the Classically Forrious Clément Canonne, Kenny Chen, Julian Mestre
#62 New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond N^4/3 Bo Liu, Yuan Xie
#63 Adaptive Variance Reduction across Smoothness and Noise Conditions Wei Jiang, Yibo Wang, Sifan Yang, Lijun Zhang, Zechao Li
#65 Spectrum Estimation is Almost as Hard as Tomography Marco Fanizza, Ryan O'Donnell, Chirag Wadhwa
#67 An Optimal Agnostic PAC Algorithm Markus Engelund Dahl, Jian Qian, Nikita Zhivotovskiy
#68 Provable Quantum-Classical Separation for Continuous Gibbs Sampling Enrico Olivucci, Mariia Sobchuk, Sehmimul Hoque, Jeffrey Hnybida, Kyungho W. Kim, Ala Shayeghi, Pooya Ronagh
#69 The First-Order Oracle Complexity of Lipschitz Convex Optimization in Nondual Settings Brian Bullins, Cristóbal Guzmán, David Martinez-Rubio, Mathieu Molina
#70 Tight Hardness of Hint-MLWE Problem and Discrete Gaussian Convolutions Navid Abapour
#71 Exponential quantum space advantage in random data streams Adam Bouland, Matthew Ding, Siddhartha Jain
#73 k-Coloring is Faster than Computing the Chromatic Number Or Zamir
#74 Parity and Pattern Detection in Permutation Streams Mark Braverman, Or Zamir
#75 Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS Relaxations Shucheng Kang
#76 Approximating Polynomials for De Morgan Formulas with Optimal Coefficient L1-Norm Bounds Yichuan Wang
#77 No-Regret Revenue Maximization in Sequential Market Making Under Inventory Constraints Davide Maran, Marcello Restelli, Francesco Emanuele Stradi
#78 From APSP to MSSP and Back Again: Improved Shortest Paths Algorithms in the Congested Clique Model Shiri Chechik
#79 Approximate Dual Separation for the Cluster LP: a $1.387$-approximation for Correlation Clustering David García-Soriano, Antoine Schohn
#80 Hermite Brings a Laptop: Analyzing Frieze-Jerrum Rounding Yields Improved Approximations for Clustering Problems David García-Soriano, Atsushi Miyauchi
#81 The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante
#82 Memory-efficient Finite-sum Optimization without Full Gradient Refreshes Wei Jiang, Yibo Wang, Wenhao Yang, Zechao Li, Lijun Zhang
#83 Improved Lower Bounds on Tree Covers Yu Chen, Shengtang Huang, Zihan Tan, Hangyu Xu
#84 Introducing Feedback Delays to Non-Delayed Adversarial MDPs: Optimal √S and √K Dependencies in Tabular and Linear AMDPs Aarush Kulkarni, Khang Nguyen, William Chang, Yan Dai
#85 Minimax Realized Full Swap Regret on the Euclidean Disk Manoj Saravanan
#86 Sharp Limits of Time Invariance in Private Continual Counting Kisung Park
#87 Intractability of Hilbert's Nullstellensatz implies algebraic hardness of permanent Peter Buergisser
#89 Efficient construction of subspace design codes over constant alphabet Shu Liu
#90 A 4/3 approximation for TAP via deferred Primal-Dual Guy Kortsarz
#91 The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting Konstantina Bairaktari, Markus Engelund Dahl, Kasper Green Larsen
#92 Multi-Access Randomness Saves Space, Even for Halting Algorithms William M. Hoza
#93 Caching with a Changing Cache Size Michael A. Bender, Daniel DeLayo, Pritom Kundu, Charlie McGuffey, Zofia Stefankovic, Zhonglue Wang
#94 Compressed Oracle Duality: A simple framework for knowing what quantum adversaries know Matthew Ding, Mark Zhandry
#95 The Harmonic Online k-Server Algorithm Is Poly(k)-Competitive Yichen Huang
#96 The Online k-Taxi Problem Is Competitive on All Metrics Christian Coester, Yichen Huang, Tze-Yang Poon
#97 An O(loglogn) Upper Bound on the Price of Stability for Undirected Multicast Shapley Games Jingyuan Huang, Yang Yuan
#98 Testing Fairness of Evolving Software under Uncertainty Chandan Kumar Sah, Li Zhang, Xiaoli Lian
#99 Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary Mengxiao Zhang
#100 Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling Sven Jäger, Alexander Lindermayr, Bart Zondervan
#101 Optimal Subcubic Byzantine Agreement with Plain PKI Marc Dufay, Roger Wattenhofer
#102 Exponential Quantum Advantage in Testing Fourier Dimensionality Kenny Chen
#103 Online Random Sampling with Real Probabilities Thomas Draper, David Harris, Feras Saad
#104 Cutting a Cake For Human Consumption: An Elementary $n$-agent Cake Cutting Protocol Alexandros Psomas
#106 Deterministic Root-Finding over Finite Fields with Elliptic Curves Pierre-Jean Spaenlehauer
#107 An Algebraic Semantic Framework for Nondeterministic Computation Bojin Zheng, Jingwen Zheng, Weiwu Wang, Zhiying Huang
#108 Separating $\mathbf{P}$ and $\mathbf{NP}$ under the Algebraic Semantic Framework Bojin Zheng, Jingwen Zheng, Weiwu Wang
#109 A Tight Superlinear Lower Bound on the Sketching Dimension of Weighted Spectral Sparsification Yanyu Chen, Yu Chen, Mingji Yang
#110 Last-Iterate Stationarity of Muon with Finitely Many Newton-Schulz Iterations Ping Li, Vincent Y. F. Tan
#111 Paths and Intersections: Repelling Pairs Yu Chen, Pavlo Pylyavskyy, Zihan Tan
#112 Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment Sophia Heimann, Hung P. Hoang, Stefan Hougardy
#113 Concentration Inequalities for Branching Random Walks with Applications to Phase Transitions in CSPs Changqing Liu, Bo Zhang
#114 Arbitrarily Slow Polynomial Convergence of Fictitious Play Jacob Abernethy, John Lazarsfeld, Andre Wibisono
#116 Unconditional Certified Randomness without Structure Andrea Coladangelo, Dakshita Khurana, Saachi Mutreja, Bhaskar Roberts, Joseph Slote, Avishay Tal
#117 On the Hardness of 4-to-1 Games with Perfect Completeness Yumou Fei, Dor Minzer, Shuo Wang
#118 Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depth Aniruddha Sen, Nick Hunter-Jones
#119 Spatial Communication Complexity of Agnostic Halfspace Learning Vera Yang
#120 Hardness Amplification of Approximate Nash Equilibrium with Constantly Many Players Xiaotie Deng, Ningyuan Li, Zihe Wang, Jie Zhang
#121 Prime cordial labeling of Kn¨odel graph Mominul Haque Khandoker Mohammed, Umme Nasreen Khanam, Khandoker Mohammed Faiyaz Shahriar
#122 The Spectral Cost of Sharpness: Fourier Truncation, the Gibbs Bend, and the Computability of Classification Wenwei Li
#127 Exact Parallel Sampling without Maximal Independent Sets Junlong Shen, Shuangzhi Li, Xirui Shi, Xingyu Li
#128 A Degree--Size Relation for Resolution over Polynomials Shuo Pang
#129 Scalable Passive QRAM Siddhartha Jain, Alexander Dalzell, Connor Hann
#130 A Linear Lower Bound on Testing Graph Isomorphism in the Bounded-Degree Model Amit Dror
#131 A Quadratic Lower Bound on Determinantal Complexity Mrinal Kumar, Ben Lee Volk
#132 A Lower Bound for Read-Once Parity Branching Programs Ben Lee Volk
#133 Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers Huanyi Zhou
#134 Almost-MMS allocations with small agent redundancy Vadim Grinberg, Uriel Feige
#135 0.4633-Approximation for Online and Offline Non-Monotone DR-Submodular Maximization Vaneet Aggarwal, Donglei Du
#136 Strongly explicit Ramanujan 2-lift towers via Hilbert modular forms Olga Kharlampovich, Igor Pak, Alina Vdovina
#137 Exponential Sampling Lower Bounds for Polynomial Sources Yan Zhong
#138 Non-Malleable Affine Extractors with Small Error and Complexity Lower Bounds Yan Zhong, Xin Li
#139 A dichotomy theorem for approximating CSPs in random-order streams Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy
#140 Finding a Shortest Vector and More in $2^{n/2+o(n)}$ Time using $q$-ary Coset Difference Tree Minki Hhan
#141 Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput Maximization Weitian Tong, Yao Xu
#142 Sample-Efficient Agnostic Multi-Distribution Learning Requires Polynomial Adaptivity Thomas Chen
#143 Supervised Learning with Hidden Correspondences August Chen, Claudio Gentile, Haim Kaplan, Tomer Koren
#144 The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness Itay Shalit, Mark Zhandry
#145 Local Search with Correlated Randomness Yunbei Xu
#147 Optimal Sample Complexity for Max-Cut Itamar Bender, Robert Krauthgamer
#148 A New Approach to Reducing Modulus Requirements in Homomorphic Computation: Precision Allocation in CKKS Zhaoyang Liang, Runkun Liu, Jingwei Fang, Dan Ding
#149 Temporal Aggregation: Maintaining Randomness against Adaptive Adversaries Bernhard Haeupler, Anton Paramonov
#150 Integral saturation of adjacency-degree lattices Zhipeng Lu
#151 The Complexity of Single-Interaction Hamiltonians Elad Hecker
#152 Limits of Finite-Sample Dependence Measures under Data Processing Inequality Yuqing Kong
#153 Optimal Marginal Convergence for Transvection-Walk-Based Trapdoored Matrices over Large Fields Mark Braverman, Aayush Jain, Stephen Newman
#154 Beating the Gilbert–Varshamov Bound at Alphabet Size 42 Gil Cohen, Tomer Manket
#155 An $O(n^{0.1537})$-Coloring Algorithm for $3$-Colorable Graphs Kaisei Deguchi, Ken-ichi Kawarabayashi, Hirotaka Yoneda, Masataka Yoneda
#156 BQP⊆IP Does Not Relativize Adam Bouland, Andrew Huang, Anand Natarajan, Itay Shalit, Avishay Tal
#157 Random-Oracle Unitary Synthesis is Impossible Andrew Huang, Akshar Ramkumar, John Wright
#158 Tight Post-Quantum Parallel Repetition for Private-Coin Arguments Zvika Brakerski, Andrew Huang, Yael Tauman Kalai, Nicholas Spooner
#159 Sharp universal death of entanglement threshold for Pauli Hamiltonians Bobak Kiani
#160 Linear-Space Exact Distance Oracle for Minor-Free Graphs Eunjin Oh
#168 Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order Queries Jiachen Shen, Hui Zhong
#169 Optimal Labeling Schemes for $\Gamma$-Free Matrices Sankardeep Chakraborty, Seungbum Jo
#170 Switching and Entropy Bounds for Stable Matchings Hao Xu, Jinshan Zhang, Feng Wang
#171 Recursive Operator Localization and Spectral Gap Descent via the Geometry of Local Spectral Expansion Ryu Hayakawa
#172 From Oblivious to Adaptive Adversaries: Black-Box Reductions for Monotone Dynamic Problems with Applications to Cuts, Distances, and Clustering Shiri Chechik, Inbal Hadad
#173 Structural Complexity of Matching with Indifferences Jinshan Zhang, Nan Zhao, Hao Xu, Meng Xi, Lin Zhao
#174 Optimal Truthful Approximation for House Allocation and Rank-Maximal Matchings with Ties Jinshan Zhang, Nan Zhao, Hao Xu, Meng Xi, Lin Zhao
#176 Harmonic Ranking for Edge-Weighted Oblivious Matching Bo Peng, Zhihao Gavin Tang
#177 Classical Oracle Separation of QMA from the QCMA Hierarchy and Quantum Cryptography Even When P = QCMA Alper Cakan
#178 Private Uniform Language Generation Di Wang, Peng Ye
#179 Polylogarithmic Shortest Path Decompositions for Minor-free Graphs in Near-linear Time Michał Włodarczyk
#180 Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials Zhangsong Li
#181 A Witnessing Duality for ReLU Network Depth Dimitrios Myrisiotis
#182 Near-Optimal Makespan and Parameterized Hardness for Multi-Robot Motion Planning Benjamin Holmgren, Jack Stade, Pankaj K Agarwal
#183 A Uniform Algorithm for Strict NP on Bounded-Treedepth Structures Thomas Depian, Robert Ganian, Jakob Greilhuber, Marlene Gründel, Simon Wietheger
#185 A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane Sarita de Berg, Jacobus Conradi, Peter Kramer, André Nusser, Sampson Wong
#186 The No-Menu Complexity of Revenue-Maximizing Auctions Gagan Aggarwal, Trung Dang, Aviad Rubinstein, Mingfei Zhao
#187 Efficient fault-tolerant self-routing on constant-degree networks Yinchen Liu, Ryan O'Donnell, Noah G. Singer
#188 The Hardness of Dominant Strategy Mechanism Design, Revisited Frederick Qiu
#189 Learning vs. Optimizing Players in Budgeted Games Giannis Fikioris, Balasubramanian Sivan, Eva Tardos
#190 Revisiting Local Push: Faster Algorithms and Optimal Query Complexity for PageRank and Effective Resistance Guanyu Cui, Zhewei Wei, Mingji Yang
#191 Computing Weighted Set Covers with Heterogeneous Stochastic Oracles: Deadline-Constrained Token Complexity Jie Wang
#193 Sharp Phase Transition for Ellipsoid Fitting Sofia de la Cerda, Aaron Potechin, Madhur Tulsiani, Jeff Xu
#194 Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements Ashwin Nayak, Xingyu Zhou
#195 Parallel Repetition for k-Player XOR Games Mark Braverman, Dor Minzer
#196 Optimal Early-Stopping Broadcast via Exponential Information Gathering Giovanni Deligios, Fatima Elsheimy, Simon Holmgaard Kamp, Ivana Klasovitá, Charalampos Papamanthou, Chen-Da Liu-Zhang, Julian Loss
#197 Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma Fernando Brandao, Alexander Dalzell, Andras Gilyen, Francisca Vasconcelos
#211 One-Way Functions and Local Descriptions of Random Data Dimitrios Myrisiotis
#212 Metric Facility Location under Batched Random Order Fabrizio Grandoni, Stefano Leonardi, Matteo Russo
#213 Random quantum circuits beyond moment matching Shih-Han Hung
#214 Optimal Zonotope Containment via Adaptive Gaussian Sampling Friedrich Eisenbrand, Thomas Rothvoss, Matteo Russo, Ruben Skorupinski
#215 Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry Frédéric Magniez, Sebastian Zur
#216 New lower bounds on tensor rank of $(n,2,m)$ matrix multiplication with GPT-6 Astra Jason Yang
#217 Online Multi-Level Aggregation with Maximum Delay Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
#218 Online Service with Per-Batch Maximum Delays Tianhang Lu, Runtian Ren, Shengcai Liu, Ke Tang
#219 Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-Complete Qiuyu Chen, Ba'ao Xie
#220 Ramsey Obstructions to Disambiguation Romain Bourneuf, Antonin Kiladjian, Stephan Thomasse
#221 (Almost) quadruply optimal unitary designs in 1D Guoding Liu, Jonas Helsen
#222 Quantum Fire with Delegated Cloning Rohit Chatterjee, Ananta Mukherjee, Vir Pathak, Supartha Podder
#223 Exact Fully Dynamic Single-Source Shortest Paths in Nonnegative Weighted Graphs Jun Liang, Yuhan Chen, Zanbo Zhang
#224 Enumerating Complexity Revisited Alexander Shekhovtsov, Nikolay Vereshchagin, Georgii Zakharov
#225 Weakly Stable Roommates with Two Master Lists: Tractable Existence and Hard Optimization Bin Yu
#226 Distributed Quantum Certification with Clifford Encoders Hyunho Cha, Jungwoo Lee
#227 Quantitative Results on Super-Ramanujan Graphs Gil Cohen, Gal Maor
#228 An exponential separation between entanglement-assisted and unassisted one-way quantum communication Ryan Anselm, Srijita Kundu, Olivier Lalonde, Ashwin Nayak
#229 Sounder, shorter, and simpler PCPs from HDX neighborhoods Yotam Dikstein, Irit Dinur, Max Hopkins, Noah G. Singer
#230 Sublinear Copies Suffice for Fidelity Estimation with Pauli Measurements Abhilash Dharmavarapu, Jayadev Acharya, Nengkun Yu, Yuhan Liu
#231 Near-Optimal Mixedness Testing with Pauli Measurements Abhilash Dharmavarapu, Jayadev Acharya, Nengkun Yu, Yuhan Liu
#232 Ruling out Fast Approximation Algorithms for Clique, Biclique, Collinearity, and Arithmetic Progressions Reina Itakura, Karthik C.S., Mayank Motwani, Gary Peng
#233 Hamiltonicity of mildly pseudorandom regular graphs Alp Muyesser
#234 Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection Yihang Sun, Mary Wootters
#235 Optimal Conversion from Zero-Concentrated to Gaussian Differential Privacy Yu-Wei Chen, Aaradhya Pandey, Jordan Awan
#239 Composable Content-Oblivious Leader Election on Eulerian Graphs Fabian Frei, Ran Gelles, Ahmed Ghazy, Alexandre Nolin
#240 When Masks Leak Their Weight: From Additive Sharing to Learning with Physical Rounding Aniruddha Biswas, Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, Xiuyu Ye
#241 Learning quantum symmetries Isaac Holt, Sathyawageeswar Subramanian
#242 When are bosonic Gaussian states classical to learn? Senrui Chen, Antonio Anna Mele, Francesco Anna Mele, John Preskill
#243 Optimal cloning of mixed states Dmitry Grinko, Marco Fanizza, Thilo Scharnhorst, Jack Spilecki
#244 Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework Jiale Chen
#245 Local Leakage Resilience of Multiplication-friendly Shamir Secret Sharing Jihun Hwang, Hemanta K. Maji, Ilya D. Shkredov, Xiuyu Ye
#246 Group Isomorphism: Depth-$2\frac{1}{2}$ Circuits and Lower Bounds Joshua A. Grochow, Gülce Kardeş, Michael Levet
#247 Triangle-Freeness: Estimation Is as Easy as Testing Asaf Shapira, Nick Kushnir
#248 Deterministic Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set Adithya Diddapur
#250 Quantum Cryptomania with Classical Communication without One-Way Functions Mohammed Barhoush, Amit Behera
#251 Quantum Fair Exchange Hao Chung, Yi Lee, Justin Raizes, Sri AravindaKrishnan Thyagarajan
#252 Quantum lower bounds for convex optimization and real matrix-vector query problems Andrew Childs
#253 Designing AI for Cyber Defense: A Decision-Centered Study of Network, Software, and Phishing Risk Sungho Kim
#254 Artificial Intelligence for Cybersecurity: A Comparative Framework for Intrusion Detection, Malware Classification, and Phishing Detection Sungho Kim
#255 Shrinkage-Calibrated Prototypical Networks for Label-Scarce and Imbalanced Defect Detection: A Cross-Modality Study on Wafer Maps and Process Sensor Data Sungho Kim
#256 A Hybrid Ensemble Voting Framework for Cardiovascular Disease Prediction Using Feature Engineering and Adaptive Threshold Optimization Sungho Kim
#258 The stationarity test: a framework for learning quantum many-body systems from their thermal states Thiago Bergamaschi
#260 Algorithmic thresholds for finding large independent sets in random graphs Matthew Cho, Lutz Warnke
#261 Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive Error Marek Elias, Gautam Kamath, Janardhan Kulkarni, George Li, Jingcheng Liu, Sepideh Mahabadi, Pan Peng, Jakub Tarnawski, Hangyu Xu, Zongrui Zou
#262 Improved Embedding of $k$-Outerplanar Metrics into $\ell_1$ Zihan Tan
#263 Polylogarithmic Collective Tree Exploration Romain Cosson, Laurent Massoulié
#264 Near-Optimal First-Order Regret for Bandits with Feedback Graphs Mengxiao Zhang, Yuheng Zhang, Haipeng Luo, Paul Mineiro
#265 A Sharp Dynamic Haussler Lemma Shihao Shao, Dacheng Tao
#266 Sampling from the Sherrington--Kirkpatrick Model up to Criticality Hang Du, Brice Huang, Sidhanth Mohanty, Amit Rajaraman
#267 Is Randomness Necessary for Adaptive Data Analysis? Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Sapir, Uri Stemmer, Eliad Tsfadia
#268 Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs Zhidan Li, Kuan Yang
#269 Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold Zhidan Li, Kuan Yang
#270 Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics Yossi Azar, Junhao Gan, Shahar Lewkowicz, Xiao Sun, Seeun William Umboh
#271 Designing Information in a Forest: Algorithmic Aspects Konstantin Zabarnyi
#272 Entropy Bounds for Local Coordination and Graph Amenability Ron Peretz, Dean Kraizberg
#274 Testability of General Graphs with Weak Query Oracles Oded Lachish, Amit Levi, Ilan Newman
#275 Optimal Online Stochastic Matching Paul Duetting, Michal Feldman, Mathieu Molina
#276 Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum Verifiers Alper Cakan
#277 One Polynomial Field for Every Euler Step and the Flow: Polynomial Dynamics for PTIME and PSPACE Olivier Bournez
#278 Canonical Graph Decompositions via Local Separations Raphael W. Jacobs, Paul Knappe, Jan Kurkofka
#279 Optimal PRGs for Low-Degree Polynomials over Polynomial-Size Fields Gil Cohen, Noam Goldgraber
#280 From Block Orthogonality to Decidability in Complex-Weighted Counting CSP Chenghua Liu, Boning Meng
#281 Fatness and Flatness Arnold Filtser, Hung Le, Nikolas Mählmann, Marcin Pilipczuk, Michał Pilipczuk
#283 Robust Exact Realization of Pairwise Boolean Statistics Kegong Shi, Hongfei Sun
#284 Nearly Optimal Sparse Navigable Graphs in General Metrics Hongyi Chen, Tianyi Zhang
#285 The Computational Complexity of Concurrent Stochastic Games: Exact Value and Approximation Ali Asadi, Krishnendu Chatterjee
#286 The Multiple Unicast Conjecture is False Mark Braverman, Zhongtian He
#287 Bayesian Optimal Stopping: Invincible Prophets and Achievable Philosophers Alireza AmaniHamedani, Ali Aouad, Senem Isik, Thomas Kesselheim, Amin Saberi
#288 Unitary Complexity in Polynomial Space William Kretschmer, Ewin Tang
#289 A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs Vikrant Ashvinkumar
#290 Optimal testing of fermionic and bosonic Gaussian states Vishnu Iyer, Bryan O'Gorman, Ojas Parekh, Kevin Thompson, Andrew Zhao
#291 Stable Voting Rules on the Edge of Optimal Metric Distortion Ziyi Cai, Fabian Frank, Jabari Hastings, Prasanna Ramakrishnan, Kangning Wang, Qilin Ye
#292 Randomized Query Lower Bounds for Submodular Function Minimization James Fox
#293 At What Cost? (In)efficiency in First-Price Procurement Auctions Simone Palazzotto, Andrés Cristi
#294 The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities Ijay Narang, Will Perkins
#295 Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian Certificates Ijay Narang, Yukai Tang
#296 Pareto Inefficiency of EFX Sepideh Mahabadi, Prasanna Ramakrishnan, Jakub Tarnawski
#297 On the Complexities of Interactive Proofs of Proximity Noga Amit, Oded Goldreich
#298 Dimension Reduction and Coresets for Min-Sum k-Clustering Asaf Dallal, Robert Krauthgamer
#299 Monotone circuit lower bounds from spread matchings Anup Rao
#300 The Complexity of Choosing Parity Projections Karthik Sheshadri, Nicholas Smirnov
#301 Strong Lower Bounds for Weak Epsilon-Nets Sujoy Bhore, Reilly Browne, Da Wei Zheng
#303 The Power and Limits of Money Burning in Bilateral Trade Moshe Babaioff, Noam Nisan, Ariel Shaulker
#304 The Exact Communication Threshold for Parallel Repetition Daiki Suruga
#305 A Quadratic Bogolyubov Theorem and Quantum Worst-Case to Average-Case Reductions Davi Castro-Silva, Alexander Golovnev, Tom Gur, Julia Wolf
#306 Thinning and Sprinkling: Robust Vertex Sampling and Almost Hamiltonicity Micha Christoph, Zach Hunter, Benny Sudakov
#308 Approximating Submodular Orienteering via Rooted Subgraph Decomposition Lars Rohwedder
#309 Limits of Lifting Gaia Carenini, Bruno Cavalar, Stefan Grosser, Jan Pich
#310 Learning vs. Optimizing Players in Budgeted Auctions Giannis Fikioris, Eva Tardos, Balasubramanian Sivan
#311 Cryptographic Conditions for Efficient Testing of Distributions and Quantum States Bruno Cavalar, Eli Goldin, Matthew Gray, Taiga Hiroka, Min-Hsiu Hsieh, Tomoyuki Morimae
#313 Tight Bounds for Tusnády's Problem in the Plane Zhewei Wei
#314 Persuasion by Parts Shuyuan Jia, Kangning Wang, Renzhe Xu
#315 Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with $\Theta(n)$ ancilla qubits Zhiyan Ding, Bowen Li, Ruizhe Zhang
#316 The Greedy Superstring Conjecture Is False Nikolai Chukhin, Rishikesh Gajjala, Juha Harviainen, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Shibata, Alexander V. Smal
#317 Omniprediction for All Mixable Proper Losses and Beyond Junyan Liu, Haipeng Luo, Lillian Ratliff
#318 Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds Zixuan Huang, Guozhang Chen
#319 Integral 2 × 3 × 3 Tensor Isomorphism is in BQP Thomas Huffstutler
#320 Efficient Proper Agnostic Learning of Halfspaces Anindya De, Elchanan Mossel, Shivam Nadimpalli, Joe Neeman
#321 Efficient Quantum State Identity Testing Shih-Han Hung, Ming-Hsien Tsai
#322 Learning the structure of open quantum systems Laura Lewis, Ewin Tang, John Wright
#323 Optimal High Probability Bounds for Random Order Online Sorting Mingyu Kang, Chenglin Fan
#324 On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated Priors Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell
#325 Optimal Auctions for Anchored Bidders under a Rational Revenue Guarantee Yanpu Chen, Guangshuai Wang
#326 A Spectral Theory of Local-to-Global Leakage Rei Ueno
#327 Linear Set Reconciliation with $O(d)$ Additive Redundancy Tianren Liu, Rui Xu, Tong Yang, Kangyang Zhou
#328 Positivity Proofs for Third-Order Holonomic Sequences via Differences Scaled by Rational Functions Fugen Hagihara
#330 Failure of Symmetry of Information for Quantum Computations Dimitrios Myrisiotis
#331 Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, Robin Vacus
#332 Random ($\log{n}$)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates Jonas Conneryd
#365 A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model Santosh Vempala
#366 New Lower Bounds for Private PAC Learning Prathamesh Dharangutte, Amartya Sanyal
#367 Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters Mahmut Levent Doğan, Keiya Sakabe, Michael Walter
#368 Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs Trevor Vaughn
#369 Quantum 1-PCA with Pauli Measurements in Nearly Linear Time Dutch Hansen, Jerry Li
#370 Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs Trevor Vaughn, Jason Li
#371 Strong Convergence for Zig-Zag Products and Typical Spectra of Irregular Graphs Gal Maor, Alon Dogon
#372 Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$ Yanyu Chen, Yu Chen
#373 The C-3PO Framework: Algorithms for $\#\mathrm{BIS}$-Hard Problems on Graphs with Low Threshold Rank or High Girth Ijay Narang
#374 Decoupling Corruption and Horizon in Robust Contextual Pricing Matteo Castiglioni, Francesco Emanuele Stradi
#375 Rapid mixing of Potts Glauber dynamics throughout uniqueness Antonio Blanca, Reza Gheissari, Heehyun Park, Xusheng Zhang
#376 Unconditional Quantum PAC Learning Advantage in the Large Error Regime Igor Oliveira
#407 Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3 Jin-Yi Cai, Jin Soo Ihm
#408 Polynomially larger deletion codes by linear hashing of substring counts Eyal En Gad
#409 Thin-shell stability and heat-adjoint hypercontractivity: logconcave sampling with sesteric complexity from a cold start Yunbum Kook, Santosh S. Vempala
#410 Testing State and Unitary Designs Akinori Kawachi, Yoshifumi Nakata, Yuki Takeuchi
#411 No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model Seri Khoury, Aaron Schild
#412 Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking Pan Xu
#413 Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small k Ziang Ni
#414 Product Expansion of Random Codes via Analytic Techniques Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
#415 Stable Movement for Nondual Lipschitz Convex Optimization: Efficiency and Nearly Optimal Oracle Rates David Martinez-Rubio, Cristóbal Guzmán
#416 Online carpooling against an oblivious adversary Yuhao Lei
#417 FIXP-Completeness via Reciprocal Gates: Applications to Second-Price Auctions Nobutaka Shimizu
#418 Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms Jin-Yi Cai, Zhuxiao Tang
#419 Exponentially Larger Deletion-Correcting Codes and Constant-List-Decodable Insertion–Deletion Codes Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
#420 The quantum query complexity of the semigroup product problem Troy Lee, Miklos Santha
#421 Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable Mingkun Xiao, Yixuan Sun
#422 Faster Dynamic Maximal Independent Set against Adaptive Adversaries Hongyi Chen, Shuyan Fan, Tianyi Zhang
#423 Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber Dynamics Aniket Das, Tselil Schramm
#424 Fair Team Contracts Junjie Chen, Matteo Castiglioni, Yingkai Li
#425 New bounds for online coloring three-colorable graphs Yaqiao Li
#447 Settling the Sample Complexity of Rényi Entropy Estimation Qisheng Wang
#448 Distributionally Robust Search: The Power of Information and the Limits of Moments Nicole Megow, Cliff Stein, José Verschae
#449 NP-Hardness of Bounded Distance Decoding for Reed--Solomon Codes Daqing Wan, Jun Zhang
#450 Almost-Linear Modular Composition over Arbitrary Commutative Rings yang zhou, Mingsheng Wang
#451 A Unified Complexity Framework for Quantum Property Testing Qisheng Wang
#452 The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle Model Pengcheng Su, Haibo Cheng, Ping Wang
#453 Tight weighted paging with delay via mirror descent Julian Born, Yann Disser, Linda Thelen
#454 High Precision Multiplicative-Error Approximation of #SAC¹ Functions in Logspace Uniform AC¹ Kuan Cheng, Shengtang Huang, Ruiyang Wu
#455 Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability Giuseppe A. Di Luna, Giovanni Viglietta
#456 A $2.81^n$ upper bound on the number of stable matchings Ebrahim Ghorbani, Matthias Mnich
#457 Faster Provable Algorithm For Random Modular Subset Sum Hyeonhak Kim, Jiseung Kim, Changmin Lee
#458 Approximating commutative rank of matrix spaces in NC Foram Lakhani, Partha Mukhopadhyay
#459 $\ell_{\infty}$ norm SVP in $\widetilde{O}(3^n)$ Yiming Gao
#460 An approximate cactus-decomposition for vertex-connectivity Romain Bourneuf, Johannes Carmesin, Jan Kurkofka, Tim Planken
#489 Newton Steps are Faster for Linear Complementarity Problems Haoyuan Ma, László Végh, Adrian Vladu
#490 QMA has perfect completeness Sabee Grewal, Dorian Rudolph
#492 Fluid Limits and Upper Bounds for Randomized Greedy Matching Sayan Mukherjee
#493 Constant-Round Massively Parallel Algorithms for Approximate MSTs in Metric Spaces Eunjin Oh, Hyeonjun Shin
#494 Computing faster with a full memory: Catalytic algorithms break time-space lower bounds Adelmo Morrison Orozco, Nathan S. Sheffield, Ryan Williams
#495 Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
#496 On ZLIP: Combinatorial Structures and Reduction to √n-ZSVP Shengmao Jiang
#497 Discrepancy for Random Linear Codes Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro
#498 Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range Avoidance Zeyong Li, Roei Tell
#499 Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs Yotam Dikstein, Izhar Oppenheim, Inga
#500 Randomness-Efficient Robust Locally Testable Codes in the Low-Acceptance Regime from HDXs Inbar Ben Yaacov, Yotam Dikstein, Siqi Liu
#501 Geometry Of The Subset Sum Problem - Part I Srinivas Bollepalli
#502 Derandomizing (Fragments of) Arthur–Merlin with Range Avoidance Zeyong Li
#503 A Simple Subquadratic Cut Query Protocol for Directed Reachability Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal
#504 Directed Global Minimum Cut in Almost-Linear Time Henry Fleischmann, Jason Li, Thatchaphol Saranurak, Benyu Wang
#505 The list size of random linear and LDPC codes at capacity Shashwat Silas
#506 Greedy Region Growing: Improved Approximations for Cutwidth, Pathwidth, Flow-Expander Decomposition, and More Aditya Anand
#507 Co-Decompositions and FO Model Checking Benjamin Merlin Bumpus, Guilherme de Castro Mendes Gomes, Laura Larios-Jones, William Turner
#508 Self-stabilising approximate clock synchronisation requires linear time Joel Rybicki
#509 The Polynomial-Time Low-Degree Conjecture is False Songtao Mao
#510 Replicable Online Learners Must Gamble: The Typical-Case Price of Replicability Shulin Lu
#511 Robust quantum state certification and uncertainty principles for total influence Andrea Coladangelo, Jerry Li, Joe Slote
#512 Gain-Sharing Optimization in Randomized Primal--Dual Analysis: Structure and Certification Pan Xu
#514 Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries Surendra Ghentiyala, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
#515 Impossibility of One-Way One-Round Quantum 4-Coloring via Matrix-Space Stability Tom Gur, Longcheng Li
#516 The Complexity of ReLU Network Synthesis from a Parameter Multiset Dimitrios Myrisiotis
#517 Adaptive Steps and Certificates for Semi-Streaming Shortest Paths Sarwan Ali
#518 A Numerical Refinement of an Exact Discrete Fourier Transform Bound Zhihao (Zephyr) Yao, Sichao Liu
#519 Near-Singularly Optimal Distributed APSP Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Peter Robinson, Jacob Way
#520 A Nonadaptive Sparse Fourier Transform in Every Dimension Mahdi Cheraghchi, Jingyi Lyu
#521 Neuromorphic Computation for Scientific Syllogism Xing Xu
#522 Impatience Makes Matching NP-Hard Chen Yan, Sushil Varma
#523 On the Power and Limitations of Multiple Intermediaries for Single-Item Auctions Aadityan Ganesh, Ciamac Moallemi, S. Matthew Weinberg
#524 Provable Recovery from Integer Quotients: Improved Bounds for Nonlinear Hidden Number Problems Taehun Kang, Changmin Lee
#525 Fast Provable Algorithms for Approximate CVP and Exact SVP on Random \(q\)-ary Lattices Jiseung Kim, Junhyuk Kwon, Changmin Lee, JeongHwan Lee
#526 Byzantine Broadcast in $\widetilde{O}(n^2)$ Communication Yuval Efron, Jovan Komatovic, Ling Ren
#527 A Proof of the Most Informative Boolean Function Conjecture Zijie Chen, Amin Gohari, Adel Javanmard, Honghao Lin, Vahab Mirrokni, Chandra Nair, David Woodruff
#528 A Deterministic O(log m)-Competitive Algorithm for Online Minimum Cost Bipartite Matching with Delays Tung-Wei Kuo
#529 Second-Best Trade Is Half Efficient in Multidimensional Markets Dirk Bergemann, Yang Cai, Kangning Wang, Jinzhao Wu, Renzhe Xu
#530 Optimal $e^{(\gamma+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices Nima Anari, Farzam Ebrahimnejad
#531 Unconditional Unclonable Encryption Prabhanjan Ananth, Seyoon Ragavan, Amit Sahai
#532 Quantum Algorithms for OPI Variants Beyond Locality and Classical Decodability Seyoon Ragavan, Noah Shutty
#533 Catalytic Tree Evaluation from Matching Vectors Alexandra Henzinger, Edward Pyne, Seyoon Ragavan
#534 Good Quantum Locally Testable Codes from Lossless Cubical Complexes Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik
#535 Stability Dichotomies for Boolean Constraint Satisfaction Problems Chunyang Wang, Yuichi Yoshida
#536 Random Deletion for Circuits in Regular Matroids Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
#537 How Hard Is It to Compute Cover Time? Ryan Aghazadeh
#538 Differentially Oblivious Priority Queues with Sublogarithmic Cost Zimai Guo, Cheng Hong, Zhechen Li
#539 Breaking the Bounded Entanglement Barrier for Quantum Position Verification Amit Behera, Vipul Goyal
#561 Recovery Beats Storage: Improved Space for Preprocessed 3SUM Amir Carmel, Yakov Kosoburd, Robert Krauthgamer
#562 Beyond Width-3: Better Hitting Set Generators for Width-4 Read-Once Branching Programs Gonen Krak
#563 Breaking the Parity Barrier for Constant-Depth Circuits Nikolai Chukhin, Xin Li, Ivan Mihajlin, Yan Zhong
#564 Quantum Query Lower Bounds from Classical Moment Matching Chandrima Kayal, Frédéric Magniez, Sayantan Sen, Dániel Szabó
#565 Algorithmic List Decoding of Reed–Solomon Codes up to Capacity Joshua Brakensiek, Yeyuan Chen, Aaron Putterman, Zihan Zhang, Kai Zhe Zheng
#566 The Containment Polytope of a Triangle and a Convex Polygon Yoonsung Choi, Sunghee Choi
#567 Lifting to Unary Sherali–Adams over Parities Yaroslav Alekseev
#568 Triangle Counting with Independent Set Queries: Tight Bounds in the IS and Hybrid Models Tomer Adar, Amit Levi
#569 Factoring Products of Sparse Irreducibles of Bounded Individual Degree via Rational Interpolation Amir Shpilka, Aminadav Chuyoon
#570 Fresh Signatures without Fresh Keys Christoph Lenzen, Julian Loss, Kecheng Shi
#571 Trapdoors Beyond Inversion: Recoverable Information in Public-Key Cryptography Kanad Chakravarti, Shreyas Gupta, Bhavana Kanukurthi, Girisha Shankar
#572 Nearly Optimal Information-Theoretic PIR with Client Preprocessing Jesko Dujmovic, Zhengnan Lai, Daniel Wichs
#573 Private Dimension-Free Mean Estimation is Impossible Without the Covariance Renaud Gaucher, Ephraim Linder, Adam Smith, Jonathan Ullman, Lydia Zakynthinou
#574 Sensitivity and Locality Lower Bounds via Low-Soundness Label Cover Noah Fleming, Max Hopkins, Yuichi Yoshida
#575 Spectral gap of Lee-Yang Hamiltonians Chaithanya Rayudu, Jun Takahashi
#576 Efficient Online Proportional Sampling with Applications to Smoothed Online Learning Amirmahdi Mirfakhar, Nina Balcan, Hedyeh Beyhaghi
#577 Hitting sets From Derivations: Waring Rank and Noncommutative ABPs Shubham Bhardwaj, Foram Lakhani, Partha Mukhopadhyay, Ramprasad Saptharishi, Pratik Shastri, Amit Sinhababu
#578 Monotone Local Search with Sample-Dependent Running Times Serge Gaspers
#579 Affine Advantage in Guess-type Attacks on Goldreich’s PRGs: Characterization and Countermeasures Ximing Fu, Mo Li, Shihan Lyu
#580 Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations Bo Li, Ankang Sun
#581 Worst-Case to Average-Case Reductions for Basic Linear Algebra Or Zamir
#582 Frequency Moments Beyond Equality: Streaming Cosine Density Moments Qin Zhang
#583 Testing Implies Distance Estimation with Polynomial Loss Gaia Carenini, Cameron Seth
#584 A Tight Space Lower Bound for Pivot-Based Distance Oracles Avi Kadria, Liam Roditty
#585 Money Burning Mechanism Design: From Welfare to Surplus Tomer Ezra
#587 Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies Irene Aldridge
#588 Achieving Optimal Redundancy for Small Dynamic Rank/Select Dictionaries Gabriel Marques Domingues
#589 A Near-Optimal Parallel Algorithm for Finding Matroid Bases Aaron Putterman, Sanjeev Khanna, Junkai Song
#590 Replicable Mean Estimation via Random Lattice Rounding Kehua Chang
#591 Sublinear Sample Size Suffices for Learning Mixtures of Gaussians up to Isometry Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
#592 Color coding for the Sherrington--Kirkpatrick model Alina Harbuzova, Saba Lepsveridze, Mahbod Majid, Ankur Moitra
#593 Four-Coloring Planar Graphs in Linear Time Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
#594 Trees with Benefits: Stochastic Hop-Constrained Ramsey-Type Embeddings with Logarithmic Expected Distortion Arnold Filtser, Goran Zuzic
#595 Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions Kuan Cheng, Ruiyang Wu
#596 Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities Huanjian Zhou, Taiji Suzuki
#597 PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations Yasushi Kawase, Bodhayan Roy, Mohammad Azharuddin Sanpui
#598 The Entire Quantum Computer on a Classical Leash Yael Kalai, Dakshita Khurana, Justin Raizes
#599 Pandora's Knapsack via Simple Policies Zohar Barak, Asnat Berlin, Ilan Reuven Cohen, Alon Eden, Omri Porat, Inbal Talgam-Cohen
#600 How to Build Pseudorandom Unitaries in Microcrypt Aditya Gulati, Dakshita Khurana, Kabir Tomer
#601 Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MA Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara
#602 A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets Jincheng Guan, Shuai Shao, Zhuxiao Tang
#603 Reed–Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic Proofs Quang Dao, Scott Kominers, Justin Thaler
#604 A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum Clustering Karthik C.S., Euiwoong Lee, Yuval Rabani, Chris Schwiegelshohn, Samson Zhou
#605 Counterexamples to Beyond-Johnson Proximity Gaps over Binary Fields Quang Dao, Scott Kominers, Justin Thaler, Kai Zhe Zheng
#606 Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy Alexander Shekhovtsov, Georgy Sokolov, Mikhail Cherniavskii, Andrey Kupavskii
#607 Factor Closure in Noncommutative Algebraic Complexity V. Arvind, Pushkar S Joglekar
#608 The Strong Secretary Conjecture is True for Linear Matroids Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos, Jose Soto, Victor Verdugo
#609 An $n^{n+o(n)}$-Time Algorithm for the Lattice Isomorphism Problem Divesh Aggarwal, Kaijie Jiang, Zihan Li, Yinchen Liu
#610 Cube-Root Soundness Is Optimal for the Line–versus–Point Test Quang Dao, Scott Kominers, Justin Thaler, Kai Zhe Zheng
#612 Does Every Language in NP ∩ coNP Have a Subexponential-Time Algorithm? Kaiyi Zhang
#613 Pairwise Exchanges of Freely Replicable Goods with Negative Externalities Shangyuan Yang, Kirthevasan Kandasamy
#614 A Unified and Simplified Framework for Dynamic Distance-Based Graph Problems Julia Chuzhoy, Ron Mosenzon
#615 Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLL Sijin Peng, Mohsen Ghaffari
#616 Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion Xiaohong Cai, Mingyang Zhu
#617 Tilted Convexity and an Exact Offline--Online Separation Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal
#618 A classical oracle separation between QMA and QMA(2) Sabee Grewal, Saachi Mutreja, Kabir Tomer
#619 A Walk from Free Probability to Matrix Discrepancy I: Matrix Spencer Tarun Kathuria
#620 A Walk from Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Problem Tarun Kathuria
#621 Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts Sebastian Siebertz, Wojciech Wawrzyniak, Saeed Amiri
#623 Lotteries Protect Single-Item Sellers from Monopolist Intermediaries Jingyi Liu, Aviad Rubinstein, Ertem Nusret Tas, Matt Weinberg, Qianfan Zhang
#624 Optimal Shallow Circuits for Majority Victor Lecomte, Prasanna Ramakrishnan
#625 Matrix Lewis Weights: Solving Semidefinite Programs in Square Root Constraints Iterations Jonathan Kelner, Shunhua Jiang, Aaron Sidford, Lichen Zhang
#626 Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials Somnath Bhattacharjee, Rishabh Kothary, Shanthanu Rai, Shubhangi Saraf
#627 Symmetric Circuits for Matrix Multiplication Anatole Dahan, Anuj Dawar, Deepanshu Kush, Benedikt Pago
#628 Reading between the levels: new tools for the Thorup--Zwick hierarchy and their applications Shiri Chechik, Avi Kadria, Gur Lifshitz, Liam Roditty
#629 High-dimensional expanders, the sparsest cut problem, and Steurer’s conjecture Farzam Ebrahimnejad, Shayan Oveis Gharan
#630 Induced-Minor-Free Graphs Admit a Star-Based Separator of Size $\Tilde{O}(\sqrt{n})$ Arnold Filtser, Nikolai Karol, Hung Le, Florian Lehner
#631 Optimal partition rank bounds for the determinant and other multilinear polynomials Neil Krishnan, Guy Moshkovitz
#632 Beyond IP= PSPACE and QIP= PSPACE: Interactive Proofs in Arbitrary Physical Theories Kishor Bharti
#633 Optimal universal sets for submodular functions Marek Adamczyk, Richard Ueltzen, Jan Vondrák
#634 More on Correlation Bounds for Polynomials Xin Li
#635 New Algorithms for Dynamic Maximal Matching and Edge Coloring Julia Chuzhoy
#636 An EPTAS for Max-Cut on Interval Graphs Morteza Alimi, Hani Ahmadzadeh
#638 A Linear-Time Construction on S^2 Achieving a Sublinear Energy Gap on Smale's Seventh Problem Rishabh Kabra, Wim Dehaen, Andrea Karlova, Mark Hamilton, Joao Carreira, Maks Ovsjanikov, Jonathan T. Barron
#639 Lower Bounds for Preprocessing Attacks on Quantum Cryptography Fangqi Dong, Alex Lombardi
#640 Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths Yang Cao, Haoran Qi, Hanzhi Wang
#641 Constant-Overhead Injection into Quantum Codes Louis Golowich, Venkatesan Guruswami
#642 Finding a Positive Index Nash Equilibrium is PPADS-Complete Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos, Jingming Yan
#643 Near-Optimal Bounds for Sketching the Schatten Norms Lin Yang
#644 Improved Transversal Non-Clifford Gates from Cup Products Louis Golowich, Itzhak Tamo, Guanyu Zhu
#645 Dimension-Free Polylogarithmic Quantum Shadow Tomography Fernando Jeronimo, Qizhao Huang, Lenny Liu
#647 Local Distributed Computation under Crash Failures Diana Ghinea, Fabian Kuhn, Chen-Da Liu-Zhang, Zahra Parsaeian
#648 DéjàVu: Plurality Consensus by First Repetition Niccolò D'Archivio, George Giakkoupis, Frédéric Giroire, Emanuele Natale
#649 Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy Rate Xin Li
#650 Succinct Interactive Commitments and Arguments for NP from Exponentially Hard Injective One-Way Functions Jesko Dujmovic, Daniel Wichs
#651 Regret Bounds for Profit Maximization in Bilateral Trade: Learning the Best Posted-Price Mechanism Johannes Brustle, Simone Di Gregorio, Federico Fusco, Stefano Leonardi
#652 A Universal Threshold Theory for Local Properties of Random Linear Codes Vinayak Kumar, Ray Li, Jonathan Mosheiff, Gilad Shavit
#653 The Complexity of Nash Equilibrium in Network Congestion and Coordination Games Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
#654 Between CPA and CCA: Security Hierarchies for Restricted Decryption Khoa Nguyen, Willy Susilo
#655 Copyless Cost Register Automata and Algebraic Groups: An Exact Characterization for Invertible Weighted Automata Zijian Zeng, Jiayin Cao, Weinan Dai, Rui Wang, Fei Ding
#656 Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields Bin Fu, Yunhui Fu
#657 Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity Vishesh Jain, Clayton Mizgerd, Eric Vigoda
#658 Strong and Compact Policies for Submodular Markov Decision Processes via LP-Based Submodular Orienteering Lars Rohwedder, Rico Zenklusen
#659 Quasipolynomial Trace Reconstruction Arnav Burudgunte, Paul Valiant, Hongao Wang
#661 RHELIOS: Adversarially Robust Online Convex Optimization with Optimal Adaptive Regret in Banach Spaces Jean Rosemond Dora, Ladislav Hluchý
#662 FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence Patterns Matthias Lanzinger
#663 Uniform Subpower Membership for Finite Mal'tsev Algebras Asterios Gkantzounis
#664 Facility Location with Customer Incompatibilities Pengfei Wu, Zachary Friggstad
#665 Deterministic directed minimum cut via capacity-selected terminals Thomas Chen
#668 Transposition achieves OPT+O(1) in polynomial time for IID list update Clayton Mizgerd
#669 Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold Nicholas Kocurek, Shayan Oveis Gharan, Dante Tjowasi
#671 Learning Partition Trees for Nearest Neighbor Search Sanjeev Khanna, Ashwin Padaki, Erik Waingarten
#672 A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic Streams Ashwin Padaki, Krish Singal, Erik Waingarten
#673 New Gate, Weight and Wire Complexity Bounds for Sigmoid Neural Networks Jiatu Li, Daniel Reichman, Ryan Williams, Tony Wu
#674 A Linear Lower Bound for Convex Body Chasing in Every Norm Nicolas Christianson
#675 A Matrix Lee-Sidford Barrier and Faster Semidefinite Programming Zhao Song, Ruizhe Zhang
#677 The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in Three Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi, Christopher Rosin, Michael Saks, Navid Talebanfard
#678 Optimal Quantum-Classical Separations for Exact Learning Srinivasan Arunachalam, Amin Shiraz Gilani, Nikhil S. Mande
#687 The asymptotic spectrum of tensors is connected Péter Vrana, Jeroen Zuiddam
#688 The Sample Complexity of Multicalibration with an ERM Oracle Princewill Okoroafor
#689 Separating Measures by Hyperplanes Jose Correa, Svenja M. Griesbach, Elfarouk Harb, Felix Hommelsheim, Reda Jlibene, Vasilis Livanos, Eilon Solan
#690 Breaking the $2^n$ barrier for graph $k$-coloring Kevin Pratt
#691 What is Learnable in Valiant's Theory of the Learnable? Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis
#692 Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs Yali Aharon Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma
#693 A Better-than-2 Approximation for k-Median Rares-Darius Buhai, Vincent Cohen-Addad, Henry Fleischmann, Anupam Gupta, Antoni Jubés Monforte, Madhusudhan Reddy Pittu, Miltiadis Stouras, Ola Svensson, Lukas Vogl
#694 Explicit tensors beyond the linear flattening barrier Benjamin Lovitz
#695 Delegating Computation with Approximate Arithmetic: Interactive Proofs for Wizards Aritra Das, Debayan Gupta, Arup Mondal, Mihir More
#696 On Brouwer's Laplacian conjecture Pravesh Kothari, Stefan Tudose
#697 An Integrality-Gap Lower Bound of 1.2325 for Minimum Multiway Cut Dimitar Chakarov, Yury Makarychev
#699 Bourgain's Theorem for a Union of Euclidean Metric Spaces Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian
#700 Predicting Solar Power Output Using Weather-Based Machine Learning Models: A Comparative Study Sungho Kim
#701 Bethe Hessian Recovery through the Kesten–Stigum Regime Dingding Dong, Theo McKenzie
#702 A general counting and sampling Lov\'asz local lemma Vishesh Jain, Clayton Mizgerd, Huy Tuan Pham
#703 From Compensation Design to Budget-Feasible Mechanisms: A Constant Approximation for Subadditive Valuations Ioannis Anagnostides, Kshipra Bhawalkar, Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Weiqiang Zheng
#704 A deterministic $(1+\varepsilon)^n$ approximation for the permanent of a nonnegative matrix Vishesh Jain, Dingding Dong
#705 Optimal girth-dependent bounds for the Bethe approximation of the permanent Vishesh Jain, Dingding Dong
#707 The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma Vishesh Jain
#708 Pseudometric-Weighted Correlation Clustering via Spectral Preclustering Chenglin Fan, Dahoon Lee, Euiwoong Lee
#709 Predicting Resource Efficient Hamiltonian Decomposition for Continuous-Time Quantum Walk Simulations Mostafa Atallah, Rebekah Herrman, Zain H Saleem
#710 Gaussian Partitioning for Reliable Learning of Multi-Index Models Ilias Diakonikolas, Giannis Iakovidis, Daniel Kane, Mingchen Ma
#711 Adversarially Robust Streaming Algorithms for $(k, z)$-Clustering Chengzhi Guo, Shaofeng Jiang, Robert Krauthgamer, Shenghao Xie, Samson Zhou
#712 Optimal Quantum de Finetti Theorems via Argmax Rounding Fernando Granha Jeronimo, Pei Wu, Haochen Xu
#713 Superlattice methods for the shortest vector problem and discrete Gaussian sampling Minki Hhan, Jiseung Kim, Sunyeop Kim, Thijs Laarhoven
#715 An $\widetilde{O}(n^3)$-time FPRAS for the Permanent Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang
#716 Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles Boxuan Chen, Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
#717 Quadratic Probing Insertions Are $\epsilon^{-(1+o(1))}$ Time Yang S. Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu, Renfei Zhou
#718 The Sample Complexity of Multi-Class Omniprediction Joey Rivkin, Princewill Okoroafor, Michael P. Kim
#719 Pareto-optimal Non-Clairvoyant Scheduling with Predictions Ziyad Benomar, Vianney Perchet
#720 Private PCPs from Product Expansion Mitali Bafna, Nikhil Vyas
#721 An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Φ-Regret Minimization Gabriele Farina, Juan Perdomo
#722 Submodularity Is Barely Testable Diptaksho Palit, Yuichi Yoshida
#723 Listing Even Cycles Even Faster Neha Pant, Virginia Vassilevska Williams
#724 $0/1$-Polytopes with Exponentially Small Edge Expansion Xiongxin Yang
#725 Counting Linear Extensions Faster than $2^n$ Keigo Oka
#726 Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing Rishikesh Gajjala, Arindam Khan
#727 Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups Ryosuke Yamano, Tetsuo Shibuya
#728 Exponential Separation of Sign-Rank and Margin Complexity Gabriel Hart, Kaave Hosseini
#729 Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset Estimation Nick Fischer, Yael Kirkpatrick, Vassilios Nakos
#730 $\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize Sinan Oral, Supartha Podder
#731 Tensor Decomposition Beyond the Spectral Threshold Agastya Vibhuti Jha, Davide Mazzali, Jeff Xu
#732 Reed--Muller Codes are Optimal Binary Linear 3-Query LCCs Oliver Janzer, Peter Manohar
#733 Add/XNOR Chains: An NP-Complete Boolean--Arithmetic Problem at the Meet-in-the-Middle Barrier Ping Wang, Mengxin Lv, Zishen Shen, Fangguo Zhang
#734 Characterizing Local Breadth in Language Generation Jon Kleinberg, Fan Wei
#735 Nested Effective Resistance Partitions and Eulerian Sparsification Richard Peng, Sushant Sachdeva, Paul Zhang, Yibin Zhao
#736 Exact Agreement Expansion up to the Top via Non-polarity Tali Kaufman, Huy Tuan Pham
#737 Single-Variable Connectivity in Random $k$-SAT Chunyang Wang, Yitong Yin, Yixiao Yu, Yiyao Zhang
#739 A computational phase diagram for the transverse field Ising model Thuy-Duong (June) Vuong
#740 A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization Alina Ene, Huy Nguyen
#741 Improved Integrality Gap for Multicommodity Flow on Trees Elfarouk Harb
#742 The State Complexity of Block-Diagonal State Space Models Chaoyue Geng
#743 Cutting Down the Tower: Single-Exponential Envy-Free Cake Cutting Qilin Ye, Yannan Bai
#744 Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing Jiale Cheng, Ziao Wang, Lei Ying
#745 The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding Shouzhen (Bailey) Gu, Lily Wang, Aleksander Kubica
#746 A polynomial-time approximation scheme for minimum-weight decoding of topological codes Shouzhen (Bailey) Gu, Lily Wang, Aleksander Kubica
#747 Polynomial Time Algorithms for the Kadison-Singer Problem Zhao Song, Song Yue
#748 NP-Hardness and Additive Inapproximability of Deterministic Communication Complexity Serge Gaspers, Tao Zixu He, Simon Mackenzie
#749 Iterative Randomized Rounding for $k$-Median in General and Euclidean Metrics Jarosław Byrka, Yuhao Guo, Yang S. Hu, Shi Li, Yongho Shin, Phanu Vajanopath, Chengzhang Wan, Zaixuan Wang
#750 An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication Complexity Haoyu Wang, Yimeng Wang, Pei Wu
#751 Byzantine Agreement with Signature Tokens Yuval Efron, Mahimna Kelkar, Saachi Mutreja, Tim Roughgarden
#753 State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron Jianan Zhang, Shuangping Li
#754 Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth Xuan Chen, Shuangping Li
#755 Near-Optimal Gap Amplification for Nonnegative Unentangled Quantum Proofs Masayuki Miyamoto
#756 Stable and Online Algorithms for Random Matrix Discrepancy Eren C. Kizildag, Shuangping Li
#757 How Many Gaussians Does Smoothed Analysis Need? The Rank-One Barrier, Random Subspaces, and Explicit Constructions Arnav Mittal
#758 Convergent Dynamics in Second Price Autobidding Games Li Chen, Jamie Morgenstern, Yuanyuan Yang
#760 The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than 1-1/e Debmalya Panigrahi, Ian Zhang
#761 Worst-Case to Average-Case Reductions for Linear Algebra: Optimal, Simple, and General Alexander Golovnev, Satyajeet Nagargoje, Igor Shinkar, Harsimran Singh, Noah Stephens-Davidowitz
#762 Rapid mixing of quantum spin chains at any finite temperature Leeseok Kim
#763 Random-Walk Cuckoo Hashing is Efficient up to the Critical Load Threshold Yang S. Hu, William Kuszmaul, Jingxun Liang
#764 Targeted Samplers Heda Chen, Dean Doron, M. H. Ebtehaj, Roei Tell
#774 Robust and Leakage-Resilient Device-Independent Oblivious Transfer in MiniQCrypt Rishabh Batra, Zhili Chen, Rahul Jain, YaoNan Zhang
#775 An $O(1)$ Bound for the KLS Constant Zhao Song, Xinzhi Zhang
#776 A General Approach to Polynomial-Time Truncated Learning via Low-Degree Moments Andor Vári-Kakas, Manuel Wiedmer
#777 Weakly interacting fermionic Gibbs states are Gaussian mixtures and classically simulable Zhengyi Han, Yuanchen Zhao, Zi-Wen Liu
#778 Compensation Design Ioannis Anagnostides, Kshipra Bhawalkar, Chris Liaw, Aranyak Mehta, Renato Paes Leme, Yifeng Teng, Grigoris Velegkas, Weiqiang Zheng
#779 Leakage-Tolerant Computation without Leakage-Free Setup Yaohua Ma, Yifan Song
#780 Abelian Cayley High-Dimensional Expanders with Polylogarithmic Degree Songtao Mao
#781 AQUI-GuaRD: Algorithmic Safety and Concentration Bounds for Constrained Control under Adversarial PDE Dynamics Jean Rosemond Dora, Ladislav Hluchý
#782 Universal Inductive Inference of Quantum States Taiga Hiroka, Min-Hsiu Hsieh, Yuki Shirakawa
#783 Parallelizable and addressable transversal non-Clifford gates on good quantum LDPC codes Yiming Li, Zimu Li, Zhengyi Han, Zi-Wen Liu
#784 A Near-Linear Element-Kernel for d-Hitting Set Zimo Sheng, Mingyu Xiao
#785 Quantum channel tomography: optimal bounds in the near-boundary regime Kean Chen, Aadil Oufkir
#786 Non-Abelian sheaf quantum LDPC codes: good and magical Zimu Li, Fuchuan Wei, Zhengyi Han, Zi-Wen Liu
#787 Concentration on HDX: Simplified and Optimized Nirjhar Das, Max Hopkins, Arka Ray, Nathan Tung
#788 Semi-Streaming Reachability and Shortest Paths in $n^{1/3+o(1)}$ Passes Gary Hoppenworth, George Z. Li, Sepideh Mahabadi, Jakub Tarnawski
#789 Beyond Monotonicity: Stochastic Online Optimization under Semi-Bandit Feedback Tsubasa Harada, Yasushi Kawase, Hanna Sumita
#790 Subexponential Upper Bounds for 3-Restricted Matching Vector Families Divesh Aggarwal, Maciej Obremski
#791 Otter: A Provably MEV-Resilient Automated Market Maker via Surplus Redistribution Elaine Shi, Mengqian Zhang, Hao Chung, Yuhao Li
#792 A Tale of Two Walks: From Kac to KMP and Back Qian Chen, Jingcheng Liu, Minglong Qin, Leonard J. Schulman, Fang Song, Penghui Yao, Mingnan Zhao
#793 Autoregressive Distribution Learning and Universal Compression Shuichi Hirahara, Mikito Nanashima
#794 On Random Purifications of Isometries and Channels Eli Goldin
#795 Counting Paths in Time $O^*(2^k)$, with Extensions to Counting Bounded Treewidth Graphs and Multilinear Monomials Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
#796 Faster Approximation Schemes for Scheduling on Related Machines Lin Chen, Tingwei Hu, Jiayi Lian, Yuchen Mao, Guochuan Zhang
#797 Optimal Multi-Item Auctions with I.I.D. Values Boyu Liu, Zhengyang Liu, Zihe Wang
#798 Parity Decision Trees of Depth $O(4^d \log \| \widehat f \|_1)$ for Boolean Functions $f$ of $\mathbb F_2$-Degree $d$ Shengyu Zhang
#799 Exact Feasibility and Privacy Amplification for Linearly Constrained Optimization Cheng Li, Zhao-Rong Lai, Jian Weng
#800 A Prescribed-Accuracy Algorithm for Max-Weight Maximum Coverage on Bipartite Graphs with One-Sided Capacities Jiayi Lu
#801 Information Loss Is All You Need: TC^0 Pseudorandomness from Worst-Case Lattices Chen Qian
#803 Single-Exponential FPT Algorithms for Minimum Bisection and Matching Cut via a New Unbreakable Decomposition Soh Kumabe
#804 High-Multiplicity Bin Packing is FPT Tomohiro Koana, Soh Kumabe
#805 Time/Space Hardness from Lattice Problems Damiano Abram, Giulio Malavolta, Lawrence Roy
#806 Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria Jinqi Tang, Shihong Ding, Cong Fang
#807 The Price of Anarchy of Draft Auctions Huy Trung Truong, Nguyen Thach, Hau Chan, Mingyu Guo
#808 A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems Chenghua Liu, Boning Meng, Juqiu Wang
#809 Silver Rate Is (Almost) Optimal for Gradient Descent Yuhan Ye, Kaizhao Liu
#810 A Deterministic Polynomial Kernel for Odd Cycle Transversal Tomohiro Koana, Soh Kumabe
#811 Breaking the $2^n$ barrier for directed hamiltonicity Tomohiro Koana, Soh Kumabe
#812 The Query Cost of Certifying a Ranking Chaoqiang Fu, Yifan Su, Daofeng Li
#813 Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex Case Kaizhao Liu, Yuhan Ye
#814 Counting Hamiltonian Cycles in Bipartite Digraphs Deterministically in $O(1.9526^n)$ Time Tomohiro Koana, Soh Kumabe
#815 Quantum Security of XOR of Permutations via Fourier Analysis Wonseok Choi, Minki Hhan, Junyoung Jang
#816 On the Quantum Chromatic Gap II Lorenzo Ciardo, Antoine Mottet
#817 Splay trees are almost dynamically optimal Petr Chmel, Bernhard Haeupler, Richard Hladík, Michal Koucký, Antti Roeyskoe, Václav Rozhoň, Ondřej Sladký, Robert E. Tarjan
#818 Faster Cluster Decomposition with Stronger Bi-Criteria Guarantee He Sun, Yong Zhang, Yacong Zhou
#819 Explicit Edit Codes via Multicoloring Huiling Xie, Zitan Chen
#820 Primal/Dual Method for the Grothendieck Constant Steven Heilman, Chris Jones, Giulio Malavolta
#821 A Quadratic Lower Bound for Noncommutative Circuits Sophus Valentin Willumsgaard, Pratik Shastri
#822 Distinguishability Threshold for Random Geometric Graphs Zach Hunter, Aleksa Milojevic, Benny Sudakov
#823 A polynomial scaling window for random k-SAT and a proof of the satisfiability conjecture Gaia Carenini
#824 Expanding Codes with Polynomial Stretch Isaac M Hair, Amit Sahai
#827 Undirected Multiple-Unicast Network Coding and Faster External-Memory Integer Sorting Baochun Li, Zongpeng Li, Sirui Liu
#828 Wait-Free Solvability of General Tasks and a New Proof of the Renaming Dichotomy Hagit Attiya, Ami Paz
#829 Extending Tardos's Theorem to Separable Convex Quadratic Programming Bin Cui, Hanqing Li, Xupeng Miao
#830 Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal Vectors Nikolai Chukhin
#831 A Polynomial Erdős-Pósa bound for Eulerian digraphs Esther Galby, Roohani Sharma, Bart van der Steenhoven
#832 IQP circuits for 2-Forrelation Quentin Buzet, André Chailloux
#835 The Power of Bidegeneracy for Hypergraph Data Structures Marco Bressan, Stefano Clemente, Giacomo Fumagalli, Daniel Paul-Pena, C. Seshadhri
#836 Quantum group codes for non-Clifford logic: enhanced decoding, addressability and parallelizability Virgile Guemard, Jean Gasnier
#837 Exact Euclidean k-Means: Faster in the Plane, Hard Beyond It Tian Bai, Fedor Fomin, Xiaoyang Xu
#838 Computational Bounds for $f$-Routing Oren Renard
#839 Incremental All-Pairs Effective Resistance in Almost-Linear Time Gernot Zöcklein, Rasmus Kyng, Maximilian Probst Gutenberg, Gramoz Goranci, Yibin Zhao
#840 Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners Gur Lifshitz, Shiri Chechik
#841 Constant-factor approximation of MinCostCSP with a conservative majority polymorphism Marcin Kozik, Stanislav Živný
#842 A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs Kourosh Mirsohi, Sandy Irani, Michael Goodrich
#843 The Minimum Bucket Capacity for Reliable Path ORAM Yijia Chang, Man Ho Au
#844 Separating ClonableQMA and QCMA Relative to a Classical Oracle Alper Cakan, Kai-Min Chung, Wei-Hsiang Hung, Tzu-Yi Yang
#845 Best-of-Many-Worlds MMS Allocation for Chores with Sublinear Disposals Zehan Lin, Xiaowei Wu, Shengwei Zhou
#846 Estimating the Volume of a Union of Convex Bodies Eeshan Banerjee, Aranya Kumar Bal, Debabrota Basu, Sourav Chakraborty, Debarshi Chanda, Uddalok Sarkar
#847 Nearly Optimal Hardness for CVP and NCP with Preprocessing Guy Weissenberg, Giacomo Fenzi
#848 Optimal Maximum-Entropy Stationary Contention Resolution for General Matchings via a Sharp Two-Point Monomer-Dimer Inequality Yanpu Chen, Guangshuai Wang
#849 Improved Separations between Quantum and Classical Communication Complexity of Total Functions François Le Gall
#850 Some Observations in Logical Clocks in Distributed Systems Dharmendra Prasad Mahato
#851 Resolving the Worst-Case Complexity of Linear Secret Sharing Oded Nir
#852 Model Checking for Metric Extensions of Monadic Second-Order Logic Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz
#853 On the Computational Power of Geometrically Local QAC circuits Yangjing Dong, Fengning Ou, Penghui Yao
#854 A Dichotomy for Complex Boolean Holant with Binary Disequality Chenghua Liu, Boning Meng
#855 Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework Francisco Sena, Aleksandr Politov, Corentin Moumard, Massimo Cairo, Romeo Rizzi, Manuel Cáceres, Sebastian Schmidt, Juha Harviainen, Alexandru I. Tomescu
#856 Contextual Search and Bilateral Trade with a Trace-Square-Root Potential Romain Cosson, Federico Fusco, Anupam Gupta, Stefano Leonardi, Renato Paes Leme, Matteo Russo
#857 Fair and Strategyproof Facility Location in Euclidean Space Yachao Yan, Houyu Zhou
#858 Pfaffian Recognition is in coRP Priyanshu Pant, Ranveer Singh
#861 The Price of Partial Information with Switching Costs: A Complete Characterization for Feedback Graphs Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Emmanuel Esposito, Federico Fusco, Tomer Koren
#862 Consistent Submodular Maximization with Full Foresight Eric Balkanski, Paul Duetting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, Morteza Zadimoghaddam
#863 Quantum Advantage for Distributed Symmetry Breaking Maxime Flin, Longcheng Li, Jukka Suomela
#864 Cryptography from Dream Compression Liyan Chen, Jiatu Li, Abhishek Jain, Lawrence Roy
#865 Solving One of Many Instances Is Almost as Hard as Solving One Nikolai Chukhin, Alexander S. Kulikov, Ivan Mihajlin, Alexander V. Smal
#873 Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm Weiming Feng, Yixiao Yu, Yiyao Zhang
#874 On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields Tiange Li, Yinan Li, Youming Qiao, Dacheng Tao, Yingjie Wang
#876 How to Hash and Commit Real Values with Dynamic Precision Binyi Chen, Yilei Chen, Zhenghao Guan, Wenjie Li
#877 Identity Testing of Markov Chains from a Single Trajectory Jianhao Jia
#878 Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model Chandrima Kayal, Sayantan Sen, Dániel Szabó
#879 Tight Coreset Bounds for $(k,z)$-Clustering in Euclidean and Doubling Metrics Junqiu Hu, Lingxiao Huang, Jian Li, Baoduo Xu
#880 Online and Fully-Dynamic Sorting Yossi Azar, Sujoy Bhore, Devdan Dey, Debmalya Panigrahi, Or Vardi, Ian Zhang
#881 An $\widetilde O(m+n^{3/2}\eps^{-1})$ algorithm for counting spanning trees by $\ell_1$-regularized resistance Rong-Hua Li, Yichun Yang
#885 A Simple Computer-Assisted Proof of the 5/6-Bound for Real-Period Pinwheel Scheduling Hiroshi Fujiwara, Grzegorz Gutowski, Katsuhisa Ouchi, Alexander Wolff
#890 Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa
#891 Public Evidence for High-Threshold Asynchronous Distributed Key Generation: Interfaces, Leakage, and Conditional Composition Kombou Victor, Qi Xia, Jianbin Gao, Hu Xia, Befoum Stephane Richard, Brinda Leaticia Kuiche Sop
#892 Dynamic Optimality to within O(log log log n) Daniel Čech, Bernhard Haeupler, Antti Roeyskoe, Václav Rozhoň, Robert Tarjan, Sorrachai Yingchareonthawornchai
#893 Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
#894 Adaptive Sparsifier Revisited: $(1 \pm \epsilon)$-Approximate, Fast, and Simple Maximilian Probst Gutenberg, Yu-Cheng Yeh, Gernot Zöcklein
#895 The Space Complexity of Property Testing Clément Canonne, Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
#896 Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang
#897 Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov Bound Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi
#898 Improved lower bounds on the approximability of Multiway Cut using Sherali–Adams relaxations Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
#899 Quantum Fourier transform toolbox Carli Bruinsma, Pietro M. Posta, Joppe Stokvis, Dmitry Grinko, Maris Ozols
#924 Inside the Critical Window of Random 2-SAT Vlady Ravelomanana
#925 Counting over Unbreakable Decompositions: A Single-Exponential Parameterized Algorithm for Minimum Bisection Aditya Anand, Evangelos Kipouridis, Karol Węgrzycki
#926 The Fairest of Them All: Best-of-Both-Worlds Fair Leader Election Chen-Da Liu-Zhang, Elisaweta Masserova, Kelsey Melissaris, Lawrence Roy, Sophia Yakoubov
#927 A Width Hierarchy of Monotone Algebraic Branching Programs Julian Dörfler, Alexander Rogovskyy
#928 A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy
#929 Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse Aryan Mokhtari, Francisco Patitucci
#930 Incremental Approximate Vertex Connectivity via Almost-Linear Time Local Cut Algorithms Felix Adena, Monika Henzinger, Daniel Rutschmann
#931 Fully Dynamic Weighted Set Cover: Worst-Case Recourse and Update Time Sayan Bhattacharya, Ruoxu Cen, Ermiya Farokhnejad, Debmalya Panigrahi
#934 Improved Bounds on Distance Preservers Yanyu Chen, Yu Chen, Zihan Tan, Mingyang Yang
#935 On Clifford hierarchy testing and near-extremizers of noncommutative uniformity norms Zongbo Bao, Jop Briët, Davi Castro-Silva, Philippe van Dordrecht, Jonas Helsen
#936 Competitive Equilibrium for Linear Chores is CLS-complete Qian Liu, Shinuo Ma, Yixin Tao, Minji Yang, Weiqiang Zheng
#937 Flexible rigidity: Compiling generic trusted-preparation protocols into sequential device-independent protocols Amir Arqand, Srijita Kundu, Ernest Y.-Z. Tan
#939 Structured Quantum Hardness from Unstructured Assumptions Xiao Liang, Takashi Yamakawa, Chak Fai Yung
#940 Random tensor isomorphism under orthogonal and unitary actions: Smoothed and average-case analysis Jeremy Chizewer, Samuel Everett, Deven Mithal, Youming Qiao
#942 Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy Mrinalkanti Ghosh
#943 The Critical Window for Sampling and Learning-to-Sample in Spin Systems Shuchang Liu, Bingsheng Zhang, Kui Ren
#945 Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Quantum Separability Martino Bernasconi, Giulio Malavolta
#946 Optimal Alternating Regret for Online Learning and Games Yixin Tao, Weiqiang Zheng
#947 Learning Positive Linear Combinations of ReLUs in Fully Polynomial Time Ilias Diakonikolas, Jelena Diakonikolas, Puqian Wang, Nikos Zarifis
#948 Efficient Quantum Fourier Transforms For Semisimple Algebras Ben Foxman, Barak Nehoran, Yongshan Ding
#949 As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyi Huang, Danny Mittal, Sahil Singla
#950 Deterministic Fault-Tolerant Connectivity Oracles with Subqadratic Space Merav Parter, Elad Tzailk
#951 Tight Bounds for $(1+\epsilon)$-Approximation for Minimum Spanning Trees in Doubling Metrics Jan Höckendorff, Felix Hommelsheim, Christian Sohler, Di Yue
#952 Near-linear-Time Sampling of the Ferromagnetic Ising Model at the Tree Uniqueness Threshold Tianshun Miao
#953 Approximate Counting of $k$-Paths in $O^*(2^k)$ Time Tomohiro Koana
#954 Optimal Regret for Profit Maximization in Bilateral Trade Matteo Castiglioni, Anna Lunghi, Alberto Marchesi
#955 Cryptographic Guarantees for Distributed Training Under Malicious Adversaries Jean Rosemond Dora, Ladislav Hluchý
#956 Minimax Rates for Estimation of Average Treatment Effects in Observational Studies Yang Cai, Alkis Kalavasis, Katerina Mamali, Anay Mehrotra, Manolis Zampetakis
#957 Stochastic Matching with Polynomial Degree Soheil Behnezhad
#958 Towards the Impossibility of Imperfectly Complete Key Agreement in the QROM Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, Takashi Yamakawa
#959 Faster Algorithms for Minimum Degree Spanning Tree Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang
#960 Dynamic $(\Delta+1)$-Coloring with Polylogarithmic Worst-Case Update Time Maxime Flin, Mohsen Ghaffari
#961 Set-defined graph classes: $\chi$-boundedness meets tropical algebra Sarosh Adenwalla, Samuel Braunfeld, Tomáš Hons, John Sylvester, Viktor Zamaraev
#962 Rapid mixing of Gibbs samplers via quantum Dobrushin–Shlosman conditions Cambyse Rouzé, Daniel Stilck França
#963 Edit Distance Approximation: Subquadratic Factor Three and Monge Approximation Schemes Egor Gorbachev
#964 Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})\Delta$ via Hidden Hard-Core Models Xiongxin Yang
#965 Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update Time Vladimir Braverman, Prathamesh Dharangutte, Chenglin Fan, Chen Wang, Shenghao Xie, Samson Zhou
#966 Near-Logarithmic Inapproximability of Parameterized Set Cover Bingkai Lin, Xin Zheng
#967 Abelian embeddings make useful promises: approximation of detrivialised equations Tamio-Vesa Nakajima, Zephyr Verwimp, Stanislav Živný
#968 Beyond light cones: State preparation complexity in quantum spin glasses Omar Al-Ghattas, David Gamarnik, Bobak T. Kiani
#969 The Local Query Complexity of Greedy Coloring and Other Extendable Labeling Problems Zi Song Yeoh, Krzysztof Onak, Dragos-Florian Ristache
#970 Minimum Sum-of-Radii Clustering with Strong and Weak Oracles Zachary Friggstad, Mahya Jamshidian, Ali Vakilian
#971 Sources of Complexity in Multi-Agent Combinatorial Contracts Tomer Ezra, Michal Feldman, Mathieu Molina, Maya Schlesinger
#972 NP-hardness of additive approximation for generalized Turán problems Yihan Chen, Jialin He, Xihe Li, Jie Ma, Tianying Xie
#973 Constant Approximation Algorithms for Knapsack and Bin Packing for Convex Polygons Arindam Khan, Yashaswini Mathur
#974 A Unified Framework for Parameterized Approximation of Clustering Objectives via Distance Mappings Martin G. Herold, Joachim Spoerhase, Evangelos Kipouridis, Dániel Marx
#975 Sample Complexity of Multiclass Omniprediction Lunjia Hu, Haipeng Luo, Jon Schneider, Kunhe Yang
#976 Parallelism and Adaptivity in Student-Teacher Witnessing Ondřej Ježil, Dimitrios Tsintsilidas
#977 Anticoncentration of the Permanent in Ginibre Ensembles Frederic Koehler, Pui Kuen Leung
#978 Stacking Stars: Minimum-Area Packing with and without Rotation Mikkel Abrahamsen, Jacobus Conradi, Arindam Khan, Jack Stade, Sampson Wong, Shuyi Yan, Hanwen Zhang
#980 Two ReLU layers is all you need Kilian Rueß, Florestan Brunck, Christoph Hertrich, Jack Stade, Amir Yehudayoff
#981 Temporal Conductance and Bounds on the Voter Model for Dynamic Networks Tatiana Rocha Avila, Holger Dell, John Lapinskas
#982 Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy Ewan Davies, Brian Tan
#983 $K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$ Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
#984 A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Gabriele Farina, Giulio Malavolta
#985 Approximation Algorithms for Multi-Criteria Network Design Problems Mehrshad Taziki, Ali Vakilian
#986 Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially Robust Nairen Cao, Anthony Fabius, Chen Wang
#987 A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds Paul Beame, Blake Holman, Niels Kornerup
#988 The Complexity of Correlated Equilibria Beyond Normal-Form Games Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Tuomas Sandholm, Brian Hu Zhang
#989 Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds Pan Peng, Ranran Shen
#990 Marton's conjecture in polynomial time Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, Aparna Gupte
#992 A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PIT Nikolai Chukhin, Karthik Gajulapalli, Alexander Golovnev, Ivan Mihajlin
#993 Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation Alexandru Gheorghiu, Aparna Gupte, Vojtěch Havlíček, Yunchao Liu
#994 Random dimension reduction and learning symmetric properties of quantum states Angus Lowe, Xinyu Tan
#995 NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes and Variants, via Non-Archimedean Rings Venkata Gandikota, Elena Grigorescu, S. Venkitesh
#996 Parallel Edge Ranking of Trees Jeff Giliberti, MohammadTaghi Hajiaghayi, Changki Yun
#997 Algorithmic Aspects of the Fermi--Hubbard Model Ainesh Bakshi, Ankur Moitra, Xinyu Tan
#998 Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array Indexes Dominik Kempa, Tomasz Kociumaka
#999 Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism Design Chengkai Zhang, Yuhao Li, Elaine Shi, Mengqian Zhang, Lirong Xia, Qishen Han
#1000 Obfuscation via Proofs of Equivalence and Polynomial-Time Reductions to Falsifiable Assumptions Damiano Abram, Agni Datta, Archisman Dutta, Lawrence Roy
#1001 Kendall–tau Center Admits a PTAS Diptarka Chakraborty, Debarati Das, Anish Mukherjee
#1002 On Robust Promise CSPs: A Boolean Dichotomy, Sharp Quantitative Bounds, and Soft-Equality Transfer Shaowei Cai, Tao Jiang, Mengchuan Zou
#1005 Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász Theorem MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani
#1006 Privacy for Free in Efficient Agnostic Halfspace Learning Giorgio Racca, Amartya Sanyal, Vikrant Singhal
#1007 Resilient and Adversarially Robust Distributed Algorithms for Graph Connectivity N. Efe Çekirge, Amit Chakrabarti, Andrew McGregor
#1008 Polynomial Interpolation for Sherali-Adams Lower Bounds Nathan Acheampong, Ben Davis, Robert Robere
#1009 Puncturable Graph Sketches and the Complexity of Distributed Vertex Connectivity N. Efe Çekirge, Amit Chakrabarti, Purna Dutta, Andrew McGregor, Vinayak Vinayak
#1010 Exact Sum-of-Radii Clustering under Any Constant Stability Shyam Ravichandran, Lev Reyzin
#1011 Solving Linear Systems in $\tilde{O}(m n \log \frac{\kappa}{\epsilon})$ Bit Operations Jonathan Kelner
#1012 Synergies between Proof Complexity and Cryptography Halley Goldberg, Mandar Juvekar, Valentine Kabanets
#1013 Improved Tours for Stochastic ATSP via Adaptive Probing and Discrepancy Minimization Manuel Christalla, Sharat Ibrahimpur, Teng Liu
#1014 An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations Yuya Uezato, Yoshiki Nakamura
#1015 Uniform convergence at optimal rate and scale Noga Alon, Steve Hanneke, Shay Moran, Tom Waknine
#1017 Lipschitz Stable Combinatorial Auctions Mahyar Afshinmehr, Elias Koutsoupias
#1018 Improved Bounds for Online Matching with Random Edge Arrivals Yilong Feng, Haolong Li, Zonghan Yang
#1019 Quantum Advantage in Local Certification of Graph Properties Benjamin Jauregui, Masayuki Miyamoto
#1020 A Counting Lemma for Somewhat Restricted 3-APs Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer
#1021 The Complexity of Continuous Contract Design over Polymatroids Max Klimm, Paul Lippke, Philipp Warode
#1022 Breaking the Quadratic Time Barrier for Flow Sparsifiers via Schur Complement Localization Gramoz Goranci, Monika Henzinger, Ali Momeni Mohammadabadi, Harald Raecke, AR Sricharan
#1023 Approximate Counting and the Provability of Combinatorial Principles Oliver Korten, Jiatu Li, Igor Oliveira, Hanlin Ren
#1024 Faster Deterministic Distributed Matching: Breaking the Log-Squared Barrier Mohsen Ghaffari, Christoph Grunau
#1026 Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in $\ell_p$ Geometries Zhengyun Nie, Anant Shyam, Brian Bullins
#1027 Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with $k$-SUM in 2D Karl Bringmann, Ariel Kulik, Karol Wegrzycki
#1029 The Hyperclique Hypothesis is False Nick Fischer
#1031 Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
#1032 On the Cost of Set-Multilinearisation in Positive Characteristic Amik Raj Behera, Michael A. Forbes, Ramprasad Saptharishi, Sébastien Tavenas
#1033 An FPRAS for Mixed Volumes Xiaoyu Chen, Kuikui Liu
#1034 Polynomial Lower Bounds for Steiner Shortcuts via Test Functions Aaron Bernstein, Henry Fleischmann, Bernhard Haeupler, Gary Hoppenworth, Thatchaphol Saranurak
#1035 Toward Algebraic Geometry of Fixed-Parameter Tractability: Case Studies Liming Cai, Sixiang Zhang
#1037 Dictators are most informative Vu Khac Ky, Tuan Tran
#1038 Distributed LTL Synthesis under Arbitrary Message Adversaries Benedikt Bollig, Patricia Bouyer-Decitre, Matthias Függer, Dhrubajyoti Ghosh, Thomas Nowak, Nathalie Sznajder
#1039 A PTAS for the Minimum Sum of Radii Problem Fabrizio Grandoni, Anupam Gupta, Jatin Yadav
#1040 From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding Zhongxia Shang, Daniel Stilck Franca
#1041 On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages Marshall Ball, Peter Crawford-Kahrl, Vladimir Podolskii, Morgan Prior
#1042 A simple proof of rapid mixing on random regular graphs beyond uniqueness Andreas Göbel, Matthew Jenssen, Marcus Michelen, Marcus Pappik, Will Perkins, Leon Schiller
#1043 Top-Down Lower Bounds for All Depths Oliver Korten
#1044 QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators Édouard Bonnet, Yeonsu Chang
#1045 Tight Depth Lower Bounds for Stretch Amplification Oliver Korten
#1046 Progress on AC0[2]-Frege Lower Bounds Yaroslav Alekseev, Svyatoslav Gryaznov, Toniann Pitassi, Robert Robere, Alexander Shekhovtsov, Iddo Tzameret
#1047 Stability Meets Kernelization: Algorithmic Extensions of the Lovász and Erdős–Goodman–Pósa Theorems Fedor V. Fomin, Petr A. Golovach, Sergei Khargeliia, Danil Sagunov, Kirill Simonov
#1048 Robust Shattering Arguments Peter Davies-Peck, Mohsen Ghaffari, Magnús M. Halldórsson, Yannic Maus, Alexandre Nolin
#1049 Randomized query complexity can beat certificate complexity Shalev Ben-David, Robin Kothari
#1050 Fast mixing of the SYK model at high temperatures Yiyi Cai, Yongtao Zhan, Alexander Zlokapa
#1051 Robust Forecast Aggregation via Additional Queries Mary Monroe, Bo Waggoner, Rafael Frongillo, Eric Neyman
#1052 NP-Hardness of Coloring $2$-Colorable $3$-Uniform Hypergraphs with $\tilde{\Omega}(\sqrt{\log \log n})$ Colors Amey Bhangale
#1053 On the Power of Determinism in Multi-Item Auctions Yiannis Giannakopoulos, Johannes Hahn
#1054 Tight Bounds for k-Median++ and Improved Bounds for k-Means++ David Naori, Haim Kaplan
#1055 Counterexamples to the Strong Roberson Conjecture Arnar Kristjánsson
#1056 Search and Verification for Strategyproof Facility Location on Metric Graphs Krzysztof Rogowski, Marcin Konrad Dziubiński
#1057 Spatial sorting and the geometry of lattice spin systems at fixed magnetization Dana Randall, Jacob Calvert, Shunhao Oh
#1058 Agnostic Product Mixed State Tomography via Robust Statistics Alvan Arulandu, Ilias Diakonikolas, Daniel M. Kane, Jerry Li
#1059 Genetic Algorithms with Optimization Guided Operators Anna Brandenberger, Ilan Doron-Arad, Elchanan Mossel
#1060 Maximal Isolating Vertex Cuts and Shredders: Structure and Applications Olivier Fischer, Sorrachai Yingchareonthawornchai
#1061 Sampling Tools and the Power of AC0 Artur Riazanov, Emanuele Viola
#1062 Mortality Is Undecidable for 2 × 2 Integer Matrices Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu
#1065 The Geometry of Sapience: Polymeric Geometry and Gauge Dynamics on the Zeta Critical Line Michael Sobolewski
#1066 Adaptivity Gaps for Influence Maximization: Percolation and Depletion Gabriel de Azevedo, Ulysse Hennebelle
#1067 Exponential quantum speedup for F_3^n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu
#1068 Sublinear-Time Algorithms on Massive Data Streams Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal, Yinzhan Xu
#1069 NP-hardness for Bipartite Colorings up to the Maximum Degree Andreas Galanis, Heng Guo, Yuchen He, Daniel Stefankovic, Eric Vigoda
#1070 Concentration from Product Moments via an Additional Element of Randomness Michael Saks, Aravind Srinivasan, Renata Valieva
#1071 Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator Guy Goldberg, Tom Gur, Sidhant Saraogi
#1072 A Faster FPTAS for Weighted Completion Time Scheduling Karl Bringmann, Anita Dürr, Karol Węgrzycki
#1073 On the pseudorandomness of simple quantum processes Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba
#1074 Local-to-Global Theorems Based on Cones with Applications to Graph Coloring Anqi Li, Shayan Oveis Gharan
#1075 Improved Exact and Approximate Quantum Fourier Transforms from Multiplication Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh
#1077 Query-optimal quantum simulation of Lindblad evolution Chunhao Wang, Christopher Ye
#1078 Efficient Robust Learning at the Information-Theoretic Limit Adam Klivans, Konstantinos Stavropoulos, Sergei Tikhonov, Arsen Vasilyan
#1079 The Stretch Factor of Planar Delaunay Triangulations Is Nearly Determined Guanlin Mo, Kangke Cheng, Hu Ding
#1080 Robust Mean Estimation Under Strong Double Corruption: Near-Linear Time and Sub-Gaussian Rate Maryam Aliakbarpour, Yuhan Liu, Junze Yin
#1082 Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth Jakob Greilhuber, Dániel Marx, George Osipov, Marta Piecyk, Paweł Rzążewski, Stanislav Živný
#1083 Pattern Matching with Edits in $\tilde{O}(n+k^3 \cdot n/m)$ Time Tomasz Kociumaka
#1084 Semi-Streaming Matching in a Single Pass II: Greedy is Optimal Sepehr Assadi, Max Jiang, Mars Xiang
#1085 Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem Mark Bun, Joao F. Doriguello, John Kallaugher, Nadezhda Voronova
#1086 Linear-length cycles in the supercritical percolated hypercube Michael Anastos
#1087 Optimal stabilizer testing and learning with limited quantum memory Srinivasan Arunachalam, Louis Schatzki
#1088 Universality in random graphs via optimal linking systems: trees and beyond Asaf Cohen Antonir, Lyuben Lichev, Maksim Zhukovskii
#1089 Randomized Greedy MIS is Fast at Every Node Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović, Srikkanth Ramachandran
#1090 Parallel Batch-Dynamic Maximal Independent Set Guy Blelloch, Andrew C. Brady, Laxman Dhulipala, Jeremy Fineman, Jared Lo
#1091 Square-root queries can help Eric Ma, Ewin Tang
#1092 Removing Spanning Trees Better Than Nash-Williams Nathan Klein, Neil Olver, Zi Song Yeoh
#1093 The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients Argyrios Deligkas, Michail Fasoulakis, Stavros Ioannidis
#1094 Price of Ignorance in Pairwise-Independent Prophet Inequalities Shaza Abdallah, David Wajc
#1095 Achieving the Optimal Abstention Rate for Learning with Distribution Shift Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
#1096 Tight Release Schedules under Distribution Shift Jing Wang
#1098 Maximum Cardinality Matching in $n^{2+o(1)}$ Time George Z. Li, Jason Li, Junkai Zhang
#1099 A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five Xiaoyu Chen, Kuikui Liu
#1100 Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $\beta \le \tfrac{1}{2} + \eps$ Mathews Boban, Anqi Li, Shayan Oveis Gharan
#1101 Bellman-Ford in Almost-Linear Time Isaac M Hair, George Z. Li, Jason Li, Junkai Zhang
#1102 Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry Leo Zhou, Noah Shutty, Mark Sellke, Stephen Jordan
#1103 Multivariate Resultants: Complexity and Applications to Real Feasibility Gorav Jindal, Bhargav C S, Himanshu Shukla, Radu Curticapean
#1104 Nearly Optimal Polynomial Time Transformation from Non-private to Private Correlation Clustering Alma Ghafari, Mina Dalirrooyfard, Slobodan Mitrović
#1105 New Lower and Upper Bounds for the Grothendieck Constant Rahul Saha, Alan Li, Anton Xue, Swarat Chaudhuri, Adam Klivans, Pravesh K. Kothari, Raghu Meka
#1106 Efficient Agnostic Learning of Tensor Network States Matthias Caro, Natalie McHugh, Sergii Strelchuk
#1108 On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten–Stigum Ferenc Bencs, Brice Huang, Daniel Lee, Kuikui Liu, Guus Regts
#1109 A Complete Characterization of Eventually Evasive Binary Patterns Simone Faro, Francesco Pio Marino, Arianna Pavone
#1110 Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel, Yunya Zhao
#1111 Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani
#1112 Optimal Sub-Gaussian Mean Estimation in Low Dimensions Jasper C.H. Lee, Suraj Mathashery, Paul Valiant, Kun Wang
#1113 A Constant-Factor Approximation for Capacitated Facility Location with Outliers Rajni Dabas
#1114 Bipartite Matching is in NC Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Thomas Thierauf
#1115 A Near-Logarithmic Approximation for All-or-Nothing Multicommodity Flow Zijian Zeng, Jiayin Cao, Weinan Dai, Rui Wang, Yuhao Liao
#1116 Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams Elena Gribelyuk, Honghao Lin, Xin Lyu, Mahbod Majid, David P. Woodruff, Huacheng Yu, Samson Zhou
#1117 Minority Dynamics with Small Samples George Giakkoupis, Dimitrios Los, Thomas Sauerwald, Isabella Ziccardi
#1118 Optimal Approximation Algorithms For Satisfiable Ordering CSPs Yury Makarychev
#1119 Smoothed Analysis for Distributed MIS Dipan Dey, Fabien Dufoulon, William K. Moses Jr., Gopal Pandurangan
#1120 Asymptotically Good Quantum Locally Testable Codes William Gay, Fernando Jeronimo
#1121 Non-manipulability and Approachability Beyond Two-Player Games Natalie Collina, Elijah Fullerton, Jingyi Liu, S. Matthew Weinberg
#1122 Existence of the Core in Approval-Based Committee Elections Patrick Becker, Matthias Greger, Dominik Peters
#1123 Approximation Algorithms for Satisfiable Phylogenetic CSPs Yury Makarychev
#1124 A Minimax Analysis of the Last Iterate of the SubGradient Method in Finite Dimension Guglielmo Beretta, Tom Cesari, Roberto Colomboni, Andrea Paudice
#1125 Approximate Polynomial Satisfiability is in the Counting Hierarchy Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
#1126 Small classes have linear neighbourhood complexity John Sylvester, Viktor Zamaraev, Maksim Zhukovskii
#1128 The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization Andreas Kontogiannis, Ioannis Panageas, Vasilis Pollatos
#1129 Connectivity in a New Bounded-Space Dynamic Model Bardiya Aryanfard, Monika Henzinger, John Kuszmaul, Jakob Nogler, Virginia Vassilevska Williams
#1130 Faster Polynomial Factorization over Finite Fields via Batched Modular Composition Zhenyu Xiong, Mingsheng Wang
#1131 Dynamic LZ77: No Space for Improvement Itai Boneh, Dvir Fried, Shay Golan, Matan Kraus
#1132 High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear Regression Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
#1134 Entanglement Lower Bounds for Symmetric Quantum Circuits Davi Castro-Silva, Ryan Dancy, Sergii Strelchuk
#1135 Even Coarse Matching Estimates Require Nearly Linear Streaming Space Gillat Kol
#1136 Good Quantum Locally Testable Codes from Product Expansion Mitali Bafna, Anqi Li, Quynh T. Nguyen
#1137 Quasipolynomial 3-Coloring of Diameter-2 Graphs via Domain Reduction from Nogoods Philip Whittington
#1138 Additive $\Omega(\log^* OPT)$ Gap for Bin Packing with Three Items per Bin Ilan Doron-Arad
#1139 Almost Every 3-Uniform Hypergraph is Class 1 Asaf Ferber, Marcelo Sales, Mason Shurman, Arnab Chaterjee
#1140 The Exact Online Threshold for the Asymmetric Binary Perceptron Sunghyeon Jo, Taekyun Lee
#1141 One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential Search Michal Feldman, Hu Fu, Bo Peng, Zhihao Gavin Tang
#1148 Pretty good shadow tomography Sabee Grewal, Angelos Pelecanos, Jack Spilecki, Ewin Tang, John Wright
#1150 Near-Linear Estimation of Network Unreliability Mu-Xia Sun
#1151 The Power of Recruiting the Smaller Side: Two Additional Traders Suffice in Two-Sided Markets Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang, Mingfei Zhao
#1152 Functional inequalities from the fundamental limits of Bayesian estimation Shuchen Li, ILIAS ZADIK
#1153 Resolution Lower Bounds versus the Weak Pigeonhole Principle Noel Arteche
#1154 Exact Universality of Online Discrepancy Sunghyeon Jo, Taekyun Lee
#1155 Linear Hashing Is Poissonesque Vinayak Kumar
#1156 Beyond the Bochner Method: Optimal Spectral Gaps for Block Dynamics of Spin Systems like the O(N) Model Jonathan Leake, Anqi Li
#1157 Fidelity Estimation to a Known Quantum State Is Nearly Quadratic in the Smaller Rank Gye Jin Lee, Sunghyeon Jo
#1158 Weighted Set Cover with Constant Worst-Case Recourse: From Exponential to Best-Known Update Time Kaustav Paul, Shay Solomon
#1159 Some algebraic and geometric computations in CH via Chow forms Robert Andrews, Abhibhav Garg, Rafael Oliveira, Éric Schost
#1160 A Tight $ \widetilde\Omega (\sqrt m) $ Information-theoretic Lower Bound for Randomized Online Set Cover Ilan Doron-Arad, Joseph (Seffi) Naor
#1161 A dimension-free bound for the isoperimetric constant of unconditional log-concave measures Pierre Bizeul, Dan Mikulincer, Ilias Zadik
#1162 Better Upper Bounds for Square-Root-Sum and Straight-Line Program Positivity Alex Meiburg, Eric Allender, Markus Bläser
#1163 Improved Approximations for Two-Edge-Connected and Two-Vertex-Connected Spanning Subgraphs Afrouz (new email) Jabal Ameli
#1164 Linear-Time Encodable Quantum Codes near the CSS GV Bound Rachel Yun Zhang
#1165 Dimension-Free $\ell_2^2$-Sampling Algorithms for Eigenvalue Estimation Nicolas Menand, Erik Waingarten
#1166 On the VC Dimension of Autoregressive Linear Threshold Functions Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
#1167 Language Generation Beyond Adversarial Examples Debmalya Panigrahi, Fan Wei, Ian Zhang
#1168 Estimating a Transition Point from Gibbs and Ground States Yuhao Cai, Zhenzhang Li
#1169 Merkle Trees Minimize Verifier Complexity in the ROM Miranda Christ, Oliver Korten, Tal Malkin, Noam Mazor, Shyamal Patel
#1170 Better Approximation for Sparsest Cut Oracles with Balance Guarantees Robin Münk, Monika Henzinger, Harald Räcke
#1171 Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed--Solomon Codes Fernando Granha Jeronimo
#1172 Online Shadow Tomography Matching the Classical Bounds Sitan Chen, Ryan O'Donnell, Angelos Pelecanos, John Wright
#1173 Improved Quantum Query Bounds for Boolean Matrix Product Verification Amin Shiraz Gilani, François Le Gall, Xingyu Zhou
#1174 An FPRAS for Counting Common Bases of Two Matroids Xiaoyu Chen, Kuikui Liu
#1175 Combinatorial Bernoulli Factories with Polynomially Many Coins Rad Niazadeh, Renato Paes Leme
#1176 Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices Daniel Spielman, Xifan Yu
#1177 Finding Stationary Points under Higher-Order Smoothness: Trapping Algorithms and First-Order Lower Bounds Huanjian Zhou, Masashi Sugiyama, Taiji Suzuki
#1178 Finding full immersions is fixed-parameter tractable in labeled tour graphs Hadas Barabash, Jim Geelen, Rose McCarty, Caleb McFarland, Paul Wollan
#1180 Polytope Sampling at the Speed of Isoperimetry Anming Gu, Bobby Shi, Kevin Tian, Hubert Yang
#1181 The sum-of-squares complexity of linear-algebraic principles Dmitriy Kunisky, Xifan Yu
#1182 Free-Probabilistic State Evolution and Random Matrix Discrepancy August Chen, Ahmed El Alaoui
#1183 Gross Substitutes Welfare in Random Order Renato Paes Leme, Martin Pal, Neel Patel
#1184 Constant-Factor Approximation for Capacitated Clustering\\in Low Dimensions with $(1+\varepsilon)k$ Centers Kangke Cheng, Guanlin Mo, Hu Ding
#1185 Geometrically Constrained Learning II: Agnostic Proper Learning of Lipschitz Functions Jane Lange, Cassandra Marcussen, Arsen Vasilyan
#1186 Approximation and Hardness in Optimization Games Erik Jahn, Aaron Koolyk, Rafail Ostrovsky, Yuval Rabani, Leonard Schulman
#1187 A Few Experts Suffice: Near-Optimal (Private) Online Learning with Limited Subscriptions Hilal Asi, Vitaly Feldman, Satyen Kale, Tomer Koren, Mihir Singhal, Kunal Talwar
#1188 Homomorphism Indistinguishability Beyond Graphs: Relational Weisfeiler--Leman and Hypertree Width Panagiotis Aivasiliotis, Hubie Chen, Andreas Göbel, Matthias Lanzinger, Marc Roth, Markus Schneider
#1189 List Coloring Uncrowded Hypergraphs at the Shattering Threshold Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo
#1190 Propose-Filter-Release: Scaling Noise to Typical Sensitivity via Private Filtering Moshe Shenfeld, Eliad Tsfadia, Katrina Ligett
#1191 On the Power of Polynomial Calculus over Non-Boolean Domains Jonas Conneryd, Yassine Ghannane, Jakob Nordström, Shuo Pang, Kilian Risse, Dmitry Sokolov
#1192 Burnside Problems for Matrix Semigroup Quotients with Applications to Border Complexity Roland Guttenberg, Nathan Lhote, Mahsa Shirmohammadi, James Worrell
#1194 Global Sinkhorn Convergence and Spectral Stability of Matrix Scaling Kun He
#1195 A (4m - 5)-Competitive Deterministic Algorithm for Online Transportation Aditya Anand, Jonathan Conroy, Ian DeHaan, Gary Hoppenworth, Chaitanya Nalam, Milind Prabhu
#1196 Pseudorandom Unitaries from a Random Permutation and One Layer of Single-Qubit Gates Jiachen Shen, Hui Zhong
#1197 Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning Julian Asilis, Shaddin Dughmi, Vatsal Sharan, Alec Sun, Shanghua Teng, Chang Wang
#1198 Replicable Parity Learning: Cubic Sample Complexity and a Geometric Characterization Jiachen Shen, Hui Zhong
#1199 XOR Lifting for One-Query Hybrid Algorithms and the Complexity of AND–OR Trees Jiachen Shen, Hui Zhong
#1201 Robust Analysis of First-Price Auctions with Large Supply Jason Hartline, Anant Shah, Matthew vonAllmen
#1202 Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the log n Barrier Sam Hiken, Nicole Wein
#1203 Sharp Second-Order Thresholds for Random Algebraic Coverage Tenghui Lin
#1204 SNARGs and ABE for Uniform Computations via Lattice Encodings Hoeteck Wee, Daniel Wichs, David J. Wu
#1205 Tight Bounds for Sublinear Metric Steiner Tree Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, Ali Vakilian
#1206 A sharp threshold for Kawasaki mixing in a fixed-magnetization SOS model Dana Randall, Dhanush Ramadas Giriyan, Andrea Richa
#1207 Hardness of Counting Orderings: Taking Gadget Amplification to the Limit Marcelo Arenas, Maria Alejandra Schild, Bernardo Subercaseaux
#1208 Quadratic Extractors Gautam Chandrasekaran, Jesse Goodman, David Zuckerman
#1209 Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way Permutation Frédéric Dupuis, Rémi Ligez, Khaireddine Medhioub, Louis Salvail, Louis-Charles Thibodeau
#1210 Near-Cubic Gate and Near-Quartic Wire Lower Bounds for SYM ◦THR Circuits Dev Nag
#1211 Flow-Optimal Separators for Minor-Free and Induced-Minor-Free Graphs in Linear Time via Follow the Regularized Leader Hung Le, Jack Spalding-Jamieson
#1212 The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear Codes Scott Duke Kominers, Justin Thaler, Kai Zhe Zheng
#1214 Error accumulation in reverse diffusion with an imperfect score: beyond path-space analyses George Giapitzakis, Ankur Moitra, Andrej Risteski, Dhruv Rohatgi
#1215 Proper Agnostic Learning of Two Balanced Product Distributions from Prefix-Conditional Samples Manoj Saravanan
#1216 A Cheeger Inequality for Hypergraphs and Its Applications Raj Kamal, Amitabha Bagchi
#1217 Dynamic Approximate Text Indexing Panagiotis Charalampopoulos, Jonas Ellert, Jakub Radoszewski
#1218 Real-to-Integer Reduction for All-Pairs Shortest Paths Nick Fischer, Adam Polak, Jonas Schmidt
#1220 Quantum algorithms for stochastic nonlinear differential equations Sergey Bravyi, Adam Byrne, Mykhaylo Zayats, Sergiy Zhuk, Alexander Zlokapa
#1222 The Complexity of Unpredictability Aryan Agarwala, Dani Dorfman
#1223 Data-Dependent Probability Estimation via Sample Amplification Vitaly Feldman, Satyen Kale, Mahbod Majid, Kunal Talwar
#1224 Finding Hypercliques Faster Than Brute Force Josh Alman, Baitian Li, Neha Pant, Kevin Pratt, Ryan Williams
#1225 A mixing time method for estimating the sample complexity of quantum state discrimination Juntai Zhou, Felix Leditzky
#1226 Kadison--Singer in Deterministic Polynomial Time Ekene Ezeunala, Haotian Jiang
#1227 Optimal tomography of bosonic and fermionic Gaussian states Senrui Chen, Marco Fanizza, Filippo Girardi, Ludovico Lami, Francesco Anna Mele, Michael Walter, Freek Witteveen
#1228 Complexity of Autobidding Equilibria in GSP Sponsored Shopping Kristoffer Arnsfelt Hansen, Yuhao Li, Xinhao Nie
#1229 Scheduling Jobs to Maximize Minimum Fractional Completion Kunal Agrawal, Sanjoy Baruah, Gregory Kehne, Jubayer Nirjhor, Kei Rockwell, Nicole Wein
#1230 Quantum Copy Complexity of Testing Monotonicity and Other Properties Preksha Naik
#1231 Testable Sanitization via Boundary Geometry Yang Cai, Katerina Mamali, Katerina Sotiraki, Zihan Yu, Manolis Zampetakis
#1232 RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing Games Bhaskar Ray Chaudhury, Jugal Garg, Xin Huang, Eklavya Sharma
#1233 Multiplying matrices via polynomials: operational asymptotic spectrum barrier Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam
#1234 Correlated Group Actions: Founding Cryptography on S4 and Sn Donald Beaver
#1235 Quadratic Statistical Randomized Encoding for All Functions Benny Applebaum
#1236 Packing Bins in the Euclidean Plane: An Almost-Optimal Approximation for Unsplittable Capacitated Vehicle Routing Jannis Blauth, Fabrizio Grandoni, Bence Mátravölgyi, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
#1237 Near-Optimal Compressed Algorithms and Data Structures by Eliminating Recursive Substructures Rajat De, Dominik Kempa
#1238 Fractional colorings of $K_r$-free graphs with local demands Ewan Davies, Abhishek Dhawan, Abhishek Methuku, Huy Nguyen, Jaehyeon Seo
#1239 The Communication Complexity of Verifying Distribution Properties Tal Herman
#1240 Subgaussian Vector Balancing by an Ising Model Heng Guo, Daniel Spielman, Xinyuan Zhang
#1241 An Explicit 4n−O(log(n)) Size Lower Bound against General Boolean Circuits Om Swostik Mishra, Rahul Santhanam
#1242 Parallel Hierarchical Agglomerative Clustering in Low Dimensions MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher, Kishen N Gowda, Ellis Hershkowitz, Rajesh Jayaram, Jakub Łącki
#1243 Optimal Dynamic Strings in Compressed Space Anouk Duyster, Tomasz Kociumaka, Hanna Komlós
#1244 A Complete Hierarchy of Local Lemmas Dimitris Achlioptas, Konstantinos Kritharidis, Kostas Zampetakis
#1245 XOR Functions and Beyond in the Random Query Model Sumegha Garg, Janani Sundaresan, Santhoshini Velusamy
#1246 The Optimal Sample Complexity of Multiclass and List Learning Chirag Pabbaraju
#1247 TFNP in the Random Oracle Model Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten, Daniel Mitropolsky, Toniann Pitassi, Artur Riazanov, Dmitry Sokolov, Tianqi Yang, Weiqiang Yuan
#1248 A General Technique for Metrical Task Systems with Action Predictions Júlia Baligács, Christian Coester, Alexa Tudose
#1249 Settling the Approximability of Submodular Facility Location Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
#1266 Approaching Optimality for Dense Bipartite Matchings Chenxin Dai, Richard Peng, Daniel Sleator, Alicia Stepin, Junzhao Yang
#1267 Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics Leon Schiller
#1268 Mutual Correlated Agreement and List-Decoding: Improvements and Separations Ignacio Manzur
#1269 Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT Steven Heilman
#1270 Fast Approximation Algorithms for Minimizing Network Unreliability Mu-Xia Sun
#1271 Approximate Syzygies of Smoothed Polynomials and Applications Aditya Bhaskara, Anxin (Bob) Guo, Tanmay Sinha, Vaidehi Srinivas, Aravindan Vijayaraghavan
#1272 Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets Chen-Yu Wei
#1273 A Hitting Set Lemma for HDX \& Applications Mitali Bafna, Dante Tjowasi
#1274 On the Role of Geometry in Solving Variational Inequalities Ioannis Anagnostides, Ioannis Panageas, Jingming Yan
#1275 Fully Dynamic Connectivity in $O(\log^3 n)$ Worst-Case Update Time Valerie King, Quanquan Liu, Zeyu Nie
#1276 Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNP Rahul Ilango, Alex Lombardi, Yaxin Tu
#1277 Tight Low-Diameter Decompositions and Tree Embeddings in Partially Dynamic Graphs Ioannis Dorkofikis, Maximilian Probst Gutenberg
#1278 A Note on a Result of Chen Li: the Thinning Problem via the Kernel Method Xuan Fang, Tianyu Wang
#1279 Comparison is All You Need: Settling the $t$-wise independence of AES Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan
#1280 Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf Codes Hadas Zeilberger, Jack O'Connor, Tom Gur, Nicholas Spooner
#1281 Fast Minority Dynamics with $\Theta(\log^2 n)$-Size Samples Petra Berenbrink, Dhanush Ramadas Giriyan, Thorsten Götte, Andrea Richa
#1282 A Two-regime Khintchine Inequality and an Improved Bound on the Degree-1 Fourier Weight for Linear Threshold Functions Xuan Fang, Tianyu Wang
#1283 Nash Equilibria, Variational Inequalities, and Fixed Points: Beating Brute Force via Smoothed Analysis Idan Attias, Yuval Dagan, Constantinos Daskalakis, Rui Yao, Manolis Zampetakis
#1284 Fine-Grained Proof Complexity for Elementary Arithmetic in Extended Frege Andrew Krapivin, Jiatu Li, Elaine Shi
#1285 A Complete Characterization of Central String Queries in Compact Space Dominik Kempa, Tomasz Kociumaka
#1286 Lossless Hardness Condensation in Deterministic Communication Complexity Simon Mackenzie
#1287 Learning CNF Formulas with Uniform Random Solutions and Membership Queries Weiming Feng, Yixiao Yu, Yiyao Zhang
#1288 Differentially Private Verification of Distribution Properties Elbert Du, Cynthia Dwork, Linjun Zhang, Pranay Tankala
#1289 Proof of Quantum Work with Classical Verification Mohammed Barhoush
#1290 The Price of Agreement in Secure Multiparty Computation Ran Cohen, Pouyan Forghani, Juan Garay, Vassilis Zikas
#1291 Non-Interactive Network Sum-Secure Computation Yang Bai, Xuan Guang, Lizhi Wang
#1292 Transparency in Team Contracts Paul Duetting, Yingkai Li, Inbal Talgam-Cohen, Jinzhao Wu
#1293 Optimal Online Joint Replenishment with Linear Delays Júlia Baliagács, Raymond Chang, Christian Coester
#1294 Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz--Petrov Generalization Shiri Sivan
#1295 Counterexamples to EFX for Submodular and Subadditive Valuations Hannaneh Akrami, Simon Mackenzie, Alexander Mayorov, Kurt Mehlhorn, Shreyas Srinivas, Mashbat Suzuki, Christoph Weidenbach
#1296 Linear-time erasure recovery for quantum expander codes Anirudh Krishna, Christopher Pattison
#1297 No size-preserving amplification with quantum advice Shih-Han Hung, Han-Hsuan Lin
#1298 Multi-Selection Pandora's Box with Nonobligatory Inspection: A PTAS and a Structural Separation Hedyeh Beyhaghi, Tianyang Han, Ahmed Luqman
#1299 Encoding orders and trees in real-valued functions C. Terry, G. Conant
#1301 Low-Temperature Sampling via Equilibrium Disagreements Andreas Galanis, Daniel Stefankovic
#1302 Efficient Algorithms for Approximately Counting Bipartite Independent Sets in Low Threshold Rank Graphs Charlie Carlson, Alexandra Kolla
#1303 Minimizing Key Schedules for Key-Alternating Ciphers Christof Beierle, Wonseok Choi, Minki Hhan, Ashwin Jha, Sunyeop Kim
#1304 Encrypted Fixed-Point Multiplication in Quasilinear Complexity Jung Hee Cheon, Junho Lee
#1305 Santa Claus and Weighted Nash Social Welfare with Subadditive Valuations Yuhang Chen, Yuda Feng, Weijiang Hu, Shi Li, Ruilong Zhang
#1306 The CNF Encoding Complexity of Boolean Functions Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux
#1307 Faster Solvers for Sparse Systems with Large Spectral Outliers Yang P. Liu, Hoai-An Nguyen, Richard Peng, Junzhao Yang
#1308 Posterior Sampling in Gaussian Mixture Models Beyond the Clusterability Threshold Syamantak Kumar, Purnamrita Sarkar, Kevin Tian, Yusong Zhu
#1309 Polylog Pairwise Poise: Approximating Multicommodity Multicast Rhea Jain, Aidin Niaparast, R. Ravi
#1310 An Exponential Top Fan-In Hierarchy for Border Depth-4 Circuits Anakin Dey, Pranjal Dutta, Zeyu Guo
#1311 The Necessity of Elias Codes in the Global Clock Model Kuowen Chen, Shengquan Du, Tsvi Kopelowitz, Seth Pettie, Ben Plosk
#1312 On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query Complexity Samruddhi Pednekar, Supartha Podder
#1313 A Quasipolynomial Algorithm for $\ell_\infty$ Contractions Ashkan Soleymani, Gabriele Farina
#1314 Distribution-Robust Halfspace Testing Xi Chen, Renato Ferreira Pinto Jr., Nathaniel Harms, Rocco A. Servedio
#1315 Hardness of Approximation for Semialgebraic CSPs: Every Geometric Semialgebraic CSP is Approximation Resistant Dionysis Arvanitakis, Vaggos Chatziafratis, Konstantin Makarychev
#1316 An Efficient Minimax-Optimal Algorithm for Adversarial m-Set Bandits Francesco Bacchiocchi, Tommaso Cesari, Roberto Colomboni
#1317 Optimal Communication for Distributed Sparse Histogram Aggregation Fangwei Ye, Yijun FAN
#1318 d-DNNF is Not Polynomially Closed Under Negation Marcelo Arenas, Oliver Broadrick, Vincent Liew, Guy Van den Broeck
#1319 The Computational Cost of Agreement in Correlated Sampling Rupkatha Hira, Moshe Noivirt, Jessica Sorrell, Eliad Tsfadia
#1320 Tight Query Depth of Recursive Randomized Greedy MIS Slobodan Mitrović, Wen-Horng Sheu
#1321 On derandomizing the line-point low-degree test Mrinal Kumar, Swastik Kopparty, Madhu Sudan, Prahladh Harsha, Ramprasad Saptharishi
#1324 Online Beck--Fiala Down to Logarithmic Sparsity Dylan Altschuler, Konstantin Tikhomirov
#1325 Efficient classical simulation of Fermi-Hubbard models with Kramers symmetry Chaithanya Rayudu, Jun Takahashi, Ojas Parekh, Andrew Zhao
#1326 Rounding, Ranges, and Exact Sample-Removal Audits for Least Squares Cong Xu, Xinwei Gao, Jinglan Hu
#1327 Nearly Optimal Submodular Sparsification, with and without Cardinality Constraints Zhengting Bao, Dongrun Cai, Xue Chen, Yuchen He, Chihao Zhang
#1328 Does Witness Indistinguishability Require Cryptography? Gal Arnon, Noam Mazor, Rafael Pass, Jad Silbak
#1329 $(1+\epsilon)$-Distortion Spanning Tree Covers of Minor-Free Graphs with Size $O(\log \log n)$ Willem Fletcher, Arnold Filtser, Ellis Hershkowitz, Lazar Milenković
#1330 An Improved Streaming Algorithm for Exact Pattern Matching Paweł Gawrychowski, Wojciech Janczewski, Ce Jin, Jelani Nelson
#1331 Get Permanent Results Faster by Counting Stars Radu Curticapean
#1332 Succinct arguments for QMA in Microcrypt Baocheng Sun, Zihan Hu
#1334 Quantum State Search with Classical Interactive Advice Mohammed Barhoush
#1335 Initialization with Exponentially Fewer Bits Dominick Banasik, Varsha Dani, Thomas P. Hayes
#1336 Balanced Fair Division Benjamin Cookson, Jakob de Raaij, Max Dupre la Tour, Nisarg Shah
#1337 Counting and Sampling by Local Repair: From the Lovász Local Lemma to Random k-SAT Dimitris Achlioptas
#1338 Efficient Error Amplification for Sorting and Orthogonal Vectors Ian Mertz, Michal Koucký, Ninad Rajgopal
#1339 Fair and Efficient Balanced Allocations for Additive Valuations Benjamin Cookson, Nisarg Shah, Paritosh Verma
#1340 Truthful-in-Expectation Mechanism with Constant Maximin-Share Guarantee Mengfan Ma, Biaoshuai TAO, Fangxiao WANG
#1341 Exploring the Tractability Frontier of Hylland–Zeckhauser Models Ioannis Panageas, Avi Shein, Shayan Taherijam, Vijay Vazirani
#1342 Draw, Then Draw: The Metric Distortion of Random-Size Stable Lotteries Nisarg Shah
#1343 Hopfield Model with $p$-spin Interactions: Shattering, Disorder Chaos and Sampling Hardness Eren C. Kizildag, Bayram A. Sahin
#1344 Shannon Rate Seeded Codes from Indistinguishability Obfuscation Jesko Dujmovic, George Lu, Jad Silbak, Daniel Wichs
#1345 Depth-$1$ expanders on the unitary group and applications Anurag Anshu, Shankar Balasubramanian, Jonas Haferkamp, Aram Harrow, Xinyu Tan
#1346 The DSIC Competition Complexity of Additive Buyers over Independent Items Emily Ryu, S. Matthew Weinberg, Eric Xue
#1347 New Results in Adaptively-Secure Broadcast Encryption and Succinct Computational Secret Sharing from Standard Lattices Saikumar Yadugiri, Rishab Goyal
#1349 Tight Bounds for Rank Estimation in Turnstile Streams Yang S. Hu, Cheng Jiang, Yinchen Liu, Huacheng Yu
#1350 Combinatorial Boolean matrix Multiplation in n^3/2^{\Omega(\sqrt{\log n})} Time Piaoyang Cui, Yiming Liu, David P. Woodruff
#1351 The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight Shouvanik Chakrabarti, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul
#1352 A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices Marco Pirazzini, Daniel Spielman
#1353 Finding Integer Roots of Polynomials in Nearly Optimal Time Yansong Feng, Itamar Nir
#1354 Generalized Sorting via Four-Cycles Soheil Behnezhad, Shane Ferrante
#1355 Algorithms for Min-Color Path with Bounded Color-Degree Ajaykrishnan E S, Daniel Lokshtanov, Jie Xue, Saket Saurabh
#1356 Simulated annealing and Weak Poincar\'e inequalities with inverse-polynomial accuracy for the Sherrington-Kirkpatrick model Zhe Hou, Jingcheng Liu, Yixiao Yu
#1357 Recovering Geodesic Distances from Noisy Observations Kevin Ren, Charles Fefferman, Jonathan Marty
#1358 Iterative Rounding for Determinant Maximization and Real Stable Polynomials Nikhil Bansal, Wenzheng Li, Mohit Singh, Yuze Xu
#1359 Sharp detection thresholds for random geometric graphs with polynomial average degrees Hang Du, Cheng Mao, Nike Sun, Yihong Wu, Jiaming Xu
#1360 Improved Algorithms in the Random-Order Model: Knapsack, GAP, and Beyond Saksham Agrawal, Arindam Khan, Akash Pareek
#1361 Private Online Release of Adaptive Linear Queries Haohua Tang, Aleksandar Nikolov
#1362 An $\Omega(\sqrt{N})$ Lower Bound for Path Following Interior Point Methods on Single-Source Shortest Paths Deeksha Adil, Daniel Dadush, Rasmus Kyng, Adrian Vladu
#1363 Metric TSP in Sublinear Time: Breaking Two Approximation Amir Azarmehr, Soheil Behnezhad
#1364 Dynamic Steiner Tree under Edge Updates Jeff Giliberti, Mohammad Taghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
#1369 Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is Hard Joseph Carolan, Andrew Childs, Matthew Coudron, Amin Shiraz Gilani, David Miloschewsky, Supartha Podder
#1371 Four Ways to Stream: Exponential Separations from Random Order and Quantum Memory Nadezhda Voronova
#1372 Enumerating Posterior-Supported Priors: First-Order Error of Finite-Integral Cross-Categorical Measurement Morphisms Ning Ni, Yongxin Zhu
#1373 Deterministic Terminal Embedding with Optimal Target Dimension for Euclidean Space Vladimir Braverman, Kuan Cheng, Jiaqing Zhu
#1374 Inevitable Knowledge in Communication Complexity and the LOCAL Model Ofer Grossman, Tomer Grossman, Moni Naor, Jonathan Shulman
#1375 A Quantum Lower Bound for Triangle Finding Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
#1376 Optimal Robust Community Detection Samuel B. Hopkins, Yiding Hua, Sidhanth Mohanty, Amit Rajaraman, David Steurer
#1377 Sublinear Approximations for Spanning Tree Congestion Sunny Atalig, Marek Chrobak, Petr Kolman, Hans Raj Tiwary
#1378 Non-Interactive Cryptography over Noisy Channels from Indistinguishability Obfuscation Yuval Ishai, George Lu, Liav Zafar
#1379 Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul, Nadezhda Voronova
#1380 Weighted Minimum Cuts and Near-Minimum Cut Estimation Mu-Xia Sun
#1382 Private Online Learning of Littlestone Classes and Matroid Flats Zaobo He, Peilin He
#1383 Sparse Hamiltonian simulation with optimal dependence on the maximum column Euclidean norm Zecheng Li, Chunhao Wang
#1384 Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance Problems Shuichi Hirahara, Bingkai Lin, Yuwei Liu, Kazuki Ogitsuka
#1385 Approximating \#BIS in $\exp(\widetilde O(n^{1/3}))$ Time Jingcheng Liu, Yitong Yin
#1386 Subquadratic Time Matrix Multiplication Data Structures Beyond the Dual Exponent, with Applications Josh Alman, Jakob Nogler, Virginia Vassilevska Williams
#1389 Linear Max Load and Additive Structure Vinayak Kumar, David Zuckerman
#1390 The Caccetta-Häggkvist Conjecture and Percentile Distortion: An Equivalence via Asymmetric Maximal Lotteries Fatih Erdem Kizilkaya, Yusuf Hakan Kalayci, David Kempe, Evi Micha
#1391 An Explainable Transfer Learning Framework for Multimodal Medical Image Classification Using ResNet50 and Grad-CAM Muhammad Rashid Majeed, Peiyun Zhang, Mst Jannatul Kobra
#1392 Multitask Contracts: Realizing the Value of Bundling Eden Saig, Yael Tolkowsky, Inbal Talgam-Cohen
#1393 Tight Bounds on the Menu-Size Complexity of Approximately Optimal Auctions with Two Items Hau Chan, Mingyu Guo, Nguyen Thach
#1394 Binary Huffman Coding with Unequal Letter Costs Is NP-Complete L. Sunil Chandran, Rishikesh Gajjala
#1395 Beyond Dolev-Strong: Adaptive Byzantine Broadcast with O(n\sqrt(n)) Messages under a Tight Honest Majority Matthieu Rambaud
#1396 Sparse $\alpha$-Navigable Graphs in Euclidean Space via Steiner Points Alex Conway, Laxman Dhulipala, Martin Farach-Colton, Yarin Shechter, Torsten Suel, Richard Wen
#1397 Adaptivity Gaps for Welfare-Maximizing Pooled Testing Edwin Lock, Nicholas Lopez, Francisco Marmolejo-Cossio, Jose Roberto Tello Ayala, David Parkes
#1398 Mitigating error propagation in chaotic dynamics via inference-time noising: a view from backward sampling Stephen Huan, Andrej Risteski, Qiuhong Anna Wei
#1399 Inapproximability of Euclidean Steiner Tree Simon Bartlmae
#1400 Adaptive Matrix Sparsification with Applications to Empirical Risk Minimization and Computational Geometry Yang Liu, Richard Peng, Colin Tang, Albert Weng, Junzhao Yang
#1401 The Honeycomb Framework for Code Bounds William Gay, Fernando Granha Jeronimo, Lenny Liu
#1402 Efficient Non-Adaptive Sparse Fourier Learning on the Boolean Cube and Finite Abelian Groups Idan Attias, Nader H. Bshouty, Marko Medvedev, Nathan Srebro
#1403 Simulating Space Bounded Read-$k$ PTMs with Space Bounded Read-Once PTMs Kuan Cheng, Shengtang Huang, Ruiyang Wu
#1404 Condorcet-Winning Sets and Peer Selection in Planar Metric Elections Gabriel Morete de Azevedo, Ulysse Hennebelle
#1409 Regev's Reduction Reaches Reconstruction Stephen Jordan, Quynh T. Nguyen, Leo Zhou
#1410 Hitting Sets for Polynomials with Small Hasse Derivative Space over Arbitrary Characteristic Fields Aranya Kumar Bal, Sumanta Ghosh
#1411 Approximation Algorithms for Directed Telephone Multicast Shahin Kamali, Seyed Mohammad Seyed Javadi
#1412 A Constant-Rate Compiler for Continual Memory Leakage Rajeev Raghunath, Shweta Agrawal, Anuja Modi
#1413 Optimal Learning under Tsybakov Noise Steve Hanneke, Hongao Wang, Mingyue Xu
#1414 Almost Tight Hardness of Approximation for 0-Extension Qingyun Chen, Weihao Zhu
#1415 Non-signaling PCPs as Algebraic Proofs, and Total Coefficients Lower Bounds for Sherali–Adams Liyan Chen, Zhengzhong Jin
#1416 Minimum-Cost $k$-Arborescence Packing in $\tilde O(km+k^4 n)$ Time Zhaienhe Zhou
#1417 Structural Accessibility in Phase-Encoded Quantum Graph Embeddings Luke James Miller, Yugyung Lee
#1418 Faster Isomorphism for Groups of Class 2 Xiaorui Sun
#1419 Minimum-Mean Testing under Metric Constraints:Shared Information, Certificates, and Adaptivity chaomeng chen, Xiang Fang
#1420 Once-Paid Subsequences and the Cost of Min-Plus Approximation Zemin Chao, Menghan Li, Xiangyu Gao, Hongzhi Wang
#1421 3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
#1422 The log log jam in Gaussian state tomography Sitan Chen, Weiyuan Gong, Qi Ye, Zhihan Zhang
#1423 SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules Jiaqi Liu, Yansong Feng, Yanbin Pan
#1424 Exact Mean Certificates under Sparse Graph Corruption chaomeng chen, Junhao Dong
#1425 Replicable Decisions in Finite Experiments: A Chain Converse and Its Limits chaomeng chen
#1426 Low-Degree Learning from Localization Schemes Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra, Arsen Vasilyan
#1427 The Price of Irreversible Experiment Access chaomeng chen, Xiang Fang
#1428 Learning to Think from Multiple Thinkers: How Chain-of-Thought Heterogeneity Affects Efficient Learnability Nirmit Joshi, Roey Magen, Nathan Srebro, Nikolaos Tsilivis, Gal Vardi
#1429 Identifying Minimax Payoffs from Bounded Interventions chaomeng chen
#1430 The Ultimate Karp-Lipton Collapse Edward A. Hirsch, Ilya Volkovich
#1431 The 3-Uniform Hyperclique Hypothesis is False Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
#1432 Explicit functions requiring larger than 4.5n size circuits Sam McGuire, Samuel Schlesinger, Ryan Williams
#1433 A Near-Optimal Generalized Sorting Algorithm Sanjeev Khanna, Aaron Putterman, Junkai Song
#1434 Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting Set Daniel Hathcock, Aditya Subramanian, Seeun William Umboh, Michael Zlatin
#1435 Memory-Regret Tradeoffs for Online Learning Nataly Brukhim, Sumegha Garg
#1436 Bootstrap, Recolor, Verify: Hierarchical Integrality Gap Instance for 0-extension Konstantin Makarychev
#1437 Exact Counting and Sampling of Labeled Graphs of Bounded Treewidth with MSO Properties KunCheng Zou, Yuanhong Wang, Yi Chang, Yuyi Wang, Ondřej Kuželka
#1438 No linear stretching of single-copy quantum pseudorandomness Boyang Chen, Andrea Coladangelo, Yao-Ting Lin, Nikos Skoumios, Justin Tysdal, Yiming Wang
#1440 Optimal Vertex Sampling for Constraint Satisfaction Problems Kehua Chang
#1441 Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy Atul Mantri
#1442 Quasipolynomial-Time Planning for Decodable POMDPs Oliver Dobson, Varun Jog, Chun Hei Michael Shiu
#1443 Optimal Quantum Algorithms for Ordered Search Joseph Carolan, Andrew Childs
#1444 Quasilinear Encoding at the Quadratic Alphabet Scale via Short Cartier Bases Zemin Chao, Dongli Liu, Yixuan Li, Hengzhao Ma, Hongzhi Wang
#1445 When quantum thermal states look classical Jordan Cotler, Harald Putterman, Alexander Zlokapa
#1446 A Scheme-Comparable Formulation of Uniqueness Entropy for k-mer Sketches on Repetitive Genomes Akmuhammet Ashyralyyev, Can Alkan
#1447 Breaching the 2-Approximation Barrier for Prize-Collecting Steiner Forest Miguel Bosch Calvo, Fabrizio Grandoni, Bence Mátravölgyi
#1448 Compressed Permutation Oracles Revisited Joseph Carolan, Christian Majenz
#1449 Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert–Varshamov Bound Quan D. Bui, Manabu Hagiwara, Shuche Wang, Van Khu Vu
#1450 Improved quantum volume estimation with transducers and amortized quantum walks Arjan Cornelissen, Simon Apers, Sander Gribling
#1465 Settling the Complexity of Hylland--Zeckhauser Equilibria Zhengyang Liu, Yixin Tao, Yonglei Yan
#1466 Work-Efficient Parallel Rounding: Product Objectives Chase Hutton, Adam Melrod
#1467 The k-server conjecture is true Christian Coester, Elias Koutsoupias, Marek Zbysiński
#1468 When Is Training Predictable? large Exact Fast-Forwarding, Decidability Frontiers, Certified Nonlinear Prediction, and Horizon-Free Model Selection Baidya Nath Saha
#1469 Near-Linear Lower Bounds for Testing Directed Acyclicity Artur Czumaj, Pan Peng, Yuyang Wang
#1470 Dimension-Independent Anti-Concentration Certificates for Log-Concave Distributions Stefan Tiegel
#1471 Polynomial-Time Approximate EFX for Chores via Flow and Matching Genjie Qin, Qizhi Fang, Minming Li, Wenjing Liu, Xin Chen
#1472 Balanced Fair Division and Generalized Kneser Graphs Sharareh Slipour, Amir Jafari
#1473 Optimal XOR Lemmas for Information Complexity Alexander A. Sherstov
#1474 Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal Approximation Liad Erez, Nadav Eisen, Tomer Koren, Yuval Dagan
#1475 A passive self-correcting quantum memory in three dimensions Shankar Balasubramanian, Margarita Davydova, Ting-Chun Lin
#1476 Constructive Arboricity in Almost-Linear Time for Dense Graphs Iman Gholami, MohammadTaghi Hajiaghayi, Mahdi JafariRaviz, Alireza Kaviani, Soheil Mohammadkhani, Amir Mohammad Shahrezaei
#1477 Global asymptotic stability of homogeneous polynomial vector fields is undecidable Ivan O. Shevchenko, Jun Liu, Xinzhi Liu
#1478 Optimal Error Exponents for Private Bayesian Hypothesis Testing Ben Jacobsen
#1479 On efficient global updates in first-order logic Tuukka Korhonen, Marek Sokołowski
#1480 Finding Gaussian Structure in Bosonic States Alvan Arulandu, Sitan Chen, Ziyun Chen, Jerry Li, Eric Ma
#1481 How to Round Spiky Balls into Submission; And Faster Algorithms For The Closest Vector Problem Divesh Aggarwal, Aditya Morolia
#1483 A Deterministic Approximation Scheme for Counting Read-Twice CNF Assignments Yucong He
#1484 The Role of Diagonal Lines in Quantum Low-Degree Testing Tianrun Zhao, Honghao Fu, Nengkun Yu
#1485 Understanding Model Misspecification in Low-Rank Distributions: Tolerant Testing and Agnostic Learning Niki Hasrati, Andrej Risteski
#1486 Learning Fourier-Sparse Signals and Multiband Signals Dongrun Cai, Xue Chen, Xiaowei Shao, Yile Wang
#1487 Breaking the quantum barriers for Graph Collision Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou
#1488 Improved Upper and Lower Bounds for Quantum Convex-Body Volume Estimation Ruizhe Zhang
#1489 A Sharp Mean-Budget Transition for Local Pair Marginals Zemin Chao, Xiangyu Gao, Zhixin Qi, Hongzhi Wang
#1490 Provably Distilling from Modern Language Models via Low Logit Rank Noah Golowich, Allen Liu, Abhishek Shetty
#1491 Conservative Modular Counting at Every Odd Prime Chengzhi Xie
#1492 On the Computation of Sparse Equilibria in Normal-Form Games Fan Chen, Constantinos Daskalakis, Gabriele Farina, Noah Golowich, Charalampos Platanos
#1493 On the most informative Boolean function under noise Dimiter Kramer, Mert Saglam
#1494 The Higher-Order Identifiability Paradox: Learning and Certifying Hypergraph Order Siming Zhang, Bo Yan, Pengpeng Qiao, Hang Yu
#1495 Distributional Quantum Query Complexity Shalev Ben-David, M. H. Ebtehaj
#1496 The Power of Test-Time Training for Approximate Sampling Noah Golowich, Ankur Moitra, Dhruv Rohatgi
#1497 Sharp Spectral Bounds for Kikuchi Matrices: \\ The Hypergraph Moore Bound and Optimal Trade-offs for $k$XOR Alexander Schmidhuber, Matthew Hastings
#1500 A Unified and Robust Theory of Lower and Upper Bounds for the √log n Barrier Dominik Kempa, Tomasz Kociumaka
#1501 Sharp Power Loss Thresholds for Vector Min Uncut Chengzhi Xie
#1502 Tight Bounds for Conservative Pointer Jumping Atul Mantri
#1503 Asymptotically good large-alphabet LDCs with polylogarithmic query complexity Tal Yankovitz
#1504 Robust and Uncertainty-Aware Explanations for Medical Vision-Language Models: A Fusion of Grad CAM, Integrated Gradients and Counterfactuals on ROCO Nabeel Raza
#1505 Fine-Grained Parameterized Algorithm: Shaving Subexponential Factor for Maximum Cut Akanksha Agrawal, Deep Antrolia, Sounaka Mishra, Vidya Sagar Sharma
#1506 Private Information Retrieval from Two Entangled Servers Atul Mantri
#1507 Matrix Multiplication from Polynomial Packings: A Constructive Proof of ω ≤ 9/4 Rafael Pass
#1508 Efficient Equilibrium Computation in Colonel Blotto Games Martin Bichler, Abheek Ghosh
#1538 From Bilateral Trade to Matching Markets: Sharp Gains from Trade Zhengyang Liu, Ying Qin, Zihe Wang
#1539 GuardKV: A Risk-Aware KV-Cache Timing Side-Channel Defense Framework for Multi-Tenant Large Language Model Inference Ruizhong Du, Jing bo, Yan Gao, Chenyang Wang, Xun Li, Jianfa Wang
#1540 Optimal Learning in Games with Arbitrary Delays: Best-of-Both-Worlds for Self-Play and Adversarial Opponents Emmanuel Esposito, Andrew Jacobsen, Hao Qiu, Alexander Ryabchenko, Mengxiao Zhang
#1541 Weighted Equitability and Matroid-Constrained Discrepancy Kristóf Bérczi, Siyue Liu, Victor Reis, Jakub Tarnawski
#1542 Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement Discrimination Qian Qi
#1543 Real-Time String Indexing in Optimal Time Gregory Kucherov, Yakov Nekrich
#1544 Beyond Gomory-Hu: All-Pairs $\times$ All-Pairs Mincuts in $O(n)$ Space Koustav Bhanja, Merav Parter, Asaf Petruschka
#1545 Online Metric Problems via Randomly Perturbed Work Functions Christian Coester, Danish Kashaev
#1546 PriProxy: Privacy-Aware Selective Proxying with Dual-Channel Leakage Evaluation for System Prompt Protection Jing bo, Yan Gao, Jinru Wu, Jianfa Wang, Yan Liu, Ruizhong Du
#1548 BSC vs. BEC vs. PSC Jan Hązła, Ryan O'Donnell
#1549 Deterministic $o(mn)$-time algorithms for computing the $k$-connected components in directed graphs Loukas Georgiadis, Evangelos Kipouridis, Evangelos Kosinas, Charis Papadopoulos, Christos Pergaminelis
#1550 Algorithms for Sparse LWE and LPN with Small Secrets Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar
#1551 Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor (and More) Édouard Bonnet, Yeonsu Chang
#1552 Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut Eduard Eiben, Roohani Sharma, Magnus Wahlström
#1553 Constant Approximation of Fréchet Distance in Near-Linear Time Haoqiang Huang, Zihe Wang, Shuo Zhang
#1554 Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman Decisions Qian Qi
#1555 Optimal Testing and Profile Recovery from Aggregated Binary Linear-Code Samples Jianxin Wang, Zixuan Wang, Chenxu Pang, Chaoen Xiao, Lei Zhang, Zaitian Fu, Conghui Zheng, Yiyang Zou
#1556 Nearly Tight Approximation for Vertex-Disjoint Cycle Packing Madhumita Kundu, William Lochet
#1557 Efficient Private and Robust Statistics Anming Gu, Arun Jambulapati, Syamantak Kumar, Argyris Mouzakis, Kevin Tian, Chutong Yang
#1558 Supply-Sensitive Revenue Recovery under Unknown Buyer Order Mirmahdi Rahgoshay, Maryam Mahboub
#1559 Polynomial-time algorithms for mean-field models up to the glass transition Alexander Schmidhuber, Alexander Zlokapa
#1561 Exact SVP and CVP in Structured Lattices: Polynomial-Space Algorithms and Reductions Jiseung Kim, Changmin Lee, Yongha Son
#1562 What can be Computed with Indefinite Causal Structure? Omri Shmueli
#1563 High Confidence Yields Outlier Robustness: Consequences in Computational Hardness, Privacy, and Replicability Varun Narayanan, Jasper C.H. Lee, Ankit Pensia
#1564 A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick Model Dylan Herman, Shouvanik Chakrabarti, Junhyung Lyle Kim, Guneykan Ozgul
#1565 Pure Differentially Private Query Release via Laplace Input Smoothing Zongrui Zou
#1567 Learning Arbitrary Lindbladians from Time Evolution Zhili Chen, Zhan Yu
#1568 Online Average-Value Allocation: A Sharp Information Frontier Mirmahdi Rahgoshay, Maryam Mahboub
#1569 Single-Exponential Algorithms for Directed Feedback Vertex Set on Planar Digraphs Daniel Lokshtanov, Saket Saurabh, Jie Xue
#1570 Hitting time for loose Hamilton cycles in the random hypergraph process Jared León, Xizhi Liu
#1571 Parisi formula and product-state optimization of quantum mixed p-spin Hamiltonians Sohom Bhattacharya
#1572 Accelerated Parallel Algorithms for Packing Linear Programming Jiale Chen, Li Chen, Andrei Graur, Aaron Sidford
#1573 Nearly Exact Length Bounds for Directed Steiner Tree and Forest in Planar Graphs Mirmahdi Rahgoshay, Maryam Mahboub
#1574 Lattice Reduction at Average Precision yang zhou, Mingsheng Wang, Zhedong Wang
#1575 Counting Exact-One Hitting Sets in Subexponential Time Shiteng Chen, Tao Jiang, Yijie Zhu
#1577 Quantum Separability in Polynomial Time Giulio Malavolta
#1578 List Decoding, Linear Hashing, and Furstenberg over $\mathbb{F}_q$ Vinayak M. Kumar, Geoffrey Mon
#1579 Deterministic Incremental Triconnectivity in O(log² n) Worst-Case Time Niels Inselmann Christiansen, Eva Rotenberg
#1580 Quantum Advantage has Few Complexity Implications Eli Goldin, Alex Lombardi, Tomoyuki Morimae
#1581 The Existence of Maximin Share Allocations is $\Delta_2^P$-complete Sushmita Gupta, Sanjay Seetharaman
#1582 Neural Hamiltonian Operator: Finite-Precision Error Bounds without a Fixed Ellipticity Margin Qian Qi
#1583 Lower Bounds Between Random CNFs and PRG Tautologies For Dag-like Communication Duri Andrea Janett, Robert Robere, Anastasia Sofronova, Dmitry Sokolov
#1584 The Power of Interaction in Locally Edge-Private Subgraph Counting Xian Chen, Pan Peng
#1585 From One Hidden Subgraph to Dense Graph Partitions with Applications to Hardness of Clustering Harman Agrawal, Pakapim Eua-anant, Bernhard Haeupler, Bundit Laekhanukit, Petar Mihov, Lazar Milenković, Rowan Santos, Zhijun Zhang
#1586 A Constant Approximation for Min-sum k-Clustering Aditya Anand, Moses Charikar, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland
#1587 Strong Backdoor to Forests is FPT: Tight Linear-Time FPT for Essentially General SAT Olesia Bilyk, Aidar Munduzbaev, Roohani Sharma, Mamnoon Siam
#1588 Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith
#1590 Sublinear Time Clustering: Taming Random Walks in Arbitrary Noise Michael Kapralov, Ekaterina Kochetkova
#1592 Uniform Guarded Bootstrapping for Topology-Sensitive Directed Shortest Paths Bin Cai
#1593 Constant-Time Range Counting for Pattern-Avoiding Permutations and Entry Access to Twin-Ordered Matrices Sankardeep Chakraborty
#1594 A Circuit Complexity Trichotomy For Regular Languages Stefan Göller, Amaldev
#1595 Optimal Online Bin Covering across Stochastic Models Nikhil Ayyadevara, Arindam Khan, Amit Kumar, K. V. N. Sreenivas
#1596 The Limits of Posted Prices in Random-Order Combinatorial Auctions Frederick Qiu, Aviad Rubinstein
#1597 Synchronization Strings over a Ternary Alphabet Huibo Xu, Shi Fu, Youming Qiao, Dacheng Tao
#1598 Learning Mixtures with Unknown Scales: Sharp Dependence on Separation Shihao Wang, Xueru Zhang
#1599 A unifying framework for Graph Minor Structure Theorems with polynomial bounds Maximilian Gorsky, Evangelos Protopapas, Sebastian Wiederrecht
#1600 First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs Eden Koveshi, Liam Roditty, Ariel Sapir
#1601 Accepting Subcubes and the Approximability of Complete Boolean Min-CSPs Shaowei Cai, Tao Jiang, Xingwu Liu
#1602 Word Length and Diameter in Permutation Groups Markus Lohrey, Alexander Thumm
#1604 Monadically Dependent Graph Classes Have Almost Bounded Merge-Width Jan Dreier, Nikolas Mählmann, Michał Pilipczuk, Szymon Toruńczyk
#1605 Optimal Private Gaussian Multi-sampling Raoof Zare Moayedi, Mohammad Hossein Yassaee, Javad B. Ebrahimi
#1606 Computational Work Extraction: The Complexity of Catalysts Atul Singh ARORA, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh
#1607 The Modular Nash-Williams Theorem Amir Jafari
#1609 From smoothed analysis to backward error: The power of adaptive perturbations Michał Dereziński, Michael W. Mahoney, Raphael Meyer, Christopher Musco
#1610 Precedence-Constrained Decision Trees and Coverings Michał Szyfelbein, Dariusz Dereniowski
#1611 When Does Private Data Collection Need Interaction? Online Selection under Local Differential Privacy Yanpu Chen, Guangshuai Wang
#1612 First-Order Model Checking on Monadically Dependent Graph Classes Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
#1613 Tight Lower Bounds under Matched High-Order Hölder Smoothness and Uniform Convexity Cedar Site Bai
#1627 Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry Canzhe Zhao, Vincent Y. F. Tan
#1628 Toward an Optimal Quantum Algorithm for Geometrically Local Hamiltonian Simulation Zheyu Shen, Yusen Wu, Penghui Yao, Xiao Yuan, Yukun Zhang
#1629 Batchwise List Decoding for Agnostic Stabilizer Learning Ching-Yi Lai
#1630 Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold Rate Hai H. Nguyen
#1631 Subexponential Approximation of the Permanent in Deterministic Polynomial Time Sergei Kudria, Jason Luo, Mahbod Majid
#1632 Natural proofs for quantum state preparation lower bounds Christine Li, Natalie Parham
#1633 Nearly Optimal Strong Coresets for $\ell_p$ Subspace Approximation Honghao Lin, Vahab Mirrokni, David Woodruff
#1634 Shallow Quantum Circuits for Geometrically Local Lindblad Dynamics Zheyu Shen, Yusen Wu, Xiao Yuan, Yukun Zhang
#1637 Regularity lemma for Gaussian polynomials Chris Jones
#1639 Parallel Repetition for Entangled Games via Conditional Relative Entropy Rahul Jain
#1640 Parallel Composition of Quantum Differential Privacy: The Role of Measurement Restrictions Ji Guan, Yecheng Qin
#1641 Exact $\ell_p$-CVP via Euclidean SVP in Polynomial Space Jiseung Kim, Minkyu Kim, Hyung Tae Lee
#1642 Faster Power Series Composition in Fixed Positive Characteristic Yijie Zhu
#1643 Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion Jack Spalding-Jamieson
#1644 Optimal Separations Between Randomized and Quantum Query Complexity under Permutation Symmetry Yunqi Huang, Lvzhou Li, Zekun Ye, Shenggen Zheng
#1645 Depth Lower Bounds for ReLU Networks with Binary Inputs Neil Krishnan, Elchanan Mossel
#1646 A Tight FPT Approximation for Capacitated k-Median Aditya Anand, Yichen Huang, Ragesh Jaiswal, Amit Kumar, Euiwoong Lee, Jatin Yadav
#1647 Hardness of Unique Shortest Vectors and Bounded Distance Decoding Sergei Kudria, Jason Luo
#1648 Breaking the Linear-Pass Barrier for DFS on Streaming Digraphs Prantar Ghosh, Amirhossein Janfaza
#1649 On Existence and Computational Complexity of Quasi-strict Equilibria Kristoffer Arnsfelt Hansen, Xinhao Nie
#1650 Rounded Potentials Certify Exact Maximum Flow Ohad Trabelsi
#1651 Coupling Independence Implies Zero-Freeness Shuai Shao, Ke Shi
#1652 Necklace Splitting with Ten Beads per Colour is PPAD-Hard Zijian Zeng, Sibo Wang, Jiayin Cao, Weinan Dai, Rui Wang
#1653 PIT and Reconstruction for Sums of High Powers Amir Shpilka, Nimrod Kaplan, Yann Tal
#1654 Faster Equal-Subset-Sum via Truncated Inclusion–Exclusion Shayan Cheshm Jahan, Alireza Keshavarz Hedayati, Ali Safari, AmirMohammad Shahrezaei
#1656 Testing Fourier Sparsity Near Optimally Arijit Ghosh, Manmatha Roy
#1657 Vertex Deletion on $H$-Induced-Minor-Free Graphs: Subexponential FPT Algorithms and Approximation Schemes Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
#1658 Constant-Factor Approximation for Generalized Max–Min Degree Arborescence in Quasi-Polynomial Time Wenzheng Li
#1661 Interior Point Methods Solve Random LPs in polylog(n) iterations Shunhua Jiang, Daniel Dadush, Rasmus Kyng, Haoyuan Ma
#1662 Tight Competitive Bounds for Online Matching on Forests Bartłomiej Bosek, Grzegorz Gutowski, Paweł Putra, Anna Zych-Pawlewicz
#1663 Adaptive Data Analysis Beyond the Privacy Barrier Florian E. Dorner, Moritz Hardt
#1664 Tight bounds for fractional and randomized truthful scheduling Georgios Anastasiadis, George Christodoulou, Elias Koutsoupias, Annamaria Kovacs, Conrad Schecker
#1665 A Nearly Linear-Time FPRAS for Counting Knapsack Ce Jin, Jaewoo Park, Barna Saha
#1666 A Hierarchy of Proofs of Quantumness Kaniuar Bacho, Dominik Leichtle, Atul Singh ARORA, Alexandru Cojocaru
#1667 Instance-Optimality of Single-Pair Personalized PageRank Christian Bertram, Mads Vestergaard Jensen, Mikkel Thorup, Hanzhi Wang, Shuyi Yan
#1668 Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and Erasures Wonseok Choi
#1670 Intractability of Continual Learning using Parametric Models with Unlimited Replay Buffer Rishi Saket
#1671 A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics Jon Nelson, Joel Rajakumar, Chao Yin, Yifan (Frank) Zhang, Michael Gullans
#1672 Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness Hector Tierno, Shuang Yang
#1673 Quantum Tolerant Testing of Fourier Dimensionality and Juntas Zekun Ye, Jialin Zhang
#1674 $L_1$ versus $L_2$ Clustering: When Does the Choice of Norm Matter? Nick Gravin, Jianhao Jia
#1675 When Do Gradients Suffice? A Characterization of First-Order Convex Optimization Noga Alon, Tomer Koren, Roi Livni, Shay Moran
#1677 The complete phase diagram of detailed-balanced Gibbs samplers for the mean-field Heisenberg model Levente Raikovich, Jozsef Mak, Csaba Czaban, Andras Gilyen
#1678 Learning DNF from Satisfying Assignments with Membership Queries Zelin Li
#1679 Quantum Interactive Proofs of Proximity Kenan Wood
#1681 Classical Tensor Codes and Quantum Tanner Codes Achieve Capacity on Erasure Channels Henry D. Pfister, Oscar Sprumont, Gilles Zémor
#1682 Improved Steiner Forest Approximation via Cut Spaces Shayan Cheshm Jahan, Alireza Keshavarz Hedayati, Ali Safari, AmirMohammad Shahrezaei
#1683 Reverse Reductions: From Faster SAT to Subexponential Algorithms Madhumita Kundu, Fahad Panolan, Saket Saurabh, Jie Xue, Meirav Zehavi
#1684 Deterministic Construction of Primes in Subexponential Time Karthik Gajulapalli
#1685 Sharp Limits of Graph-Based Nearest Neighbor Search on the Sphere Kejing Lu
#1686 A Dichotomy for Constrained Eulerian Orientations Jincheng Guan, Shuai Shao, Ke Shi
#1687 Optimal (Randomized) Compact Routing Schemes Gur Lifshitz, Shiri Chechik, Avi Kadria, Liam Roditty
#1688 A Sharp Barrier of Consistent Submodular Maximization: Any Improvement over 2 − √2 Entails Exponential Queries or Linear Recourse Shi Fu, Qixin Zhang, Dacheng Tao
#1697 Fourier Entropy Bounds via Approximations Manaswi Paraashar, Nitin Saurabh
#1699 Low-Error Extractors Dean Doron, Jesse Goodman
#1701 The Price of Stability in Undirected Network Design: Lower Bounds and Structural Guarantees Christos Tsoufis
#1702 The Contraction Lemma Beyond ETH: Algorithms and Lower Bounds Karthik Gajulapalli
#1703 Likelihood-Ratio Learning under Weak Overlap via Analytic Temporal Elimination Wei Chen, Yubing Wu, Junmei Yang, Delu Zeng
#1704 Compete Fairness in Secure Two-party Computation from Quantum One-Wayness Arpita Maitra, Goutam Paul, Asim K. Pal, Asmita Samanta, Hridam Basu
#1706 The Metacomplexity Structure of Search Problems Shalev Ben-David, M. H. Ebtehaj
#1707 Fitting Ultrametrics under any $\ell_p$ Objective Moses Charikar, Ruiquan Gao
#1708 Statistical-to-computational gaps in central limit theorems for high-dimensional tensors Debsurya De, Dmitriy Kunisky
#1709 Optimal Competitive Ratios for Chasing Convex Functions with Quadratic Growth Linzhe He, Sifan Yang, Wei Jiang, Lijun Zhang
#1710 Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks Vedat Levi Alev, Shravas Rao
#1711 Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand Inequality Zihao Liang, Mingmou Liu
#1712 Near-Optimal Almost-Ramsey Spanning Tree Covers, via Layered Clusterings Michael Elkin, Idan Shabat
#1713 PAC Learning with Multiple Correct Answers Steve Hanneke, Farnam Mansouri, Alireza F. Pour, Amirreza Shaeiri, Kun Wang
#1714 Smallest Multiplicative Stretch for an $\alpha$-APASP Below $\widetilde O \left(n^{\omega}\right)$ Runtime Ariel Sapir, Lakshay Saggi
#1715 The Complexity of Space–Reset Tradeoffs in Online Quantum Computation Rinka Miura
#1716 Using Small Advice to Compress the Predecessor Matrix Ariel Korin, Tsvi Kopelowitz, Liam Roditty
#1717 Approximating Transcendence Degree in Medium Characteristic Michael Forbes, Andrei Staicu
#1718 A Dichotomy for Exact Quantum Circuit Amplitudes Chenghua Liu, Boning Meng
#1719 Truly Subquadratic 3SUM over Every Bounded-Exponent Abelian Group Zijian Zeng, Sibo Wang, Jiayin Cao, Weinan Dai, Rui Wang
#1720 Breaking the $O(mn)$ Barrier for Minimum Bipartite Dijoin via Dynamic and Local Graph Algorithms Chaitanya Nalam, Thatchaphol Saranurak
#1721 A Fast Algorithm for Subspace Convolution Shlomo Perles, Omri Weinstein
#1722 Vector Balancing in Polynomial Time Shengtao Guo, Ethan X. Fang, Junwei Lu
#1723 Testing isomorphism of finite groups in time polynomial in the group order Youming Qiao, Chuanqi Zhang
#1724 Sparsest Cut on Abelian Cayley Graphs Jake Ruotolo
#1725 Inapproximability of L1->L2 Subspace Distortion Vijay Bhattiprolu
#1726 How Many Votes Is a Lie Worth? Measuring Strategyproofness through Resource Augmentation Ratip Emin Berker, Vincent Conitzer, Eden Hartman, Jiayuan Liu, Caspar Oesterheld
#1727 Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms Serge Gaspers
#1728 Information Required to Preserve Past Learning Pinang Xu
#1731 B\"{u}chi Determinization with Optimal States and Square Root Index Improvement Cong Tian, Runzhe Ma, Wensheng Wang, Zhenhua Duan
#1733 One-point value of a combinatorial generating series as a complexity measure Varsha Gupta
#1735 Computational Complexity of Data-Driven Configuration for Integer Programming, Clustering, and Learning Algorithms Dravyansh Sharma
#1736 Decoding Expander Walk Codes up to the Johnson Bound in Near-Linear Time Silas Richelson, Sourya Roy, Madhur Tulsiani
#1737 The Movement Complexity of Sorting Sichen Wang
#1738 Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions Yegor Gorodzha, Steven Hoehner, Gil Kur
#1739 Quantum Approximate Pattern Matching with Wildcards and Weighted Edits: Provable Baselines and Sparse-Defect Verification Ziming Zhao, Junyu Chen, Zhaoxuan Li, Fanqi Kong, Yu Peng, Jiongchi Yu, Xiaofei Yue
#1740 Unitary Synthesis with a PSPACE Oracle Sichen Wang
#1742 A Proof of the Matrix Spencer Conjecture Emrullah Akbas, Suvrit Sra
#1743 Improved Bounds for Certifying Injective Norm of Sparse Random Tensors Pravesh Kothari, Anand Louis, Rameesh Paul, Prasad Raghavendra
#1744 Efficient Algorithms for Minrank and Index Coding for Low-Treewidth Graphs Shlomo Perles, Omri Weinstein
#1745 Byzantine Partition Detection Under Churn Sinchan Sengupta, Matthieu Perrin
#1746 Canada Retravelled Andreas Abels, Elias Pitschmann, Kevin Schewior, Daniel Schmand
#1747 The Price of Anarchy in Markets for Lemons Naveen Durvasula, Tim Roughgarden
#1748 When Can Physical Evidence Survive a World-Model Update? Finite-Cost Re-Auditing and Reusable Policy Certificates Qingqing Li
#1750 Greed is All You Need: An Approximation Algorithm Framework for Nested Norm Covering and Packing Problems Junhao Gan, Gerald Huang, Seeun William Umboh
#1752 Claw-free perfect graphs are chromatic-choosable. Umesh Shankar, Suchismita Mishra, Narayanan N