Cover Image

Noisy Computing of the Threshold Function

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Wang, Ziao, Ghaddar, Nadim, Zhu, Banghua, Wang, Lele
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

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation
by: Wang, Ziao, et al.
Published: (2023)

On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
by: Wang, Ziao, et al.
Published: (2022)

Noisy Sorting Capacity
by: Wang, Ziao, et al.
Published: (2022)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
by: Chen, Wenjing, et al.
Published: (2023)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

Real Time Proportional Throughput Maximization: How much advance notice should you give your scheduler?
by: Mottu, Nadim A.
Published: (2025)

Testably Learning Polynomial Threshold Functions
by: Slot, Lucas, et al.
Published: (2024)

Online Edge Coloring: Sharp Thresholds
by: Blikstad, Joakim, et al.
Published: (2025)

Improved Algorithms for Clustering with Noisy Distance Oracles
by: Pradhan, Pinki, et al.
Published: (2026)

Noisy (Binary) Searching: Simple, Fast and Correct
by: Dereniowski, Dariusz, et al.
Published: (2021)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

Faster MAX-CUT on Bounded Threshold Rank Graphs
by: Anderson, Prashanti, et al.
Published: (2025)

Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
by: Dürr, Christoph, et al.
Published: (2024)

Improving the Threshold for Finding Rank-1 Matrices in a Subspace
by: Dastidar, Jeshu, et al.
Published: (2025)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
by: Kanellopoulos, Sotiris, et al.
Published: (2026)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

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

Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata
by: Nakar, Yonatan, et al.
Published: (2025)

The Competitive Ratio of Threshold Policies for Online Unit-density Knapsack Problems
by: Ma, Will, et al.
Published: (2019)

Rapid Mixing at the Uniqueness Threshold
by: Chen, Xiaoyu, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Publishing Below-Threshold Triangle Counts under Local Weight Differential Privacy
by: Pfisterer, Kevin, et al.
Published: (2026)

Efficient Algorithms for Personalized PageRank Computation: A Survey
by: Yang, Mingji, et al.
Published: (2024)

Threshold Rules for the Classical Prophet Inequality
by: Zhang, Jiechen
Published: (2026)

Improved Algorithms for Effective Resistance Computation on Graphs
by: Yang, Yichun, et al.
Published: (2025)

Revisiting Local Computation of PageRank: Simple and Optimal
by: Wang, Hanzhi, et al.
Published: (2024)

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
by: Munch, Elizabeth, et al.
Published: (2025)

Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
by: Zeng, Shiwei, et al.
Published: (2023)

On Circular Threshold Words and Other Stronger Versions of Dejean's conjecture
by: Tunev, Igor N.
Published: (2025)

Frequency Moments in Noisy Streaming and Distributed Data under Mismatch Ambiguity
by: Liu, Kaiwen, et al.
Published: (2026)

Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach
by: Li, Cheng, et al.
Published: (2025)

DNA Probe Computing System for Solving NP-Complete Problems
by: Xu, Jin, et al.
Published: (2025)

Hedgegraph Polymatroids
by: Chandrasekaran, Karthekeyan, et al.
Published: (2025)

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

Query-Efficient Correlation Clustering with Noisy Oracle
by: Kuroki, Yuko, et al.
Published: (2024)

Computing Flows in Subquadratic Space
by: Brand, Jan van den, et al.
Published: (2026)

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

Online Computation with Untrusted Advice
by: Angelopoulos, Spyros, et al.
Published: (2019)

Property Testing of Computational Networks
by: Czumaj, Artur, et al.
Published: (2025)

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
by: Dhulipala, Laxman, et al.
Published: (2025)