ITCS 2021
who it's for
theoretical computer scientists, complexity theorists, quantum computing researchers, algorithm designers, machine learning researchers, distributed systems researchers, market design researchers
topics
planted clique hypothesis; trace reconstruction algorithms; list-recovery threshold computation; QBF CDCL versus Q-resolution; linear cross-entropy benchmarking limits; hardness of training ReLU networks; pseudorandom generators for permutation branching programs; distributed load balancing frameworks; lower bounds for off-chain plasma protocols; interactive proofs for verifying machine learning
| title | author | length |
|---|---|---|
| The entropy of lies: playing twenty questions with a liar | Yuval Dagan, Yuval Filmus, Daniel Kane, Shay Moran | 23m |
Distributional 20 Questions with up to K lies requires on average H(mu) + K·H2(mu) yes/no queries, where H(mu) + K·H2(mu) is tight (matching lower bound up to… | ||
| Comparing computational entropies below majority (or: When is the dense model theorem false?) | Russell Impagliazzo, Sam McGuire | 39m |
Shows explicit separations proving the dense model theorem false below majority: constructions of delta-dense distributions that are pseudorandom for small… | ||
| Algorithmic Persuasion with Evidence | Martin Hoefer, Pasin Manurangsi, Alexandros Psomas | 28m |
Paper at ITCS 2021 studies persuasion with unforgeable evidence, gives a polynomial-time max-flow algorithm that computes a sequential equilibrium, and proves… | ||
| The Complexity of Finding Fair Independent Sets in Cycles | Ishay Haviv | 19m |
Shows that finding an independent set in a cycle that picks about half from each given part is PPA-complete, and that the version asking for two disjoint such… | ||
| Sharp Threshold Rates for Random Codes | Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters | 16m |
Characterizes exact threshold rates for a wide class of monotone symmetric properties of completely random codes: R = 1 − max_tau H_q(tau)/b, shows these… | ||
| Pseudorandom Generators for Unbounded-Width Permutation Branching Programs | William Hoza, Edward Pyne, Salil Vadhan | 26m |
Presents an explicit INW-style generator that has seed length O(log n log(1/ε) + log n log log n) for permutation branching programs of arbitrary width, proved… | ||
| Pipeline Interventions | Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth, Juba Ziani | 25m |
Layered graphical model where agents follow stochastic transition matrices and a central planner pays convex costs to change those matrices under budget B… | ||
| A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits | Mrinal Kumar, Ben Lee Volk | 27m |
Paper proves an explicit existential bound: for non-rigid n-by-n matrices with parameters εn and εn^2 there exists an equation of degree O(n^3) vanishing on… | ||
| The Strongish Planted Clique Hypothesis and Its Consequences | Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm | 24m |
Postulates that for kappa = N^{0.1} planted clique cannot be solved in time N^{o(log N)} and uses a randomized graph product that samples N random L‑vertex… | ||
| Sample efficient identity testing and independence testing of quantum states | Nengkun Yu | 09m |
Constructs an explicit independent measurement M on a D-dimensional state whose post-measurement classical distributions satisfy ||P-Q||_2 =… | ||
| Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution | Olaf Beyersdorff, Benjamin Böhm | 28m |
Paper proves that standard QBF CDCL and Q-resolution are incomparable by giving two explicit families: QParity has polynomial-size QCDCL refutations but… | ||
| The Quantum Supremacy Tsirelson Inequality | William Kretschmer | 20m |
Proves a query lower bound for linear cross-entropy benchmarking: any polynomial-time quantum algorithm needs about 2^{n/4} queries to beat the trivial quantum… | ||
| A New Model for Ant Trail Formation and its Convergence Properties | Moses Charikar, Shivam Garg, Deborah M. Gordon, Kirankumar Shiragur | 33m |
A flow-based pheromone model on directed graphs is defined with decay, node leakage and forward/backward unit flows and a linear decision rule; for two… | ||
| Approximately Strategyproof Tournament Rules in the Probabilistic Setting | Kimberly Ding, S. Matthew Weinberg | 23m |
Shows that for independent, weakly ε-bounded probabilistic tournaments two natural recursive rules—randomized deathmatch and randomized single‑elimination… | ||
| Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming! | Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana | 36m |
Establishes one-pass streaming bounds for estimating the number of monochromatic edges given a coloring: an algorithm that stores sample R of size n/√T (first… | ||
| The Variable-Processor Cup Game | Alek Westover, William Kuszmaul | 19m |
Shows that allowing P to vary changes guarantees drastically: the greedy emptier remains optimal versus deterministic adversaries but its backlog jumps from… | ||
| Complexity measures on symmetric group and beyond | Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals | 33m |
Defines an abstract simplicial complex framework that extends degree, decision tree complexity and sensitivity from the hypercube to domains like the symmetric… | ||
| Comparison Graphs: a Unified Method for Uniformity Testing | Uri Meir | 36m |
Defines comparison graph as which sample pairs to compare and proves a structural theorem: if the graph has enough edges and few two-paths dependencies then… | ||
| Circular Trace Reconstruction | Shyam Narayanan, Michael Ren | 30m |
Problem: reconstruct a circular binary string from independent deletion-channel traces (deletions prob q). Main claims: worst-case reconstruction uses… | ||
| Self-testing of a single quantum device under computational assumptions | Tony Metger, Thomas Vidick | 23m |
Constructs a protocol that self-tests an EPR pair and the device’s measurements for a single monolithic quantum device under the computational assumption that… | ||
| Polynomial-time trace reconstruction in the low deletion rate regime | Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha | 23m |
Claim: a polynomial-time algorithm reconstructs any n-bit string with high probability using polynomially many traces when the deletion rate δ < n^{-1/3+ε}… | ||
| Metrical Service Systems with Transformations | Sebastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke | 24m |
Defines Metrical Server Systems with Transformations: each request is a map from domain AT to image BT and the algorithm pays only to move into AT. Shows any… | ||
| Tight Hardness Results for Training Depth-2 ReLU Networks | Daniel Reichman, Pasin Manurangsi, Subhi Goel, Adam R. Klivans | 32m |
Proves concrete limits and matching algorithms for depth-2 ReLU training: shows single-ReLU NP-hard (agnostic) and NP-hardness for any K≥2 in the realizable… | ||
| A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization | Pranjal Dutta, Nitin Saxena, Thomas Thierauf | 28m |
If an explicit univariate family has support sum ≥ D^{1/2+ε} then VP ≠ VNP; a constant ε yields an exponential separation. The proof uses depth reduction… | ||
| Circuit Depth Reductions | Alexander Golovnev, Alexander S. Kulikov, Ryan Williams | 34m |
Proves structural depth reductions: any size-S circuit is an OR of 2^{S/3} formulas (toy lemma) and the main result gives a depth-3 with top fan-in 2^{S/3.9}… | ||
| Dynamic inference in probabilistic graphical models | Weiming Feng, Kun He, Xiaoming Sun, Yitong Yin | 23m |
Presents an algorithm that updates samples and estimates after small edits to a graphical model with cost roughly proportional to the edit size rather than… | ||
| Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality | Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra | 35m |
Proves KKL, Friedgut and Talagrand without hypercontractivity by combining random restrictions with a version of the log-Sobolev inequality. Shows that… | ||
| On Rich 2-to-1 Games | Mark Braverman, Subhash Khot, Dor Minzer | 23m |
Defines an r-wise rich two-to-one label-cover variant where each left vertex induces a near-uniform distribution over 2-sized partitions of the left alphabet… | ||
| Distributed Quantum Proofs for Replicated Data | Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, ami Paz | 20m |
Claim: replicated-data consistency can be certified with log N qubits per certificate and per message, versus Θ(N) classically. Construction uses quantum… | ||
| On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions | Mikito Nanashima | 29m |
Shows that non-adaptive black-box reductions from NP-hard languages to an auxiliary-input pseudorandom generator would collapse the polynomial hierarchy, using… | ||
| Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits | Boaz Barak, Chi-Ning Chou, Xun Gao | 33m |
Claims a classical algorithm that uses light-cone marginals to sample from shallow random circuits, computes each marginal in poly(n)·2^L time where L is the… | ||
| On the complexity of isomorphism problems for tensors, groups, and polynomials I: Tensor Isomorphism | Joshua A. Grochow, Youming Qiao | 31m |
Proves that for any constant D≥3, D-tensor isomorphism reduces in polynomial time to 3-tensor isomorphism, so a large cluster of problems (cubic forms, algebra… | ||
| Bounds on the QAC0 Complexity of Approximating Parity | Gregory Rosenthal | 17m |
Constant-depth QAC0 circuits can approximate parity arbitrarily well but at steep cost: depth seven requires exponential size, and the paper gives a depth-11… | ||
| Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate | Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma | 21m |
Proves query lower bounds for local list decoding of very low‑rate binary codes and shows these bounds hold even for exponentially large lists. Main… | ||
| Is the space complexity of planted clique recovery the same as that of detection? | Jay Mardia | 25m |
Asks whether planted clique recovery can match detection in space and gives a near-complete constructive answer: a derandomized, combinatorial algorithm is… | ||
| Algorithms and Hardness for Multidimensional Range Updates and Queries | Joshua Lau, Angus Ritossa | 39m |
Shows that multidimensional range updates flatten via a kd-style reduction to 1D giving ~Õ(√p) per operation and proves matching conditional lower bounds (no… | ||
| Two combinatorial MA-complete problems | Dorit Aharonov, Alex B. Grilo | 28m |
Two new combinatorial problems are shown MA-complete: SetCSP is MA-hard for inverse-polynomial ε, and an implicit-graph problem ACAC is in MA via random-walk… | ||
| Delegated Stochastic Probing | Curtis Bechtel, Shaddin Dughmi | 25m |
Defines a game-theoretic model of delegated stochastic probing and gives an explicit single-proposal mechanism that is as powerful as general signaling… | ||
| Explicit SoS lower bounds from high-dimensional expanders | Irit Dveer Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani | 34m |
Constructs deterministic, polynomial-time Max-3-XOR instances from Ramanujan complexes whose true optimum is at most 1 − μ (μ a fixed constant, e.g. ~0.1) yet… | ||
| Sampling Arborescences in Parallel | Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild | 26m |
Claims an RNC sampler that outputs a rooted arborescence from a weighted digraph with probability proportional to product of edge weights, running in polylog… | ||
| Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum | Zachary Remscrim | 29m |
Proves concrete limits: gives a general lower bound on 2QCFA running time in terms of Dwork–Stockmeyer non-regularity D_L, shows palindrome needs exponential… | ||
| On the Complexity of #CSP^d | Jiabao Lin | 20m |
Proves a full dichotomy for Counting-CSP^d: for any finite function set F over a finite domain the partition function is computable in polynomial time exactly… | ||
| Interactive Proofs for Verifying Machine Learning | Jonathan Shafer, Guy N. Rothblum, Shafi Goldwasser, Amir Yehudayoff | 46m |
Defines PAC verification (verifier with sample access plus an interactive prover) and gives concrete separations: realizable thresholds admit order 1/ε… | ||
| Shrinkage under random projections, and cubic formula lower bounds in AC^0 | Yuval Filmus, Or Meir, Avishay Tal | 23m |
Proves an n^3 lower bound on De Morgan formula size for an explicit AC^0 function built by composing a small hard gadget F0 with a surjectivity block, using… | ||
| Ordered Graph Limits and Their Applications | Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Yuichi Yoshida | 28m |
The paper defines a new limit object called an orderon (a function on R^2→[0,1] mixing an order coordinate and a variability coordinate), introduces a… | ||
| Error Correcting Codes for Uncompressed Messages | Ofer Grossman, Justin Holmgren | 19m |
Defines codes for polynomial-time recognizable message sets S and proves for up to 3% adversarial errors an efficiently encodable/decodable randomized code… | ||
| Total Functions in the Polynomial Hierarchy | Daniel Mitropolsky, Christos Papadimitriou, Robert Kleinberg | 35m |
Defines a hierarchy TFΣi of total search classes and proves specific natural problems sit at low levels: the empty problem is in TFΣ2 via a union‑bound /… | ||
| Relaxing Common Belief for Social Networks | Noah Burrell, Grant Schoenebeck | 24m |
Paper defines common P_mu belief (a factional-belief relaxations of common belief) and proves it undergirds partial approximate coordination in threshold… | ||
| Tiered Random Matching Markets: Rank is Proportional to Popularity | Itai Ashlagi, Mark Braverman, Clayton Thomas, Geng Zhao | 21m |
Man-proposing deferred acceptance runs in Θ(n log n) proposals and yields average ranks that scale inversely with public scores: expected rank for an agent is… | ||
| Black-Box Uselessness: Composing Separations in Cryptography | Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody | 37m |
Defines a composable notion called black-box uselessness and proves that infinitely-often one-way functions are useless for building key agreement when one… | ||
| Pseudobinomiality of the Sticky Random Walk | Venkatesan Guruswami, Vinayak Kumar | 28m |
Defines a sticky random walk (first bit uniform, later bits stay with prob (1+λ)/2) and proves the Hamming-weight distribution differs from Bin(n,1/2) by total… | ||
| Robust Quantum Entanglement at (nearly) Room Temperature | Lior Eldar | 16m |
Constructs a family of local Hamiltonians whose thermal state remains hard to prepare: the Hamiltonian is topologically ordered and its thermal state has… | ||
| Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers | Abhijit Mudigonda, Ryan Williams | 34m |
Proves a concrete lower bound: there is a language in QCMA running in linear time on a QRAM that cannot be decided by small‑space random‑access machines in… | ||
| Online Search With a Hint | Spyros Angelopoulos | 22m |
Explores linear search with untrusted hints and gives concrete tradeoffs: exact-position hints admit a shrunk exponential strategy that is Pareto-optimal… | ||
| Non-quasi-linear Agents in Quasi-linear Mechanisms | Moshe Babaioff, Richard Cole, Jason Hartline, Nicole Immorlica, Brendan Lucier | 30m |
Mechanisms that are truthful for quasi-linear agents remain structured when agents have convex payment disutility: each best response is a uniform scaling best… | ||
| Sequential Defaulting in Financial Networks | Pál András Papp, Roger Wattenhofer | 25m |
Paper models discrete-time updates of announced recovery rates in networks with debts and CDSs and shows concrete, surprising behaviors: small examples produce… | ||
| No quantum speedup over gradient descent for non-smooth convex optimization | Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif | 24m |
Proves that quantum algorithms give no asymptotic advantage for non‑smooth 1‑Lipschitz convex optimization in high dimension by showing a matching 1/epsilon^2… | ||
| Quantum versus Randomized Communication Complexity, with Efficient Players | Uma Girish, Ran Raz, Avishay Tal | 21m |
Shows a concrete partial function (a XOR lift of Aaronson’s Fourrelation) that has an efficient small-cost quantum simultaneous protocol with a few EPR pairs… | ||
| Agnostic learning with unknown utilities | Kush Bhatia, Peter L. Bartlett, Anca Dragan, Jacob Steinhardt | 18m |
Framework studies agnostic supervised learning where the utility U is arbitrary and only the hypothesis class F is restricted, and it introduces a K-comparison… | ||
| On Distributed Differential Privacy and Counting Distinct Elements | Lijie Chen, Badih Ghazi, Ravi Kumar, Pasin Manurangsi | 27m |
Shows that distinct counting under constant-epsilon, delta = 1/poly(n) privacy is basically impossible in the local model: any local protocol needs error ≈ N /… | ||
| A Generalized Matching Reconfiguration Problem | Noam Solomon, Shay Solomon | 33m |
Shows a linear-time procedure that reconfigures any unweighted source matching into any target matching while keeping intermediate matchings within one of the… | ||
| Sensitivity Analysis of the Maximum Matching Problem | Yuichi Yoshida, Samson Zhou | 22m |
Gives a randomized algorithm that achieves a 1+ε approximation with O(1) worst-case edge sensitivity (uses randomized greedy + McGregor’s layered… | ||
| Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets | Vijay V. Vazirani, Mihalis Yannakakis | 32m |
Shows that computing exact HZ equilibria requires nonlinear fixed points by giving a unique irrational 4×4 instance (root of 17) and proves exact computation… | ||
| An O(n) time algorithm for finding Hamilton cycles with high probability | Rajko Nenadov, Angelika Steger, Pascal Su | 24m |
Claim: an algorithm finds a Hamilton cycle in G(n,p) with high probability in O(n) time under the model that neighbor queries return a uniform random neighbor… | ||
| Communication memento: Memoryless communication complexity | Srinivasan Arunachalam, Supartha Podder | 33m |
Defines memoryless communication complexity where messages are a rewritable register and cost is the largest message size, proves tight equivalences with… | ||
| Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration | Michael B. Cohen, Aaron Sidford, Kevin Tian | 30m |
Introduces a concrete condition called relative Lipschitzness between operator G and regularizer R and proves that standard extragradient (Mirror Prox)… | ||
| Training (Overparametrized) Neural Networks in Near-Linear Time | Binghui Peng, Zhao Song, Jan van den Brand, Omri Weinstein | 19m |
Proves that training two‑layer ReLU networks with width m and n samples runs in near‑linear time by replacing the costly J J^T computation (previously Ω(m… | ||
| A New Connection Between Node and Edge Depth Robust Graphs | Jeremiah Blocki, Mike Cinkoske | 23m |
Gives a concrete reduction that turns an E-edge-depth-robust DAG with m edges into an E/2 node-depth-robust DAG with O(m) nodes and constant indegree by… | ||
| Towards local testability for quantum coding | Anthony Leverrier, Vivien Londe, Gilles Zémor | 32m |
Construction produces an LDPC quantum code (hemi-cube) that encodes one logical qubit with minimum distance distance ~√n and local-testability/soundness… | ||
| Complete Problems for Multi-Pseudodeterministic Computations | Peter Dixon, A Pavan, N. V. Vinodchandran | 26m |
Establishes that collision probability estimation is complete for turning approximation and multi-valued search algorithms into pseudodeterministic ones: if… | ||
| Online Paging with a Vanishing Regret | Yuval Emek, Shay Kutten, Yangguang Shi | 30m |
Online paging with cache size K and universe N over T rounds becomes achievable with predictions: a simulation algorithm SIM algorithm replaces true… | ||
| Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility | José Correa, Paul Dütting, Felix Fischer, Kevin Schewior, Bruno Ziliotto | 34m |
Revisits the unknown-IID prophet problem and gives three concrete results: a class of MRS algorithms analyzed via variational calculus that raises the large-n… | ||
| Differentially Oblivious Turing Machines | Ilan Komargodski, Elaine Shi | 27m |
Claim: any multi-tape Turing machine admits a compiler to a Differentially Oblivious Turing Machine that hides any single differing step while incurring only… | ||
| Quantitative Correlation Inequalities via Semigroup Interpolation | Shivam Nadimpalli, Rocco A. Servedio, Anindya De | 32m |
Proves a quantitative Gaussian correlation bound: for symmetric convex sets K,L the correlation ≥ φ(Σ_i Inf_i(K)·Inf_i(L)) with Inf_i defined as the negated… | ||
| Shrinkage of Decision Lists and DNF Formulas | Benjamin Rossman | 22m |
Result gives a concrete shrinkage bound: the expected decision list size under a p‑random restriction is at most M^{α(p)} where α(p) is an explicit function of… | ||
| Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing | Kunal Mittal, Ran Raz | 24m |
Claims that a strong multiplayer parallel-repetition theorem (conjectured decay Val(G^n) ≤ 2^{-Ω(KN)} for the independent K-player function game) yields… | ||
| Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma | Stefan Dziembowski, Grzegorz Fabiański, Sebastian Faust, Siavash Riahi | 26m |
Paper proves there is no perfect Plasma: any off‑chain plasma protocol must either incur large exit sizes or allow non‑uniquely attributable mass exits. Under… | ||
| Majorizing Measures for the Optimizer | Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha | 33m |
Proves a constructive version of the majorizing measures duality: a convex program for the Gaussian chaining functional and a simplified dual are within a… | ||
| Randomness and Fairness in Two-Sided Matching with Limited Interviews | Hedyeh Beyhaghi, Eva Tardos | 20m |
Model has N applicants and N positions, each side draws iid uniform preferences, applicants send K applications, positions interview K' and then… | ||
| Counterexamples to the Low-Degree Conjecture | Justin Holmgren, Alexander S Wein | 19m |
Refutes Hopkins’ low-degree conjecture by building distributions where degree-O(log n) polynomials provably fail to distinguish IID Gaussian Q from structured… | ||
| High-entropy dual functions and locally decodable codes | Farrokh Labib, Jop Briet | 34m |
Shows a negative result: for infinitely many primes P there exists a K(P) and explicit families of order-k dual functions over F_p^n that cannot be… | ||
| Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions | Nicole Immorlica, Ian Kash, Brendan Lucier | 30m |
Model where a one-dimensional hidden state follows a drifting Gaussian state and noisy samples cost a per-sample fee plus optional fixed setup cost… | ||
| Batching and Optimal Multi-stage Bipartite Allocations | Yiding Feng, Rad Niazadeh | 24m |
A polynomial-time algorithm achieves the optimal competitive ratio for K-stage bipartite allocation, namely gamma_K = 1 - (1-1/K)^K (tending to 1-1/e), and a… | ||
| Learning and Strongly Truthful Multi-task Setting Peer Prediction: A Variational Approach | Grant Schoenebeck, Fang-Yi Yu | 27m |
Defines a variational estimator of phi‑mutual information and uses it to build a multi‑task peer‑prediction payment: learn an ideal scoring rule K on withheld… | ||
| Distributed load balancing: a new framework and improved guarantees | Allen Liu, Sara Ahmadian, Binghui Peng, Morteza Zadimoghaddam | 19m |
Distributed algorithm balances loads on a bipartite source–worker graph in the CONGEST model, producing a 1+ε approximation for general convex objectives by… | ||
| Erasure-Resilient Sublinear-Time Graph Algorithms | Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma | 25m |
Defines queries on an alpha-erased graph (adjacency lists with adversarial missing entries) and measures performance over all completions; degree and neighbor… | ||
| How to Sell Information Optimally: an Algorithmic Study | Yang Cai, Grigoris Velegkas | 22m |
Provides an algorithmic characterization: when type distribution and payoff matrix are explicit the revenue-optimal menu is computable via a polynomial-size… | ||
| Computation Over the Noisy Broadcast Channel with Malicious Parties | Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena | 27m |
Shows a protocol that computes bit‑exchange over a noisy broadcast channel tolerating up to half malicious parties while cutting per‑player communication from… | ||
| nothing matches | ||