Cover Image

New Algorithms and Lower Bounds for Streaming Tournaments

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ghosh, Prantar, Kuchlous, Sahil
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
by: Ghosh, Prantar, et al.
Published: (2024)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
by: Funke, Daniel, et al.
Published: (2024)

Lower Bounds for Non-adaptive Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
by: Kumar, Mithilesh, et al.
Published: (2024)

An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling
by: Zhao, Jingyang, et al.
Published: (2025)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
by: Cervenjak, Philip, et al.
Published: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

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

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
by: Gupta, Sushmita, et al.
Published: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
by: Atalig, Sunny, et al.
Published: (2024)

Adaptive BSTs for Single-Source and All-to-All Requests: Algorithms and Lower Bounds
by: Shiran, Maryam
Published: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

Lower Bounds for the Algorithmic Complexity of Learned Indexes
by: Croquevielle, Luis Alberto, et al.
Published: (2026)

Dynamic Parameterized Feedback Problems in Tournaments
by: Zych-Pawlewicz, Anna, et al.
Published: (2024)

The APX-hardness of the Traveling Tournament Problem
by: Zhao, Jingyang, et al.
Published: (2023)

The SpaceSaving$\pm$ Family of Algorithms for Data Streams with Bounded Deletions
by: Zhao, Fuheng, et al.
Published: (2023)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
by: Yoshida, Yuichi
Published: (2026)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

New Algorithms for Parity-SAT and Its Bounded-Occurrence Versions
by: Jain, Sanjay, et al.
Published: (2026)

Lower Bounds on $0$-Extension with Steiner Nodes
by: Chen, Yu, et al.
Published: (2024)

Double Exponential Lower Bound for Telephone Broadcast
by: Tale, Prafullkumar
Published: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
by: Doron-Arad, Ilan, et al.
Published: (2024)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
by: Chen, Yu, et al.
Published: (2026)

Streaming Algorithms for Connectivity Augmentation
by: Jin, Ce, et al.
Published: (2024)

Streaming Algorithms for Network Design
by: Chekuri, Chandra, et al.
Published: (2025)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Improved Lower Bounds for Privacy under Continual Release
by: Aryanfard, Bardiya, et al.
Published: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
by: Fleming, Noah, et al.
Published: (2026)