ITCS 2022
who it's for
theoretical computer scientists, complexity theorists, quantum computing researchers, cryptographers, coding theorists, algorithm designers, algorithmic game theorists
topics
external-memory dynamic optimality; quantum LDPC codes; polynomial identity testing; stabilizer rank lower bounds; fastest mixing Markov chains; balanced allocations with queries; budget-smoothed submodular maximization; Reed-Solomon repair schemes; homomorphic secret sharing download rates; lattice-based broadcast encryption; minimum circuit size problem; dynamic matching algorithms
| title | author | length |
|---|---|---|
| Balanced Allocations with Incomplete Information: The Power of Two Queries | Dimitrios Los, Thomas Sauerwald | 20m |
Proves any adaptive one-quantile or one-threshold scheme has gap at least Omega(log n / log log n) in the heavily loaded regime, disproving the conjectured… | ||
| Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for all Distributi | Meryem Essaidi, Matheus Venturyne Xavier Ferreira, S. Matthew Weinberg | 25m |
New auction ADRA claims a single-item mechanism that is revenue-optimal, incentive-compatible for bidders and credible for the seller for all distributions, by… | ||
| What Does Dynamic Optimality Mean in External Memory? | Michael A. Bender, Martin Farach-Colton, William Kuszmaul | 27m |
Defines external-memory dynamic optimality for update-heavy workloads, builds a new Jello tree and proves it is statically optimal and competitive against any… | ||
| On polynomially many queries to NP or QMA oracles | Dorian Rudolph, Sevag Gharibian | 33m |
Shows that any problem solvable by graphs of bounded separator number or bounded depth is decidable by a deterministic machine in n^{O(s)} time using O(s log… | ||
| Explicit Abelian Lifts and Quantum LDPC Codes | Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani | 34m |
Constructs polynomial-time explicit d-regular expanders that are Z_L lifts (and more generally transitive abelian lifts) for L up to about 2^{cN}… | ||
| The importance of the spectral gap in estimating ground-state energies | Abhinav Deshpande, Alexey V. Gorshkov, Bill Fefferman | 23m |
Shows that adding an inverse-polynomial spectral gap to the precise (inverse-exponential) ground-state energy problem drops complexity from PSPACE-complete to… | ||
| Polynomial Identity Testing via Evaluation of Rational Functions | Dieter van Melkebeek, Andrew Morgan | 37m |
Paper shows that the rational function evaluation generator is equivalent (up to variable rescaling) to the Shpilka–Volkovich generator and gives an explicit… | ||
| Almost-Orthogonal Bases for Inner Product Polynomials | Chris Jones, Aaron Potechin | 27m |
Provides an explicit almost‑orthogonal polynomial basis for orthogonally invariant functions of m Gaussian or spherical or Boolean vectors, with degree‑D basis… | ||
| More Dominantly Truthful Multi-task Peer Prediction with a Finite Number of Tasks | Yuqing Kong | 35m |
Introduces a new information measure, volume mutual information, that equals the determinant-based mutual information under uniform density and satisfies the… | ||
| Classical algorithms and quantum limitations for maximum cut on high-girth graphs | Boaz Barak, Kunal Marwaha | 15m |
Shows a concrete limitation: for graphs of girth ≥6 any one-local algorithm (classical or quantum) can only achieve cut fraction 1/2 + C/√D with C ≤ 1/√2 ≈… | ||
| Budget-Smoothed Analysis for Submodular Maximization | Aviad Rubinstein, Junyao Zhao | 20m |
Paper introduces budget-smoothed analysis where an adversary picks a worst-case submodular function and the budget is sampled from a fixed distribution, gives… | ||
| Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions | Sepehr Assadi, Chen Wang | 27m |
A constant-factor correlation clustering algorithm appears with only adjacency list of positive subgraph access: randomized algorithm runs in O(n log^2 n) time… | ||
| Lower Bounds on Stabilizer Rank | Shir Peleg, Amir Shpilka, Ben Lee Volk | 22m |
Proves a concrete barrier for Clifford+T simulation by showing the stabilizer rank of the n-fold magic state is linear Ω(n) (n/100) and the approximate rank is… | ||
| Reduction From Non-Unique Games To Boolean Unique Games | Ronen Eldan, Dana Moshkowitz | 33m |
Presents a polynomial-time reduction that fixes the 2016 construction by replacing periodic half‑spaces with ordinary half‑spaces and reduces a conjectured… | ||
| Geometric Bounds on the Fastest Mixing Markov Chain | Sam Olesker-Taylor, Luca Zanetti | 23m |
Proves two concrete claims: a Cheeger-type bound that the optimal reversible relaxation time is Theta(1/phi_match) up to a log N factor (uses SDP duality, a… | ||
| A variant of the VC-dimension with applications to depth-3 circuits | Peter Frankl, Svyatoslav Gryaznov, Navid Talebanfard | 30m |
Defines a new combinatorial measure, the universal r-dimension, and reduces its extremal estimate to counting independent sets in r-uniform hypergraphs via a… | ||
| Double Coverage with Machine-Learned Advice | Alexander Lindermayr, Nicole Megow, Bertrand Simon | 27m |
Defines Lambda-DC, an online k-server algorithm that interpolates between Double Coverage and Follow-the-Prediction by moving the predicted-side server at… | ||
| Vertex Fault-Tolerant Emulators | Greg Bodwin, Michael Dinitz, Yasamin Nazari | 30m |
Constructs vertex-fault-tolerant emulators that provably use fewer edges than comparable spanners: for multiplicative stretch 2k−1 spanners the known size is… | ||
| Distributed Vertex Cover Reconfiguration | Yannic Maus, Keren Censor-Hillel, Shahar Romem-Peled, Tigran Tonoyan | 35m |
Defines batched reconfiguration where each batch must be safe under any adversarial ordering (equivalently batch vertices form an independent set), and proves… | ||
| Convex Influences | Anindya De, Shivam Nadimpalli, Rocco A. Servedio | 28m |
Defines convex influence along a direction as the negated degree-two Hermite coefficient and shows it equals the infinitesimal rate at which Gaussian volume… | ||
| A Gaussian Fixed Point Random Walk | Yang P. Liu, Ashwin Sah, Mehtaab Sawhney | 20m |
Online vector balancing in the Komlós setting gets an explicit Markov-chain construction: a one-dimensional Gaussian fixed point walk whose stationary law is… | ||
| Maximizing revenue in the presence of intermediaries | Gagan Aggarwal, Kshipra Bhawalkar Lane, Guru Guruganesh, Andres Perlroth | 22m |
Proposal of an intermediate-proof mechanism that guarantees seller revenue within a constant factor of welfare for any demand structure when valuations are… | ||
| Mixing in non-quasirandom groups | W. T. Gowers, Emanuele Viola | 22m |
Paper proves concrete communication bounds for the three-party product=1 problem in three non-quasirandom, non-almost-abelian families: affine groups get… | ||
| Sample-based Proofs of Proximity | Guy Goldberg, Guy N. Rothblum | 28m |
Shows how query-based interactive proofs of proximity convert to sample-based ones with only Q samples and about Q + C communication, using k‑wise independent… | ||
| Nonlinear Repair Schemes of Reed-Solomon Codes | Roni Con, Itzhak Tamo | 29m |
Claims a nonlinear repair method for Reed‑Solomon codes over prime fields, proving almost all 2‑dimensional RS codes are asymptotically MSR for any number of… | ||
| Sublinear-Time Computation in the Presence of Online Erasures | Iden Kalemaj, Sofya Raskhodnikova, Nithin Varma | 23m |
Introduces an online erasure model where after each query an adversary can hide up to t entries and proves concrete testing limits: linearity is testable with… | ||
| Eliminating Intermediate Measurements using Pseudorandom Generators | Uma Girish, Ran Raz | 28m |
Proves that any quantum circuit with intermediate measurements, time T and space S, simulates to a measurement-free circuit in time T poly S and space S log T… | ||
| Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing | Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha | 25m |
Shows that in a smoothed model (noise whose covariance has nontrivial projection in every direction) the Banaszczyk bound improves to sqrt(log d)+sqrt(log log… | ||
| Mixing of 3-term progressions in Quasirandom Groups | Amey Bhangale, Prahladh Harsha, Sourya Roy | 28m |
Proves Gowers’ conjecture: for every finite d‑quasi‑random group the 3‑term progression counting form equals the product of expectations up to error… | ||
| On Fairness and Stability in Two-Sided Matchings | Gili Karni, Guy N. Rothblum, Gal Yona | 33m |
Shows that sampling fair hospital orders and running Gale Shapley fails via a 3x3 counterexample where two doctors in one cluster get systematically worse… | ||
| Quantum Meets the Minimum Circuit Size Problem | Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang | 37m |
Defines concrete quantum MCSP variants (Boolean, state, unitary) and proves MQCSP in QCMA as an upper bound and NP-hardness for a multi-output quantum MCSP… | ||
| Adversarially Robust Coloring for Graph Streams | Amit Chakrabarti, Prantar Ghosh, Manuel Stoeckl | 37m |
Shows a concrete lower bound: any adversarially robust k‑coloring algorithm for Δ‑bounded graphs uses Ω(n Δ^2 / k) space, so robust Δ+1 or O(Δ) colorings force… | ||
| Matroid Secretary is Equivalent to Contention Resolution | Shaddin Dughmi | 39m |
Main claim: the matroid secretary conjecture is equivalent (up to constant factors) to the statement that offline contention resolution and online random‑order… | ||
| Locality-Preserving Hashing for Shifts with Connections to Cryptography | Elette Boyle, Itai Dinur, Niv Gilboa, Yuval Ishai, Nathan Keller, Ohad Klein | 22m |
Constructs a locality-preserving hash that reads D bits and achieves error delta ≈ 1/D^2 and proves that delta ≥ 1/D^2 via a birthday-paradox lower bound, so… | ||
| Omnipredictors | Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, Udi Wieder | 37m |
Shows that a multi-calibrated predictor (computed from data via a weak agnostic learner and multicalibration algorithms) serves as an omnipredictor for… | ||
| Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity v | Harry Buhrman, Bruno Loff, Subhasree Patro, Florian Speelman | 31m |
Shows conditional linear quantum lower bounds for zero-edge-weight triangle and a list of computational geometry problems by quantizing classical fine-grained… | ||
| Pseudorandom Self-Reductions for NP-Complete Problems | Reyad Abed Elrazik, Robert Robere, Assaf Schuster, Gal Yehuda | 13m |
Claim: non-adaptive pseudorandom self-reduction for Max Clique (and every nontrivial hereditary max-subgraph problem) holds assuming the non-uniform planted… | ||
| Optimal Bounds for Dominating Set in Graph Streams | Sanjeev Khanna, Christian Konrad | 42m |
One-pass streaming Dominating Set on n-vertex graphs gets a constructive algorithm that uses Õ(n) space and returns an O(√n · polylog n)-approximation, with a… | ||
| Smaller ACC0 Circuits for Symmetric Functions | Brynmor Chapman, Ryan Williams | 23m |
Every symmetric Boolean function on n bits admits small constant‑depth circuits using composite moduli: for any ε>0 there exists a modulus m so a depth‑3 mod‑m… | ||
| Keep That Card in Mind: Card Guessing with Limited Memory | Boaz Menuhin, Moni Naor | 33m |
A deterministic algorithm using about log^2 N bits of memory tracks log N nested ranges and guarantees about half sqrt(M) correct guesses in expectation… | ||
| Multi-Channel Bayesian Persuasion | Yakov Babichenko, Inbal Talgam-Cohen, Haifeng Xu, Konstantin Zabarnyi | 26m |
Main technical claim: a communication structure M1 always yields at least as much sender value as M2 for every prior and every utility profile iff every… | ||
| Interactive Communication in Bilateral Trade | Jieming Mao, Renato Paes Leme, Kangning Wang | 16m |
Model where seller and buyer alternately send verifiable signals updating each other’s priors and seller sets a price at the end. Main theorem claims any… | ||
| Faster Sparse Matrix Inversion and Rank Computation in Finite Fields | Sílvia Casacuberta, Rasmus Kyng | 26m |
Claims a faster algorithm for inverting sparse n-by-n matrices over finite fields with expected time about O(n^{2.2131}) for O(n) nonzeros, by reducing A^{-1}… | ||
| Symmetric Sparse Boolean Matrix Factorization and Applications | Sitan Chen, Zhao Song, Runzhou Tao, Ruizhe Zhang | 29m |
Average-case result recovers a K‑sparse Boolean factor W from M = W W^T when each row of W is an independent uniform K‑subset, with high probability and… | ||
| Interaction Preserving Compilers for Secure Computation | Nico Döttling, Vipul Goyal, Giulio Malavolta, Justin Raizes | 33m |
A compiler converts an n‑round insecure protocol into a secure MPC with communication roughly equal to the original protocol (no multiplicative blowup, only an… | ||
| An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams | Sepehr Assadi, Vihan Shah | 21m |
An algorithm gives an alpha-approximate maximum matching in dynamic graph streams using n^2/alpha^3 bits of space (optimal up to constants) and works for alpha… | ||
| 3 + ε Approximation of Tree Edit Distance in Truly Subquadratic Time | Masoud Seddighin, Saeed Seddighin | 17m |
Proves a 3 + ε approximation for tree edit distance running in truly subquadratic time (about n^1.99). Converts rooted trees to strings via parenthesis… | ||
| Support Recovery in Universal One-bit Compressed Sensing | Soumyabrata Pal, Arya Mazumdar | 19m |
Universal one-bit schemes recover support with concrete measurement bounds: exact recovery requires roughly O(K^2 log(N/K)) measurements unless the dynamic… | ||
| Bounded indistinguishability for simple sources | Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Akshayaram Srinivasan | 36m |
Shows both positive and negative Braverman-style claims: for constant-degree/local sources constant k suffices to fool simple distinguishers, and depth‑one… | ||
| Small-Box Cryptography | Yevgeniy Dodis, Harish Karthikeyan, Daniel Wichs | 23m |
Three-step recipe gives concrete security bounds for SPN/AES-style designs: a reduced-round proof, a hardness-amplification cascade, and the Big-to-Small… | ||
| Individual Fairness in Advertising Auctions through Inverse Proportionality | Shuchi Chawla, Meena Jagadeesan | 29m |
Proposes and analyzes inverse proportional allocation that enforces a multiplicative-to-additive fairness constraint called value stability while retaining… | ||
| On Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization | Ronen Shaltiel, Emanuele Viola | 46m |
Asks whether scaling the Impagliazzo–Wigderson assumption yields an extreme high-end PRG (seed R = (1+o(1))·L, output M ≈ 2^{1−o(1)·L}, total compute ≈… | ||
| A Spectral Approach to Polytope Diameter | Nikhil Srivastava, Hariharan Narayanan, Rikhav Shah | 20m |
Constructs a weighted 1-skeleton from the Hessian of log-volume of the polar polytope, shows that Hessian has exactly one positive eigenvalue and decomposes as… | ||
| Uniform Bounds for Scheduling with Job Size Estimates | Ziv Scully, Isaac Grosof, Michael Mitzenmacher | 27m |
Single-server queuing with Poisson arrivals and multiplicative beta-alpha bounded noise on job size estimates gets a new rank-based scheduler RaDiCal that is… | ||
| Cursed yet Satisfied Agents | Yiling Chen, Alon Eden, Juntao Wang | 23m |
Defines the Wallet Game and shows cursed agents act like rational bidders with a cursed valuation that mixes true and signal-conditioned value, so truthful… | ||
| Lifting With Sunflowers | Ian Mertz, Shachar Lovett, Raghu Meka, Toniann Pitassi, Jiapeng Zhang | 36m |
Proves that many lifting theorems (tree‑like, DAG‑like, depth‑dependent) follow from a single sunflower‑based lemma, replacing lengthy casework with a short… | ||
| Improved Hardness of BDD and SVP Under Gap-(S)ETH | Huck Bennett, Chris Peikert, Yi Tang | 17m |
Shows fine-grained hardness reductions from SAT to lattice problems using locally dense gadgets and two-point counts, proving BDD cannot be solved in 2^{o(n)}… | ||
| Online Multivalid Learning: Means, Moments, and Prediction Intervals | Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M. Pai, Aaron Roth | 33m |
Provides algorithms that guarantee group-conditional uncertainty in an adversarial online setting: multi-calibration and 1−δ prediction-interval coverage for… | ||
| Low-bandwidth recovery of linear functions of Reed-Solomon-encoded data | Noah Shutty, Mary Wootters | 26m |
Shows a concrete scheme for Reed–Solomon codes that computes any linear function λ·f by downloading only o(b) bits, specifically Θ(b / log b) bits when using… | ||
| Extremely Deep Proofs | Noah Fleming, Toniann Pitassi, Robert Robere | 28m |
Proves that for resolution, k‑DNF resolution and cutting planes there are CNFs on n variables with polynomial‑size proofs but any subexponential‑size proof… | ||
| Monotone Complexity of Spanning Tree Polynomial Re-visited | Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, Partha Mukhopadhyay | 31m |
Shows that the spanning tree polynomial on theta(N) variables for constant-degree expander families requires monotone circuits of size 2^{Omega(N)}, giving the… | ||
| Excluding PH Pessiland | Shuichi Hirahara, Rahul Santhanam | 11m |
Proves unconditionally that PH Pessiland excluded by showing PH-average hardness is equivalent to existence of a PH-confutable pseudorandom generator (PH-PRG)… | ||
| Algebraic Restriction Codes and their Applications | Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, Maciej Obremski | 12m |
Defines an algebraic restriction code that encodes X0,X1 via a random N×M matrix R (M>N) so R·Xhat = X, forcing only scalar-on-X0-plus-X1 evaluations to decode… | ||
| Quantum Distributed Algorithms for Detection of Cliques | Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, Rotem Oshman | 24m |
Takes any classical distributed listing routine and converts it into a faster quantum detection routine by running nested Grover searches over carefully… | ||
| Probing to minimize | Weina Wang, Anupam Gupta, Jalani Williams | 34m |
Proves the first adaptive approximation for minimizing the minimum-weight element under a knapsack constraint with expected cost at most four times OPT while… | ||
| Fixed-Parameter Sensitivity Oracles | Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J. A. Gregor Lagodzinski, Martin Schirneck, Simon Wietheger | 22m |
Proposes fixed-parameter sensitivity oracles that preprocess a graph for up to f simultaneous edge failures while keeping parameter k fixed. For vertex cover… | ||
| On the Existence of Competitive Equilibrium with Chores | Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, Ruta Mehta | 32m |
Shows that deciding whether a competitive equilibrium exists with divisible chores is NP-hard to decide existence, gives two simple sufficient conditions that… | ||
| Optimal Sub-Gaussian Mean Estimation in Very High Dimensions | Jasper C.H. Lee, Paul Valiant | 24m |
Linear time algorithm that is sample optimal up to a 1+o(1) factor for very high dimensions where effective dimension >> (log 1/delta)^2. Main tool is a new… | ||
| Continuous Tasks and the Asynchronous Computability Theorem | Hugo Rincon Galeana, Sergio Rajsbaum, Ulrich Schmid | 27m |
Proves an iff characterization: a distributed task is wait-free shared-memory solvable exactly when there exists a continuous chromatic function carried by the… | ||
| A Complete Linear Programming Hierarchy for Linear Codes | Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones | 37m |
Constructs a family of polynomial-size linear programs (after factoring translation and permutation symmetries) that encode L‑point interactions via… | ||
| On the download rate of homomorphic secret sharing | Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, Mary Wootters | 24m |
Proves optimal linear HSS for low-degree polynomials with exact rate 1 - d t / k, gives a PIR instantiation with upload cost n^{1/d} and that download rate… | ||
| Indistinguishability Obfuscation of Null Quantum Circuits and Applications | James Bartusek, Giulio Malavolta | 19m |
Construction gives a candidate indistinguishability obfuscator for quantum circuits that always output zero (null circuits) under the quantum hardness of LWE… | ||
| Errorless versus Error-prone Average-Case Complexity | Shuichi Hirahara, Rahul Santhanam | 15m |
Paper proves reductions between error-prone heuristics and errorless average-case algorithms by building on non-adaptive average BPP/poly instant checker… | ||
| Local Access to Random Walks | Amartya Shankha Biswas, Edward Pyne, Ronitt Rubinfeld | 19m |
Provides a local-access algorithm that answers position-at-time queries on a random walk with per-query cost about (1/(1−λ))·√n (up to polylog factors), and… | ||
| Small Hazard-Free Transducers | Johannes Bund, Christoph Lenzen, Moti Medina | 13m |
Claims that every Mealy transducer on n inputs admits a hazard-free circuit of size O(n · 2^{|S|+e}) and depth O(|S| log n + e) where |S| is state count and e… | ||
| Symbolic determinant identity testing and non-commutative ranks of matrix Lie algebras | Gábor Ivanyos, Tushant Mittal, Youming Qiao | 34m |
Proves that many matrix Lie algebra representations produce singular matrix spaces that have no shrunk subspaces and, except for the zero or adjoint… | ||
| Circuit lower bounds for low-energy states of quantum code Hamiltonians | Anurag Anshu, Chinmay Nirkhe | 49m |
Proves a concrete circuit-depth lower bound for every low-energy state of Hamiltonians built from stabilizer codes, giving depth at least Θ(log D) and a second… | ||
| A Unifying Framework for Characterizing and Computing Width Measures | Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon | 30m |
Paper defines F-branch width and proves any reasonable cut-function comes from a partner-hereditary family, shows only six size-identifiable families matter… | ||
| Embeddings and labeling schemes for A* | Talya Eden, Piotr Indyk, Haike Xu | 19m |
Proves nearly tight tradeoffs between heuristic complexity and A scans: for Lp embeddings with dimension D < N/log N A scans Ω(N) on average; for L∞ or… | ||
| Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity | Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams | 24m |
Presents concrete Merlin–Arthur protocols and time bounds: near-linear MA for 3SUM by reducing to counting solutions mod d, encoding inputs as a polynomial… | ||
| Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs | Amey Bhangale, Aleksa Stankovic | 21m |
Proves that MAX-3-LIN over any finite non-abelian group is UFG NP-hard to approximate to (1−ε, 1/|G|+ε) and gives a matching UFG hardness for satisfiable… | ||
| Time-Traveling Simulators Using Blockchains and Their Applications | Vipul Goyal, Justin Raizes, Pratik Soni | 31m |
Defines a formal notion of time-traveling simulation where the simulator receives an F-block valid extension of the public chain and uses it to simulate… | ||
| An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes | Anubhav Baweja, Justin Jia, David P. Woodruff | 19m |
Claims a one plus epsilon PTAS for tournament Feedback Arc Set running in semi‑streaming memory using sampling and local moves. Algorithm approximates… | ||
| Pre-Constrained Encryption | Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, Giulio Malavolta | 38m |
Defines Pre-Constraint Encryption where an authority-generated decryption key K is limited to computing only a pre-authorized class of functions (and can… | ||
| Algorithms and Lower Bounds for Comparator Circuits from Shrinkage | Bruno P. Cavalar, Zhenjian Lu | 19m |
Proves an average-case lower bound: there is an explicit polynomial-time function f on n bits such that every comparator circuit with at most n^{1.5} gates… | ||
| Correlation detection in trees for planted graph alignment | Luca Ganassali, Marc Lelarge, Laurent Massoulié | 24m |
Works in the sparse constant-degree regime and reduces matching to correlation detection in trees by comparing neighborhoods up to depth D ≈ log n, using a… | ||
| Improved Decoding of Expander Codes | Xue Chen, Kuan Cheng, Xin Li, Minghui Ouyang | 26m |
Proves a new worst-case distance lower bound for any expander code: distance ≥ αn/(2ε) (and shows this is tight up to constants). Gives a linear-time decoder… | ||
| Interactive Proofs for Synthesizing Quantum States and Unitaries | Gregory Rosenthal, Henry Yuen | 21m |
Defines quantum analogs of function classes and proves concrete inclusions: state PSPACE ⊆ state QIP (completeness with exponentially small trace distance… | ||
| PCPs and Instance Compression from a Cryptographic Lens | Liron Bronfman, Ron D. Rothblum | 26m |
Assuming subexponential LWE, the work constructs publicly verifiable constant-query succinct PCAs for every bounded-depth NP relation by combining the JKKZ… | ||
| Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu | Mojtaba Hosseini, Vijay V. Vazirani | 29m |
Paper proposes Nash-bargaining-based matching models (one-sided and two-sided; Fisher and Arrow-Debreu) with explicit convex programs for linear, separable and… | ||
| Separating the NP-Hardness of the Grothendieck problem from the Little-Grothendieck problem | Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani | 37m |
Proves NP-hardness of approximating the (bilinear) Grothendieck problem strictly beyond the PSD bound: shows no polytime algorithm achieves better than π/2 +… | ||
| Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr | Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky | 30m |
Paper proves an exact correspondence: problems solvable in LOCAL O(log n) are precisely those that are L-full, and these coincide with the Baire (descriptive… | ||
| Adaptive Massively Parallel Constant-round Tree Contraction | MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh, Hsin-Hao Su | 29m |
Claims a constant-round AMPC algorithm for tree contraction, giving O(1/epsilon^2) rounds on trees with max degree ≤ n^epsilon and O(1/epsilon^3) rounds on… | ||
| On Semi-Algebraic Proofs and Algorithms | Noah Fleming, Mika Göös, Stefan Grosser, Robert Robere | 22m |
Shows that minimizing conical junta degree on the violations polynomial exactly matches Sherali‑Adams degree via a Hrubeš‑style factorization, uses slack… | ||
| Beating Classical Impossibility of Position Verification | Jiahui Liu, Qipeng Liu, Luowen Qian | 32m |
Constructs a position‑verification protocol where verifiers are entirely classical verifiers and all messages are classical, but the prover must be quantum… | ||
| A lower bound on the space overhead of fault-tolerant quantum computation | Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi | 33m |
Shows that for any non‑unitary qubit noise channel N any fault‑tolerant encoding needs at least n' ≥ α_N log T physical qubits (α_N computable from N), and if… | ||
| Deterministic Dynamic Matching In Worst-Case Update Time | Peter Kiss | 19m |
Presents deterministic dynamic algorithms that give a 2+ε approximate matching with polylog worst-case update time and a 3/2+ε guarantee in Õ(√n) worst-case… | ||
| Larger Corner-Free Sets from Combinatorial Degenerations | Matthias Christandl, Omar Fawzi, Hoang Ta, Jeroen Zuiddam | 25m |
Introduces a combinatorial degeneration method that views corner problems as independent sets in a 3-uniform hypergraph power and uses adjacency tensors to… | ||
| Secret Sharing, Slice Formulas, and Monotone Real Circuits | Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi | 33m |
Proves that recent secret sharing techniques cannot achieve subexponential complexity by exhibiting a monotone P function whose schemes (and corresponding… | ||
| Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems | Shiri Antaki, Quanquan C. Liu, Shay Solomon | 31m |
Deterministic distributed algorithms implement dynamic symmetry-breaking with near-optimal message costs: Delta+1 coloring and maximal matching use O(m^{1/2})… | ||
| Optimal Deterministic Clock Auctions and Beyond | George Christodoulou, Vasilis Gkatzelis, Daniel Schoepflin | 24m |
Presents concrete algorithms and tight guarantees: a deterministic water-filling clock auction that provably achieves a 4·log|O| approximation for any… | ||
| Multiscale entropic regularization for MTS on general metric spaces | Farzam Ebrahimnejad, James R. Lee | 34m |
Shows a concrete algorithm: mirror descent with a multi-scale entropic regularizer run on a constructed DAG over the metric, not on random HSTs. Builds a DAG… | ||
| Beating the Folklore Algorithm for Dynamic Matching | Mohammad Roghani, Amin Saberi, David Wajc | 23m |
Deterministic algorithm achieves a deterministic (2−ε)-approx for fully dynamic matching with worst-case update time n^{3/4}. It maintains an epsilon-D kernel… | ||
| Correlation-Intractable Hash Functions via Shift-Hiding | Alex Lombardi, Vinod Vaikuntanathan | 29m |
Gives a simple self-reduction showing that a shift-hiding PRF that is one-way on the zero output yields correlation-intractable hash families for many… | ||
| Domain Sparsification of Discrete Distributions using Entropic Independence | Nima Anari, Michal Derezinski, Thuy-Duong Vuong, Elizabeth Yang | 22m |
Proves that for any distribution satisfying entropic independence with parameter alpha a preprocessed sampler reduces the ground set from N to about… | ||
| Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions | Lijie Chen, Shuichi Hirahara, Neekon Vafa | 31m |
Proves concrete average-case hardness from weaker worst-case fine‑grained assumptions: improving on Hirahara’s 2^{O(N/log N)} threshold, the paper shows that… | ||
| Dynamic Matching Algorithms Under Vertex Updates | Hung Le, Lazar Milenkovic, Shay Solomon, Virginia Vassilevska Williams | 26m |
Maintains maximal matchings under vertex insertions and deletions with a concrete tradeoff: a simple bipartite algorithm (one side fixed) is irrevocable and… | ||
| Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems | François Le Gall, Saeed Seddighin | 18m |
Presents quantum algorithms for longest palindromic substring and longest common substring with concrete bounds: LPS solved in sqrt(n) time (with matching… | ||
| Testing Distributions of Huge Objects | Oded Goldreich, Dana Ron | 28m |
Defines the DOHO model—sampling distributions over length-n strings with queries to sampled bits and distance measured by the earthmover's distance under… | ||
| Mechanism Design with Moral Bidders | Shahar Dobzinski, Sigal Oren | 21m |
Defines an alpha-moral bidder model where a bidder lies only if profit > alpha × sum of others' losses; constructs deterministic single-item mechanisms and… | ||
| Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE | Zvika Brakerski, Vinod Vaikuntanathan | 21m |
Constructs a lattice-inspired candidate that aims for polylogarithmic ciphertext size for broadcast encryption and ciphertext-policy ABE, built by flipping a… | ||
| Lower Bounds for Symmetric Circuits for the Determinant | Anuj Dawar, Gregory Wilsenach | 43m |
Proves an exponential lower bound for determinant on arithmetic circuits that are symmetric under Alt_n × Alt_n, separating that model from the known… | ||
| The Space Complexity of Sampling | Eshan Chattopadhyay, Jesse Goodman, David Zuckerman | 45m |
Shows explicit lower bounds: any read-once branching program of width 2^{0.01N} outputs a distribution exponentially far from the uniform distribution over a… | ||
| Small Circuits Imply Efficient Arthur-Merlin Protocols | Michael Ezra, Ron D. Rothblum | 34m |
Assumes a polynomial-size DNF of parities that computes the inner product on > 5/6 accuracy and derives extremely efficient public-coin (AM/R2) protocols… | ||
| Noisy Boolean Hidden Matching with Applications | Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou | 23m |
Defines p-noisy Boolean hidden matching where each matching edge flips independently with probability p and proves the plaintext protocol is optimal, giving… | ||
| Randomness Extraction from Somewhat Dependent Sources | Marshall Ball, Oded Goldreich, Tal Malkin | 31m |
Defines three dependence models and gives sharp positive and negative results: T-coordinated sources admit deterministic extraction — any two‑source extractor… | ||
| Uniform brackets, containers, and combinatorial Macbeath regions | Kunal Dutta, Arijit Ghosh, Shay Moran | 32m |
Shows an equivalence: having ε‑containers or λ‑heavy ε M‑nets for both a set system and its complement suffices to produce uniform ε‑brackets, and vice versa… | ||
| FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs | Balaram Behera, Edin Husić, Shweta Jain, Tim Roughgarden, C. Seshadhri | 26m |
Proves fixed-parameter algorithms that enumerate specific near-cliques in c-closed graphs, with concrete bounds: FPT enumeration of maximal (d+1)-plexes in… | ||
| Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs | Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan | 20m |
Gives a randomized algorithm that approximates and samples perfect matchings in d-regular ε-spectral expanders in time n^{o(log d)} (more precisely n^{o(log d)… | ||
| nothing matches | ||