Cover Image

Spectral Refutations of Semirandom $k$-LIN over Larger Fields

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kocurek, Nicholas, Manohar, Peter
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Semirandom Planted Clique and the Restricted Isometry Property
by: Błasiok, Jarosław, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

Semirandom Planted Clique via 1-norm Isometry Property
by: Guruswami, Venkatesan, et al.
Published: (2025)

On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models
by: Bhaskara, Aditya, et al.
Published: (2024)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
by: Kocurek, Nicholas, et al.
Published: (2026)

Solving Random Planted CSPs below the $n^{k/2}$ Threshold
by: Basu, Arpon, et al.
Published: (2025)

A Dynamic Programming Approach to Evader Pathfinding in Static Pursuit Scenarios
by: Samanta, Sukanya, et al.
Published: (2025)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2025)

Sampling and Identity-Testing Without Approximate Tensorization of Entropy
by: Gay, William, et al.
Published: (2025)

Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
by: Jo, Seungbum, et al.
Published: (2022)

Engineering Minimal k-Perfect Hash Functions
by: Hermann, Stefan, et al.
Published: (2025)

Maintaining $k$-MinHash Signatures over Fully-Dynamic Data Streams with Recovery
by: Clementi, Andrea, et al.
Published: (2024)

On $k$-connectivity oracles in $k$-connected graphs
by: Nutov, Zeev
Published: (2026)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Time-Optimal $k$-Server
by: Frei, Fabian, et al.
Published: (2025)

Computing k-mers in Graphs
by: Alanko, Jarno N., et al.
Published: (2025)

Structural Parameterizations of $k$-Planarity
by: Gima, Tatsuya, et al.
Published: (2025)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

On Parallel $k$-Center Clustering
by: Coy, Sam, et al.
Published: (2023)

On Constrained and k Shortest Paths
by: Bendahi, Abderrahim, et al.
Published: (2024)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
by: Nutov, Zeev
Published: (2022)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev, et al.
Published: (2025)

Optimal $k$-Secretary with Logarithmic Memory
by: Qiao, Mingda, et al.
Published: (2025)

Fully Dynamic Euclidean k-Means
by: Bhattacharya, Sayan, et al.
Published: (2025)

The $k$-Fold Matroid Secretary Problem
by: Gujjar, Rishi, et al.
Published: (2025)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Fault-tolerant $k$-Supplier with Outliers
by: Chakrabarty, Deeparnab, et al.
Published: (2023)

Local Search k-means++ with Foresight
by: Conrads, Theo, et al.
Published: (2024)

Insights into $(k,ρ)$-shortcutting algorithms
by: Leonhardt, Alexander, et al.
Published: (2024)

Dynamic k-center clustering with lifetimes
by: Moretti, Simone, et al.
Published: (2026)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
by: Nederlof, Jesper
Published: (2025)

Spectral Clustering with Side Information
by: Fichtenberger, Hendrik, et al.
Published: (2025)

On the Efficient Discovery of Maximum $k$-Defective Biclique
by: Cui, Donghang, et al.
Published: (2025)

Improved bicriteria approximation for $k$-edge-connectivity
by: Nutov, Zeev
Published: (2025)

The k-Center Problem of Uncertain Points on Graphs
by: Xu, Haitao, et al.
Published: (2025)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)