ITCS 2023
who it's for
theoretical computer scientists, complexity theorists, algorithm designers, cryptographers, quantum computing researchers, distributed systems researchers, privacy and fairness researchers
topics
constant-depth sorting networks; oracle and constructivity methods; Jordan normal form bit complexity; matrix multiplication via matrix groups; majority dynamics with adversarial schedulers; guarded extension variables in proofs; differentially private continual releases; graph algorithms with predictions; limits of QAOA via polynomial approximations; quantum cryptography hardness assumptions; interactive proofs of proximity; TFNP and proof-system characterizations
| title | author | length |
|---|---|---|
| Constant-depth sorting networks | Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii | 45m |
Considers sorting under k-sorting networks where each unit sorts k positions in one layer, uses the 0-1 principle and a new access technique to prove exact and… | ||
| Black-box Constructive Proofs are Unavoidable | Lijie Chen, Ryan Williams, Tianqi Yang | 21m |
Main claim: proving NEXP not in a typical circuit class C is equivalent to the existence of a black-box constructivity — a randomized poly(n)-time oracle… | ||
| On Oracles and Algorithmic Methods for Proving Lower Bounds | Nikhil Vyas, Ryan Williams | 16m |
Proves an equivalence between missing string circuit complexity and whether Σ2E requires exponential-size circuits relative to every oracle, constructs uniform… | ||
| On disperser/lifting properties of the Index and Inner-Product functions | Paul Beame, Sajin Koroth | 29m |
Proves two concrete limits and one positive construction: shows simulation-based lifting methods cannot push gadget size below m < log n − ω(1) by giving… | ||
| Bit Complexity of Jordan Normal Form and Spectral Factorization | Nikhil Srivastava, Ravindran Kannan, Nick Ryder, Papri Dey | 25m |
Gives a concrete, polynomial‑time procedure that either computes a matrix polynomial spectral factor q (to error ε in coefficient norm) or certifies none… | ||
| Certification with an NP Oracle | Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan | 16m |
Checking a claimed certificate is coNP-complete, and under P ≠ NP no algorithm finds a certificate of size φ(k) for any rapidly growing φ. With access to an NP… | ||
| Matrix multiplication via matrix groups | Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans | 23m |
Paper proves in the Cohn–Umans group-theoretic framework that groups of Lie type cannot yield omega = 2, by combining Gowers’s quasirandomness bounds (PSL(2… | ||
| TFNP Characterizations of Proof Systems and Monotone Circuits | Noah Fleming, Sam Buss, Russell Impagliazzo | 20m |
Paper proves necessary and sufficient conditions for when TFNP classes correspond to proof systems and to monotone-circuit models, and constructs a formal… | ||
| Resilience of 3-Majority Dynamics to Non-Uniform Schedulers | Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov | 40m |
Defines a p-epsilon scheduler that lets an adversary pick, each round, a distribution over triplets within Lp distance ε of uniform and shows precise… | ||
| Beyond Worst-Case Budget-Feasible Mechanism Design | Aviad Rubinstein, Junyao Zhao | 20m |
Presents a simple randomized mechanism that partitions sellers, learns a best lottery of two take-it-or-leave-it payments on each half, and offers samples from… | ||
| Exponential separations using guarded extension variables | Emre Yolcu, Marijn Heule | 25m |
Proves exponential separations between redundancy-based CNF proof systems by embedding short extended‑resolution (ER) proofs into guarded formulas so only some… | ||
| HappyMap: A Generalized Multicalibration Method | Zhun Deng, Cynthia Dwork, Linjun Zhang | 19m |
A postprocessing method called HappyMap algorithm maps any predictor to satisfy a new fairness/robustness condition, s-Happy Multicalibration, by iteratively… | ||
| Worst-Case to Expander-Case Reductions | amir Abboud, Nathan Wallheimer | 23m |
Shows that many graph problems reduce to expander instances by a simple gadget: add an expansion layer U of about n vertices and randomly connect original… | ||
| On computing homological hitting sets | Ulrich Bauer, Abhishek Rathod, Meirav Zehavi | 25m |
Defines the minimum homological hitting set problem and gives three concrete results: a polynomial‑time algorithm on triangulated closed surfaces that finds an… | ||
| Proofs of Quantumness from Trapdoor Permutations | Tomoyuki Morimae, Takashi Yamakawa | 17m |
Constructs proofs of quantumness from trapdoor permutations by coherently executing interactive hashing and then running a KMCVY22-style challenge, replacing… | ||
| A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems | Monika Henzinger, Billy Jin, Richard Peng, David Williamson | 20m |
Introduces a dual cut-toggling algorithm for solving Lx = b that mirrors KOSZ: it maintains vertex potentials on a low-stretch spanning tree, samples… | ||
| Generalized Private Selection and Testing with High Confidence | Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer | 26m |
A unified framework produces a private selection algorithm that attains 2 + o(1) pure DP selection from arbitrarily many epsilon‑DP candidates by randomized… | ||
| All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method | Sepehr Assadi, Aaron Bernstein, Zachary Langley | 27m |
Algorithm gives a semi-streaming (O~(n) space) method that uses the multiplicative weights update method to reduce all-norm load balancing to an oracle solved… | ||
| Secure Distributed Network Optimization Against Eavesdroppers | Yael Hitron, Merav Parter, Eylon Yogev | 19m |
Claims an f-secure CONGEST framework that protects against an oblivious, computationally unbounded eavesdropper who sees all messages on up to f edges, with… | ||
| Is it easier to count communities than find them? | Cynthia Rush, Fiona Skerman, Alexander S Wein, Dana Yang | 24m |
Defines a planted dense submatrix model with additive Gaussian noise and studies testing between one planted community and M planted communities (the count 1… | ||
| Graph Searching with Predictions | Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li | 19m |
Shows that with per-node distance hints an algorithm called TreeX finds a goal in a tree with total movement O(D + Δ·e), where D is true root–goal distance, Δ… | ||
| Symmetric Formulas for Products of Permutations | William He, Benjamin Rossman | 20m |
Proves that the permutation-matrix product decision problem PMM_{k,n} requires size n^{Ω(log k)} for formulas invariant under the shifted-diagonal Sn^{k-1}… | ||
| Algorithms with More Granular Differential Privacy Guarantees | Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke | 26m |
Defines per-attribute differential privacy and gives concrete algorithms that trade per-person epsilon for much smaller per-attribute epsilon0. Uses Gaussian… | ||
| Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds | Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena | 15m |
Proves that noisy-CAS vs CAS can incur the worst-case slowdown Θ(log n): any adaptive protocol that uses √n rounds on CAS yields an equivalent beeping (OR)… | ||
| Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly | Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu | 18m |
Claim: p pass streaming algorithms need space Theta(n^{deg(f)}) to compute Max‑CSPf exactly where deg(f) is f's multilinear polynomial degree and p is… | ||
| Lifting to Parity Decision Trees Via Stifling | Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif | 17m |
Proves a concrete lifting theorem: parity decision tree (PDT) size of S composed with majority on 3 bits is at least 2^{DT(S)}, and more generally if gadget g… | ||
| An Algorithmic Bridge Between Hamming and Levenshtein Distances | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha | 23m |
Presents a 1+ε approximation algorithm for the new EDa metric (substitution cost 1/a, indel cost 1) that runs sublinearly for realistic parameters: overall… | ||
| An Improved Lower Bound for Matroid Intersection Prophet inequalities | Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg | 25m |
Proves an improved impossibility: the prophet inequality for an intersection of q partition matroids is at least q^{1/2+1/\log\log q} (so super-√q). Uses the… | ||
| A subpolynomial-time algorithm for the free energy of one-dimensional... | Hamza Fawzi, Omar Fawzi, Samuel Scalet | 24m |
Algorithm computes thermodynamic-limit free energy for translation-invariant 1D quantum chains with error ε in time exp(O(log(1/ε)/log log(1/ε))) — a… | ||
| The Strength of Equality Oracles in Communication | Toniann Pitassi, Morgan Shirley, Adi Shraibman | 18m |
Provides tight (up to polylog factors) characterizations of NP^EQ, ∃·EQ, UP^EQ and U·EQ in terms of the blocky covering number, the blocky partition number… | ||
| Certificate games | Sourav Chakraborty, Anna Gal, Sophie Laplante, Rajat Mittal, Anupa Sunny | 21m |
Defines a zero-communication certificate game that yields four complexity measures: CG (private randomness), CG_pub (shared randomness), CG (shared… | ||
| Clustering Permutations: New Techniques with Streaming Applications | Diptarka Chakraborty, Debarati Das, Robert Krauthgamer | 26m |
Presents a concrete algorithm that gives a 1.99-approximation for the Ulam 1‑median (improving over the prior 2−ε with ε ≈ 2^−40), extends to k‑median and… | ||
| Is This Correct? Let's Check! | Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan | 20m |
Model builds knowledge as a preferential attachment tree with hidden truth labels, random errors at rate epsilon, and random checks of ancestor chains of depth… | ||
| Private Counting of Distinct and k-Occurring Items in Time Windows | Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Jelani Nelson | 27m |
Paper gives private algorithms for counting distinct and k-occurring items over time windows by reducing these queries to differentially private range queries… | ||
| Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations | Anurag Anshu, Tony Metger | 28m |
Proves Gaussian-style concentration for the Hamming weight distribution of n-qubit outputs by building local approximations via low-degree polynomial… | ||
| On Identity Testing and Noncommutative Rank Computation over the Free Skew Field | V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, Ramya C | 28m |
Gives deterministic reductions and concrete bounds: a size-s rational formula with inversion height h is identity-preserving under a sparsification to 2(h+1)… | ||
| New Lower Bounds and Derandomization for ACC, and a... | Lijie Chen | 22m |
Proves concrete circuit lower bounds and derandomizations: shows MA_sub_ACC0 has no n^k-size ACC0 circuits by building an AC0-parity verifier from a… | ||
| Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence | Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, Aleksandrs Slivkins | 25m |
Gradient-based pacing algorithms update a single multiplier per advertiser and, without ever converging to an equilibrium, guarantee expected liquid welfare at… | ||
| False Consensus, Information Theory, and Prediction Markets | Yuqing Kong, Grant Schoenebeck | 23m |
Proves that when private signals are conditional independence (substitutes), any epsilon-approximate consensus (agents’ mutual information with outcome ≤ ε… | ||
| Online Pen Testing | Mingda Qiao, Gregory Valiant | 21m |
Defines an online “pen testing” model where testing reduces an option’s value by threshold theta and passing reveals only residual value; proves a universal… | ||
| The Complexity of Infinite-Horizon General-Sum Stochastic Games | Yujia Jin, Vidya Muthukumar, Aaron Sidford | 20m |
Shows that finding an approximate Nash for infinite-horizon general-sum stochastic games is PPAD-complete both for simultaneous and for turn-based models under… | ||
| What Can Cryptography Do For Decentralized Mechanism Design? | Elaine Shi, Hao Chung, Ke Wu | 20m |
Paper proves that adding cryptography — a practical MPC-assisted model where many miners run an honest-majority multi‑party computation over user bids — lets… | ||
| List Agreement Expansion from Coboundary Expansion | Roy Gotlib, Tali Kaufman | 18m |
Claim: if a pure simplicial complex has coboundary expansion over S_l in every link and 1-up agreement expansion then list agreement testing succeeds with 3l… | ||
| Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes | Lunjia Hu, Charlotte Peale | 23m |
Defines Comparative Learning and proves that the sample complexity is governed by the mutual VC dimension, not the individual VC dimensions; gives a… | ||
| Differentially Private Continual Releases of Streaming Frequency Moment Estimations | Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong | 18m |
A differentially private streaming algorithm estimates Lp frequency moments over T rounds with 0.9 probability and gives explicit multiplicative and additive… | ||
| Quantum Proofs of Deletion for Learning with Errors | Alexander Poremba | 21m |
Constructs LWE-based public-key and homomorphic encryption schemes that produce a single quantum ciphertext whose Fourier-basis measurement yields a classical… | ||
| Consensus Division in an Arbitrary Ratio | Paul W. Goldberg, Jiawei Li | 27m |
Shows that for alpha = l/k rationals worst-case lower bound is about 2(k−1)/k · n cuts and gives matching upper bounds for a large subset Q of rationals, while… | ||
| Counting Subgraphs in Somewhere Dense Graphs | Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth | 26m |
Classifies parameterized complexity of counting homomorphisms, (induced) subgraphs when both pattern and host classes are structured: FPT occurs exactly when… | ||
| Is Untrusted Randomness Helpful? | Uma Girish, Ran Raz, Wei Zhan | 20m |
Defines a model where an algorithm gets many adversarial untrusted random bits plus k truly random bits and may output 0,1 or "I don't know", formalized as… | ||
| Making Auctions Robust to Aftermarkets | Moshe Babaioff, Nicole Immorlica, Yingkai Li, Brendan Lucier | 25m |
Uniform-price auctions can collapse once unconstrained resale exists: equilibrium welfare can drop to price of anarchy Θ(log m) because speculators buy many… | ||
| Decision Making under Miscalibration - 8 minute | Jodi Yona | 09m |
Defines a regret notion under bounded miscalibration and computes minimax optimal threshold formulas (closed form under several miscalibration metrics) that… | ||
| Decision Making under Miscalibration | Guy N. Rothblum, Gal Yona | 21m |
Defines a minimax threshold ĵ that minimizes worst-case regret under a bounded miscalibration α and shows closed-form answers for both expected and max… | ||
| Epic Fail: Emulators can tolerate some edge faults for free | Greg Bodwin, Michael Dinitz, Yasamin Nazari | 28m |
Proves that emulators can tolerate many edge failures without growing size: constructs f-edge-fault-tolerant 5-emulators that remain on n^{4/3} edges using a… | ||
| Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique | Pasin Manurangsi | 28m |
Reduction from the exponential biclique problem maps a bipartite graph to its adjacency matrix as a concept class, then applies random edge sparsification… | ||
| Karchmer-Wigderson Games for Hazard-free Computation | Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh | 23m |
Defines a hazard-free Karchmer-Wigderson game and proves its communication cost exactly matches hazard-free formula depth and its protocol size matches formula… | ||
| Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom | Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang | 20m |
Gives an efficient procedure that, using four copies of an n‑qubit state, samples the scaled convolution q_psi of the Weyl‑operator characteristic distribution… | ||
| Asynchronous Multi-Party Quantum Computation | Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, Joao Ribeiro | 16m |
Claims an asynchronous multi‑party quantum computation protocol that achieves statistical security and guaranteed output delivery up to a tight <1/4 corruption… | ||
| A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators | Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer | 26m |
Presents a concrete algorithmic framework that combines difference estimators with differential privacy to convert oblivious streaming routines into… | ||
| Efficient algorithms for certifying lower bounds on the discrepancy of random matrices | Prayaag Venkat | 22m |
Proves a deterministic polynomial-time algorithm that with high probability certifies discrepancy ≥ exp(−n^2/m) for an m×n Gaussian matrix, and a… | ||
| Unsplittable Euclidean Capacitated Vehicle Routing: A 2+\epsilon)(2+ϵ)-Approximation Algorithm | Fabrizio Grandoni, Claire Mathieu, Hang Zhou | 22m |
Proves a 2+ε approximation for unsplittable Euclidean CVRP with arbitrary demands by clustering small terminals in each cell into ε-sized groups, moving… | ||
| Rounding via Low Dimensional Embeddings | Mark Braverman, Dor Minzer | 27m |
Shows a concrete rounding scheme using project to R2/R3 and hyperplane-style cuts that deliberately avoid heavy segments, yielding improved max‑cut guarantees… | ||
| Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses | Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi | 24m |
Shows that for any dense-enough sparse random max-CSP the optimal satisfiable fraction equals a random-assignment baseline plus an explicit 1/√α second-order… | ||
| On the computational hardness needed for quantum cryptography | Zvika Brakerski, Ran Canetti, Luowen Qian | 20m |
Defines EFI pairs (efficiently sampleable, statistically far but quantumly indistinguishable mixed states) and shows they imply commitments, oblivious… | ||
| Vertex Sparsification for Edge Connectivity in Polynomial Time | Yang P. Liu | 22m |
Constructs c-edge-connectivity mimicking networks with about k c^3 edges (or kc^3 · polylog n) in randomized polynomial time, improving prior kc^4-size… | ||
| Kolmogorov Complexity Characterizes Statistical Zero Knowledge | Eric Allender, Shuichi Hirahara, Harsha Tirumala | 29m |
Main theorem: for any reasonable promise problem A, A in NISZK iff A RP many-one reduces to RK (with RK using approximation error e(m) ≈ Θ(log^2 m)), and A in… | ||
| Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP | Amol Pasarkar, Christos Papadimitriou, Mihalis Yannakakis | 32m |
Paper defines a two-player long choice game on 2^n pigeons whose iterated-majority argument yields class PLC; it reduces the classic pigeonhole circuit (PPP)… | ||
| Fractional certificates for bounded functions | Shachar Lovett, Jiapeng Zhang | 22m |
Defines epsilon-fractional certificate complexity and proves that any bounded function f with polynomial degree D satisfies Fc_eps(f) = O(D^8 log^16 n / eps^4)… | ||
| Expander Decomposition in Dynamic Streams | Arnold Filtser, Michael Kapralov, Mikhail Makarov | 24m |
This work shows a dynamic-stream algorithm that produces an expander decomposition reaching the optimal ε–φ tradeoff while using O(n/φ^2) memory but requiring… | ||
| Beeping Shortest Paths via Hypergraph Bipartite Decomposition | Fabien Dufoulon, Yuval Emek, Ran Gelles | 19m |
Distributed beeping networks compute single and multiple shortest paths with concrete bounds: a single-path algorithm runs in O(D log log n + log^3 n) rounds… | ||
| PPP-Completeness and Extremal Combinatorics | Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček, Alon Rosen, Nikolaj Ignatieff Schwartzbach | 28m |
Paper proves PWPP corresponds to “weak” extremal theorems and PPP to “strong” ones, gives many new natural completions, and builds explicit reductions using… | ||
| Incompressiblity and Next-Block Pseudoentropy | Iftach Haitner, Noam Mazor, Jad Silbak | 21m |
Shows that a distribution that is k incompressible yields k−2 next‑bit pseudoentropy and that incompressibility is equivalent (up to two bits) to a strong… | ||
| Unitary property testing lower bounds by polynomials | Adrian She, Henry Yuen | 20m |
A method shows any T-query tester that accesses an unknown unitary U and U^{-1} has acceptance probability given by a degree ≤2T multivariable polynomial, and… | ||
| Quantum space, ground space traversal, and how to embed multi-prover... | Dorian Rudolph, Sevag Gharibian | 22m |
Shows that QCMASPACE = NEXP, so allowing an exponentially long classical streamed proof breaks Savitch‑style collapse; proves a universal path‑following lemma… | ||
| Necessary Conditions in Multi-Server Differential Privacy | Albert Cheu, Chao Yan | 15m |
Shows that the non-interactive multi-server differential privacy model cannot learn parity with polynomial samples against an unbounded adversary when up to… | ||
| Making Decisions under Outcome Performativity | Michael P. Kim, Juan C. Perdomo | 27m |
Defines performative omnipredictor: a regression p(x,y') that, after a simple post‑processing, simultaneously approximates performative optima for any loss set… | ||
| A New Conjecture on Hardness of Low-Degree 2-CSP’s with... | Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan | 24m |
Conjectures that a d-to-d bipartite 2-CSP conjecture with d = 2^{log^{ε} n}, completeness 0.5 and soundness s = 2^{-log^{0.5+ε} n} is NP-hard, and shows this… | ||
| On Interactive Proofs of Proximity with Proof-Oblivious Queries | Oded Goldreich, Guy N. Rothblum, Tal Skverer | 24m |
Authors Oded Goldreich, Guy N. Rothblum and Tal Skverer show a concrete exponential separation between property testing and interactive proofs of proximity… | ||
| Quantum algorithms and the power of forgetting | Amin Shiraz Gilani, Andrew M. Childs, Matthew Coudron | 22m |
Main claim: no polynomial-query genuine rooted quantum algorithm finds an entrance→exit path in the three-colored welded-tree oracle. Proof builds an address… | ||
| Exact Completeness of LP Hierarchies for Linear Codes | Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones | 30m |
Shows that the LP hierarchy for linear binary codes recovers the exact maximum code size once the level reaches level n (previously only known to converge by… | ||
| Learning versus Pseudorandom Generators in Constant Parallel Time | Shuichi Hirahara, Mikito Nanashima | 25m |
Proves an equivalence: existence of polynomial-stretch pseudorandom generators computable in NC0 is characterized by average-case hardness of weak learning for… | ||
| Strategyproof Scheduling with Predictions | Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan | 25m |
Paper designs a strategyproof scheduling mechanism called scaled greedy that caps per-job scaling to avoid worst-case blowups, proving it is strategyproof… | ||
| Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks | Antoine El-Hayek, Monika Henzinger, Stefan Schmid | 24m |
Proves that broadcast, k‑broadcast and cover‑of‑size‑k in synchronous adversarial dynamic networks all have asymptotically tight linear worst‑case time. Upper… | ||
| Improved Monotonicity Testers via Hypercube Embeddings | Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer | 26m |
Shows a distance-preserving embedding that reduces monotonicity testing on product domains (p-biased cubes and hypergrids) to the uniform hypercube, so any… | ||
| Online Learning and Bandits with Queried Hints | Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala | 22m |
Algorithm queries an ML model with two candidate actions (or arms) and plays the chosen one, coupling differentially private Laplace noise with a… | ||
| Opponent Indifference in Rating Systems: A Theoretical Case for Sonas | Greg Bodwin, Forest Zhang | 22m |
Defines an axiom called opponent indifference and proves any one‑dimensional, memoryless, zero‑sum rating satisfying it has a constant K and a separable skill… | ||
| Matroid Partition Property and the Secretary Problem | Dorna Abdolazimi, Anna Karlin, Nathan Klein, Shayan Oveis Gharan | 25m |
Proves that no algorithm which first reduces a matroid to a partition matroid (possibly after sampling a beta fraction) and then runs the standard secretary… | ||
| The Time Complexity of Consensus Under Oblivious Message Adversaries | Hugo Rincon Galeana, ami Paz, Stefan Schmid, Ulrich Schmid, Kyrill Winkler | 19m |
Establishes the first time complexity lower bounds for consensus under oblivious message adversaries and rephrases Coulouma et al.’s solvability criterion as a… | ||
| Efficiently Testable Circuits | Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Pietrzak | 21m |
Claims a compiler that maps any Boolean circuit C into Ĉ, T̂ compiler so the compiled circuit is functionally equivalent, increases size by only a constant… | ||
| Learning Reserve Prices in Second-Price Auctions | Yaonan Jin, Pinyan Lu, Tao Xiao | 32m |
Proves that learning an optimal anonymous reserve for second-price auctions needs nearly-tight sample complexity equal to prior Myerson bounds while crucially… | ||
| Bootstrapping Homomorphic Encryption via Functional Encryption | Nir Bitansky, Tomer Solomon | 23m |
Claims a method to bootstrap a leveled homomorphic scheme into FHE from semi-compact public-key FE under polynomial assumptions for uniform adversaries and… | ||
| Downward self-reducibility in TFNP | Prahladh Harsha, Daniel Mitropolsky, Alon Rosen | 27m |
Paper proves that if a TFNP search problem is downward self-reducible then it lies in PLS, and that circuit-style d.s.r. with poly-blowup also implies PLS… | ||
| Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments | Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, Janani Sundaresan | 19m |
Handles fully dynamic online d‑dimensional scheduling with m machines and proves a randomized algorithm against an oblivious adversary achieves competitive… | ||
| Recovery from Non-Decomposable Distance Oracles | Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang | 24m |
Study of locating an unknown length-n sequence from distance queries for non-decomposable metrics focuses on DTW and gives concrete bounds and constructions… | ||
| Loss Minimization through the lens of Outcome Indistinguishability | Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder | 24m |
Paper proves that requiring loss OI—Outcome Indistinguishability for a loss-derived distinguisher class—is sufficient to get an Omnipredictor, with learning… | ||
| nothing matches | ||