Cover Image

Experimental Design Using Interlacing Polynomials

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lau, Lap Chi, Wang, Robert, Zhou, Hong
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Machine Learning Computation
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Sparsification by Deterministic Discrepancy Walk
by: Lau, Lap Chi, et al.
Published: (2024)

A Combinatorial Characterization of Constant Mixing Time
by: Lau, Lap Chi, et al.
Published: (2025)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
by: Lau, Lap Chi, et al.
Published: (2024)

Outlier Robust Multivariate Polynomial Regression
by: Arora, Vipul, et al.
Published: (2024)

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

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation
by: Greenhut, Daniel, et al.
Published: (2025)

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
by: McMahan, Jeremy
Published: (2024)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
by: Pham, Ninh, et al.
Published: (2025)

Polynomial-time derivation of optimal k-tree topology from Markov networks
by: Dastjerdi, Fereshteh R., et al.
Published: (2024)

Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
by: Alman, Josh, et al.
Published: (2025)

A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
by: Chandrasekaran, Gautam, et al.
Published: (2025)

Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
by: Diakonikolas, Ilias, et al.
Published: (2024)

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

Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
by: Lee, Jane H., et al.
Published: (2024)

Faster Graph Embeddings via Coarsening
by: Fahrbach, Matthew, et al.
Published: (2020)

Learning Linear Attention in Polynomial Time
by: Yau, Morris, et al.
Published: (2024)

Approximation Algorithms for D-optimal Design
by: Singh, Mohit, et al.
Published: (2018)

Robust Sparse Regression with Non-Isotropic Designs
by: Liu, Chih-Hung, et al.
Published: (2024)

Prediction-Specific Design of Learning-Augmented Algorithms
by: Li, Sizhe, et al.
Published: (2025)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
by: Gaspers, Serge, et al.
Published: (2025)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
by: Luo, Yuetian, et al.
Published: (2023)

GPU Memory Usage Optimization for Backward Propagation in Deep Network Training
by: Hong, Ding-Yong, et al.
Published: (2025)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Polynomial-Time Approximability of Constrained Reinforcement Learning
by: McMahan, Jeremy
Published: (2025)

Learning-Augmented Hierarchical Clustering
by: Braverman, Vladimir, et al.
Published: (2025)

Efficient Algorithms for Verifying Kruskal Rank in Sparse Linear Regression and Related Applications
by: Zhou, Fengqin
Published: (2025)

Exact Learning of Weighted Graphs Using Composite Queries
by: Goodrich, Michael T., et al.
Published: (2025)

Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
by: Jiang, Minhui, et al.
Published: (2024)

Testing Calibration in Nearly-Linear Time
by: Hu, Lunjia, et al.
Published: (2024)

Fast and explainable clustering based on sorting
by: Chen, Xinye, et al.
Published: (2022)

Fast and Accurate Triangle Counting in Graph Streams Using Predictions
by: Boldrin, Cristian, et al.
Published: (2024)

Fair Submodular Cover
by: Chen, Wenjing, et al.
Published: (2024)

Online Learning with Limited Information in the Sliding Window Model
by: Braverman, Vladimir, et al.
Published: (2026)

Learning-Augmented Moment Estimation on Time-Decay Models
by: Nagawanshi, Soham, et al.
Published: (2026)

Learned LSM-trees: Two Approaches Using Learned Bloom Filters
by: Fidalgo, Nicholas, et al.
Published: (2025)

Agnostic Learning of General ReLU Activation Using Gradient Descent
by: Awasthi, Pranjal, et al.
Published: (2022)

ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
by: Hertrich, Christoph, et al.
Published: (2021)

A Competitive Algorithm for Agnostic Active Learning
by: Price, Eric, et al.
Published: (2023)