Cover Image

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bangachev, Kiril, Bresler, Guy, Tiegel, Stefan, Vaikuntanathan, Vinod
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Cryptography and Security Discrete Mathematics Statistics Theory
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
by: Bangachev, Kiril, et al.
Published: (2024)

Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration
by: Bangachev, Kiril, et al.
Published: (2024)

Average-Case Reductions for $k$-XOR and Tensor PCA
by: Bresler, Guy, et al.
Published: (2026)

Graph Quasirandomness for Hypothesis Testing of Stochastic Block Models
by: Bangachev, Kiril, et al.
Published: (2025)

Symmetric Perceptrons, Number Partitioning and Lattices
by: Vafa, Neekon, et al.
Published: (2025)

On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors
by: Gadouleau, Maximilien, et al.
Published: (2024)

When does a bent concatenation not belong to the completed Maiorana-McFarland class?
by: Kudin, Sadmir, et al.
Published: (2024)

Millions of inequivalent quadratic APN functions in eight variables
by: Beierle, Christof, et al.
Published: (2025)

Security issues of CFS-like digital signature algorithms
by: D'Alconzo, Giuseppe, et al.
Published: (2021)

Demystifying the RSA Algorithm: An Intuitive Introduction for Novices in Cybersecurity
by: Luo, Zhengping Jay, et al.
Published: (2023)

The Beginner's Textbook for Fully Homomorphic Encryption
by: Ko, Ronny
Published: (2025)

Nearly-Linear Time Seeded Extractors with Short Seeds
by: Doron, Dean, et al.
Published: (2024)

Optimal Inapproximability of Promise Equations over Finite Groups
by: Butti, Silvia, et al.
Published: (2024)

Structural Properties of Non-Linear Cellular Automata: Permutivity, Surjectivity and Reversibility
by: Ramdhane, Firas Ben, et al.
Published: (2025)

On the matching arrangement of a graph, improper weight function problem and its application
by: Bolotnikov, Aleksey, et al.
Published: (2024)

Oblivious Defense in ML Models: Backdoor Removal without Detection
by: Goldwasser, Shafi, et al.
Published: (2024)

Polynomial Complexity of Inversion of sequences and Local Inversion of Maps
by: Sule, Virendra
Published: (2024)

New classes of reversible cellular automata
by: Haugland, Jan Kristian, et al.
Published: (2024)

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
by: Chakrabarty, Deeparnab, et al.
Published: (2025)

Spanning-tree-packing protocol for conference key propagation in quantum networks
by: Trushechkin, Anton, et al.
Published: (2025)

On completely factoring any integer efficiently in a single run of an order finding algorithm
by: Ekerå, Martin
Published: (2020)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

Double Spending Analysis of Nakamoto Consensus for Time-Varying Mining Rates with Ruin Theory
by: Doger, Mustafa, et al.
Published: (2024)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
by: Bresler, Guy, et al.
Published: (2025)

Exact Thresholds for Noisy Non-Adaptive Group Testing
by: Chen, Junren, et al.
Published: (2024)

PoW Security-Latency under Random Delays and the Effect of Transaction Fees
by: Doger, Mustafa, et al.
Published: (2024)

Transaction Capacity, Security and Latency in Blockchains
by: Doger, Mustafa, et al.
Published: (2024)

Refined Bitcoin Security-Latency Under Network Delay
by: Doger, Mustafa, et al.
Published: (2022)

The Identity Problem in the special affine group of $\mathbb{Z}^2$
by: Dong, Ruiwen
Published: (2023)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
by: Bhandari, Siddharth, et al.
Published: (2021)

Ordering groups and the Identity Problem
by: Bodart, Corentin, et al.
Published: (2024)

The Rate-Immediacy Barrier in Explicit Tree Code Constructions
by: Cohen, Gil, et al.
Published: (2025)

Optimal, Qubit-Efficient Quantum Vehicle Routing via Colored-Permutations
by: Onah, Chinonso, et al.
Published: (2026)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
by: Buhai, Rares-Darius, et al.
Published: (2024)

Combinatorial Designs and Cellular Automata: A Survey
by: Manzoni, Luca, et al.
Published: (2025)

Uniformity Testing under User-Level Local Privacy
by: Canonne, Clément L., et al.
Published: (2025)

Locally Private Histograms in All Privacy Regimes
by: Canonne, Clément L., et al.
Published: (2024)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

An Incentive-Compatible Semi-Parallel Proof-of-Work Protocol
by: Doger, Mustafa, et al.
Published: (2025)