Cover Image

Online Orthogonal Vectors Revisited

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gajulapalli, Karthik, Golovnev, Alexander, King, Samuel, Saraogi, Sidhant
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Output-Sparse Matrix Multiplication Using Compressed Sensing
by: Bennett, Huck, et al.
Published: (2025)

Matrix Multiplication Verification Using Coding Theory
by: Bennett, Huck, et al.
Published: (2023)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
by: Alman, Josh, et al.
Published: (2025)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

The Planted Orthogonal Vectors Problem
by: Kühnemann, David, et al.
Published: (2025)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Faster Convolutions: Yates and Strassen Revisited
by: Brand, Cornelius, et al.
Published: (2025)

Parameterized Critical Node Cut Revisited
by: Knop, Dušan, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Structural Parameterizations for Two Bounded Degree Problems Revisited
by: Lampis, Michael, et al.
Published: (2023)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

On the Space Complexity of Online Convolution
by: Andersson, Joel Daniel, et al.
Published: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Asymmetric Number Partitioning with Splitting and Interval Targets
by: Bismuth, Samuel, et al.
Published: (2022)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
by: Firbas, Alexander, et al.
Published: (2024)

Vector TSP: A Traveling Salesperson Problem with Racetrack-like Acceleration Constraints
by: Casteigts, Arnaud, et al.
Published: (2020)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
by: Kumar, Rajendra, et al.
Published: (2018)

Random tensor isomorphism under orthogonal and unitary actions
by: Chizewer, Jeremy, et al.
Published: (2026)

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
by: Aggarwal, Divesh, et al.
Published: (2025)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

First Order Logic on Pathwidth Revisited Again
by: Lampis, Michael
Published: (2022)

Distance Vector Domination
by: Cordasco, Gennaro, et al.
Published: (2024)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
by: Guruswami, Venkatesan, et al.
Published: (2024)

Neighborhood-Aware Graph Labeling Problem
by: Shahverdikondori, Mohammad, et al.
Published: (2026)