On the public citation graph
Improved Bounds on the Sample Complexity of Learning
0 signed · 154 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/(sici)1098-2418(199809)13:2<99::aid-rsa1>3.0.co;2-mopenalex-snapshot
Balls and bins: A study in negative dependence
inferredcites →https://doi.org/10.1006/inco.1994.1097openalex-snapshot
Predicting {0, 1}-Functions on Randomly Drawn Points
inferredcites →https://doi.org/10.1007/978-1-4612-0865-5_26openalex-snapshot
Probability Inequalities for sums of Bounded Random Variables
inferredcites →https://doi.org/10.1007/978-1-4612-5254-2openalex-snapshot
Convergence of Stochastic Processes
inferredcites →https://doi.org/10.1007/978-3-319-21852-6_3openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1016/0097-3165(95)90052-7openalex-snapshot
Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
inferredcites →https://doi.org/10.1016/0890-5401(92)90010-dopenalex-snapshot
Decision theoretic generalizations of the PAC model for neural net and other learning applications
inferredcites →https://doi.org/10.1080/01621459.1963.10500830openalex-snapshot
Probability Inequalities for Sums of Bounded Random Variables
inferredcites →https://doi.org/10.1093/biomet/55.2.422openalex-snapshot
An Inequality Involving Multinomial Probabilities
inferredcites →https://doi.org/10.1137/1116025openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1145/279943.279968openalex-snapshot
The complexity of learning according to two models of a drifting environment
inferredcites →https://doi.org/10.1214/aop/1176988847openalex-snapshot
Sharper Bounds for Gaussian and Empirical Processes
inferredcites →https://doi.org/10.5555/93335.93339openalex-snapshot
Inductive principles of the search for empirical dependences (methods based on weak convergence of probability measures)
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/3-540-44634-6_4openalex-snapshot
Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming
inferred← citeshttps://doi.org/10.1007/978-3-030-29349-9_2openalex-snapshot
Core-Sets: Updated Survey
inferred← citeshttps://doi.org/10.1007/978-3-030-59267-7_25openalex-snapshot
On Coresets for Support Vector Machines
inferred← citeshttps://doi.org/10.1007/978-3-031-20624-5_20openalex-snapshot
Estimating the Clustering Coefficient Using Sample Complexity Analysis
inferred← citeshttps://doi.org/10.1007/978-3-031-70341-6_8openalex-snapshot
MANTRA: Temporal Betweenness Centrality Approximation Through Sampling
inferred← citeshttps://doi.org/10.1007/978-3-319-24486-0_15openalex-snapshot
Subsampling in Smoothed Range Spaces
inferred← citeshttps://doi.org/10.1007/978-3-642-04128-0_29openalex-snapshot
Shape Fitting on Point Sets with Probability Distributions
inferred← citeshttps://doi.org/10.1007/978-3-642-22300-6_45openalex-snapshot
Geometric Computations on Indecisive Points
inferred← citeshttps://doi.org/10.1007/978-3-642-23783-6_42openalex-snapshot
The VC-Dimension of SQL Queries and Selectivity Estimation through Sampling
inferred← citeshttps://doi.org/10.1007/978-3-642-32512-0_42openalex-snapshot
An Explicit VC-Theorem for Low-Degree Polynomials
inferred← citeshttps://doi.org/10.1007/s00454-007-1328-5openalex-snapshot
Finding a Guard that Sees Most and a Shop that Sells Most
inferred← citeshttps://doi.org/10.1007/s00454-010-9248-1openalex-snapshot
Relative (p,ε)-Approximations in Geometry
inferred← citeshttps://doi.org/10.1007/s00454-010-9308-6openalex-snapshot
Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting
inferred← citeshttps://doi.org/10.1007/s00454-016-9824-0openalex-snapshot
Two Proofs for Shallow Packings
inferred← citeshttps://doi.org/10.1007/s00454-019-00075-0openalex-snapshot
Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning
inferred← citeshttps://doi.org/10.1007/s00454-019-00134-6openalex-snapshot
Near-Optimal Coresets of Kernel Density Estimates
inferred← citeshttps://doi.org/10.1007/s00454-020-00243-7openalex-snapshot
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications
inferred← citeshttps://doi.org/10.1007/s00454-021-00318-zopenalex-snapshot
The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
inferred← citeshttps://doi.org/10.1007/s00454-022-00376-xopenalex-snapshot
The $\epsilon$-$t$-Net Problem
inferred← citeshttps://doi.org/10.1007/s10115-019-01393-8openalex-snapshot
ProSecCo: progressive sequence mining with convergence guarantees
inferred← citeshttps://doi.org/10.1007/s10115-022-01689-2openalex-snapshot
gRosSo: mining statistically robust patterns from a sequence of datasets
inferred← citeshttps://doi.org/10.1007/s10489-016-0872-1openalex-snapshot
Link prediction based on sampling in complex networks
inferred← citeshttps://doi.org/10.1007/s10618-015-0423-0openalex-snapshot
Fast approximation of betweenness centrality through sampling
inferred← citeshttps://doi.org/10.1007/s10851-013-0431-xopenalex-snapshot
Learning Big (Image) Data via Coresets for Dictionaries
inferred← citeshttps://doi.org/10.1016/j.comgeo.2013.01.002openalex-snapshot
Shape matching under rigid motion
inferred← citeshttps://doi.org/10.1016/j.comnet.2008.04.021openalex-snapshot
Processing top-k queries from samples
inferred← citeshttps://doi.org/10.1016/j.ins.2016.09.029openalex-snapshot
Sampling-based algorithm for link prediction in temporal networks
inferred← citeshttps://doi.org/10.1016/j.ipl.2022.106250openalex-snapshot
Optimal approximations made easy
inferred← citeshttps://doi.org/10.1016/j.knosys.2022.108820openalex-snapshot
Random walk-based algorithm for distance-aware influence maximization on multiple query locations
inferred← citeshttps://doi.org/10.1051/ps:2005018openalex-snapshot
Theory of Classification: a Survey of Some Recent Advances
inferred← citeshttps://doi.org/10.1109/focs.2012.31openalex-snapshot
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
inferred← citeshttps://doi.org/10.1109/focs.2014.69openalex-snapshot
The Communication Complexity of Distributed epsilon-Approximations
inferred← citeshttps://doi.org/10.1109/focs.2018.00082openalex-snapshot
Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics
inferred← citeshttps://doi.org/10.1109/focs.2019.00051openalex-snapshot
Multi-resolution Hashing for Fast Pairwise Summations
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00118openalex-snapshot
Revisiting Agnostic PAC Learning
inferred← citeshttps://doi.org/10.1109/icde51399.2021.00141openalex-snapshot
Approximating Multidimensional Range Counts with Maximum Error Guarantees
inferred← citeshttps://doi.org/10.1109/icde55515.2023.00141openalex-snapshot
Finding Best Tuple via Error-prone User Interaction
inferred← citeshttps://doi.org/10.1109/icdm.2018.00057openalex-snapshot
ProSecCo: Progressive Sequence Mining with Convergence Guarantees
inferred← citeshttps://doi.org/10.1109/icdm50108.2020.00064openalex-snapshot
gRosSo: Mining Statistically Robust Patterns from a Sequence of Datasets
inferred← citeshttps://doi.org/10.1109/imcom53663.2022.9721770openalex-snapshot
Alpha Lightweight Coreset for k-Means Clustering
inferred← citeshttps://doi.org/10.1109/infcom.2011.5935005openalex-snapshot
Optimal sampling algorithms for frequency estimation in distributed data
inferred← citeshttps://doi.org/10.1109/ita.2016.7888187openalex-snapshot
Sample compression schemes for VC classes
inferred← citeshttps://doi.org/10.1109/tit.2002.806131openalex-snapshot
Extension of the PAC framework to finite and countable Markov chains
inferred← citeshttps://doi.org/10.1109/tpami.2024.3416710openalex-snapshot
Sequential Manipulation Against Rank Aggregation: Theory and Algorithm
inferred← citeshttps://doi.org/10.1109/tpami.2024.3476683openalex-snapshot
Pixel is All You Need: Adversarial Spatio-Temporal Ensemble Active Learning for Salient Object Detection
inferred← citeshttps://doi.org/10.1109/tpds.2022.3144595openalex-snapshot
Communication-efficient k-Means for Edge-based Machine Learning
inferred← citeshttps://doi.org/10.1137/080736600openalex-snapshot
Approximate Halfspace Range Counting
inferred← citeshttps://doi.org/10.1137/090765092openalex-snapshot
Semialgebraic Range Reporting and Emptiness Searching with Applications
inferred← citeshttps://doi.org/10.1137/1.9781611973099.5openalex-snapshot
On Multiplicative λ-Approximations and Some Geometric Applications
inferred← citeshttps://doi.org/10.1137/1.9781611973105.103openalex-snapshot
Turning Big data into tiny data: Constant-size coresets for k -means, PCA and projective clustering
inferred← citeshttps://doi.org/10.1137/100801809openalex-snapshot
On Multiplicative $\lambda$-Approximations and Some Geometric Applications
inferred← citeshttps://doi.org/10.1137/120888909openalex-snapshot
Submodular Functions: Learnability, Structure, and Optimization
inferred← citeshttps://doi.org/10.1137/130916448openalex-snapshot
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
inferred← citeshttps://doi.org/10.1137/140977746openalex-snapshot
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
inferred← citeshttps://doi.org/10.1137/16m1093604openalex-snapshot
The Communication Complexity of Distributed epsilon-Approximations
inferred← citeshttps://doi.org/10.1137/18m1209854openalex-snapshot
Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering
inferred← citeshttps://doi.org/10.1137/25m1799684openalex-snapshot
Turning Big Data Into Tiny Data: Coresets for Unsupervised Learning Problems
inferred← citeshttps://doi.org/10.1145/1247069.1247128openalex-snapshot
On approximate halfspace range counting and relative epsilon-approximations
inferred← citeshttps://doi.org/10.1145/1368436.1368446openalex-snapshot
Processing top k queries from samples
inferred← citeshttps://doi.org/10.1145/1542362.1542421openalex-snapshot
On the set multi-cover problem in geometric settings
inferred← citeshttps://doi.org/10.1145/1993636.1993712openalex-snapshot
A unified framework for approximating and clustering data
inferred← citeshttps://doi.org/10.1145/1998196.1998204openalex-snapshot
Comparing distributions and shapes using the kernel distance
inferred← citeshttps://doi.org/10.1145/2213556.2213588openalex-snapshot
Nearest-neighbor searching under uncertainty
inferred← citeshttps://doi.org/10.1145/2390176.2390185openalex-snapshot
On the set multicover problem in geometric settings
inferred← citeshttps://doi.org/10.1145/2462356.2462363openalex-snapshot
Small-size relative ( p ,ε)-approximations for well-behaved range spaces
inferred← citeshttps://doi.org/10.1145/2462356.2462388openalex-snapshot
Range counting coresets for uncertain data
inferred← citeshttps://doi.org/10.1145/2463664.2465219openalex-snapshot
Nearest neighbor searching under uncertainty II
inferred← citeshttps://doi.org/10.1145/2556195.2556224openalex-snapshot
Fast approximation of betweenness centrality through sampling
inferred← citeshttps://doi.org/10.1145/2582112.2582155openalex-snapshot
The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
inferred← citeshttps://doi.org/10.1145/2629586openalex-snapshot
Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees
inferred← citeshttps://doi.org/10.1145/2700222openalex-snapshot
The Discrete and Semicontinuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection
inferred← citeshttps://doi.org/10.1145/2890490openalex-snapshot
Sample Compression Schemes for VC Classes
inferred← citeshttps://doi.org/10.1145/2902251.2902303openalex-snapshot
Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures
inferred← citeshttps://doi.org/10.1145/2955098openalex-snapshot
Nearest-Neighbor Searching Under Uncertainty II
inferred← citeshttps://doi.org/10.1145/2996913.2996939openalex-snapshot
Scalable spatial scan statistics through sampling
inferred← citeshttps://doi.org/10.1145/3034786.3056110openalex-snapshot
Output-optimal Parallel Algorithms for Similarity Joins
inferred← citeshttps://doi.org/10.1145/3097983.3098000openalex-snapshot
Coresets for Kernel Regression
inferred← citeshttps://doi.org/10.1145/3219819.3219973openalex-snapshot
Scalable k -Means Clustering via Lightweight Coresets
inferred← citeshttps://doi.org/10.1145/3311967openalex-snapshot
Output-Optimal Massively Parallel Algorithms for Similarity Joins
inferred← citeshttps://doi.org/10.1145/3375395.3387643openalex-snapshot
The Adversarial Robustness of Sampling
inferred← citeshttps://doi.org/10.1145/3394486.3403235openalex-snapshot
Estimating the Percolation Centrality of Large Networks through Pseudo-dimension Theory
inferred← citeshttps://doi.org/10.1145/3406325.3451022openalex-snapshot
A new coreset framework for clustering
inferred← citeshttps://doi.org/10.1145/3431285openalex-snapshot
Journey to the Center of the Point Set
inferred← citeshttps://doi.org/10.1145/3442590openalex-snapshot
TipTap: Approximate Mining of Frequent k -Subgraph Patterns in Evolving Graphs
inferred← citeshttps://doi.org/10.1145/3448016.3452802openalex-snapshot
At-the-time and Back-in-time Persistent Sketches
inferred← citeshttps://doi.org/10.1145/3580305.3599325openalex-snapshot
Efficient Centrality Maximization with Rademacher Averages
inferred← citeshttps://doi.org/10.1145/3587254openalex-snapshot
MaNIACS : Approximate Mining of Frequent Subgraph Patterns through Sampling
inferred← citeshttps://doi.org/10.1145/3628601openalex-snapshot
SILVAN : Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds
inferred← citeshttps://doi.org/10.1145/3736252.3742585openalex-snapshot
The Pseudo-Dimension of Contracts
inferred← citeshttps://doi.org/10.1186/s40537-024-00940-7openalex-snapshot
On data efficiency of univariate time series anomaly detection models
inferred← citeshttps://doi.org/10.1214/ecp.v7-1047openalex-snapshot
Some Extensions of an Inequality of Vapnik and Chervonenkis
inferred← citeshttps://doi.org/10.1287/moor.2023.1351openalex-snapshot
Bilateral Trade: A Regret Minimization Perspective
inferred← citeshttps://doi.org/10.14778/3675034.3675055openalex-snapshot
Efficient Discovery of Significant Patterns with Few-Shot Resampling
inferred← citeshttps://doi.org/10.1613/jair.1.12397openalex-snapshot
Safe Multi-Agent Pathfinding with Time Uncertainty
inferred← citeshttps://doi.org/10.17169/refubium-28335openalex-snapshot
Dynamic Planar Voronoi Diagrams for General Distance Functions and Their Algorithmic Applications
inferred← citeshttps://doi.org/10.17877/de290r-43openalex-snapshot
Coresets and streaming algorithms for the k-means problem and related clustering objectives
inferred← citeshttps://doi.org/10.20382/jocg.v10i1a8openalex-snapshot
Covering many points with a small-area box
inferred← citeshttps://doi.org/10.3390/a13050123openalex-snapshot
Mining Sequential Patterns with VC-Dimension and Rademacher Complexity
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2014.34openalex-snapshot
The Cover Number of a Matrix and its Algorithmic Applications
inferred← citeshttps://doi.org/10.4230/lipics.approx-random.2019.62openalex-snapshot
New Frameworks for Offline and Streaming Coreset Constructions
inferred← citeshttps://doi.org/10.4230/lipics.esa.2019.40openalex-snapshot
Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction
inferred← citeshttps://doi.org/10.4230/lipics.esa.2019.76openalex-snapshot
Geometric Crossing-Minimization - A Scalable Randomized Approach
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2022.51openalex-snapshot
Introduction to Core-sets: an Updated Survey
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2020.78openalex-snapshot
Epsilon-approximations and epsilon-nets
inferred← citeshttps://doi.org/10.4230/lipics.socg.2021.12openalex-snapshot
On Undecided LP, Clustering and Active Learning
inferred← citeshttps://doi.org/10.46298/dmtcs.6631openalex-snapshot
On the VC-dimension of half-spaces with respect to convex sets
inferred← citeshttps://doi.org/10.46298/theoretics.24.2openalex-snapshot
Realizable Learning is All You Need
inferred← citeshttps://doi.org/10.48550/arxiv.0908.3716openalex-snapshot
Carnival of Samplings: Nets, Approximations, Relative and Sensitive
inferred← citeshttps://doi.org/10.48550/arxiv.1101.5805openalex-snapshot
The VC-Dimension of Queries and Selectivity Estimation Through Sampling
inferred← citeshttps://doi.org/10.48550/arxiv.1110.2136openalex-snapshot
Active Learning Using Smooth Relative Regret Approximations with Applications
inferred← citeshttps://doi.org/10.48550/arxiv.1111.2942openalex-snapshot
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
inferred← citeshttps://doi.org/10.48550/arxiv.1111.6937openalex-snapshot
Efficient Discovery of Association Rules and Frequent Itemsets through Sampling with Tight Performance Guarantees
inferred← citeshttps://doi.org/10.48550/arxiv.1310.5245openalex-snapshot
The Discrete and Semi-continuous Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection Techniques
inferred← citeshttps://doi.org/10.48550/arxiv.1312.6305openalex-snapshot
Output-Sensitive Tools for Range Searching in Higher Dimensions
inferred← citeshttps://doi.org/10.48550/arxiv.1412.3922openalex-snapshot
Size sensitive packing number for Hamming cube and its consequences
inferred← citeshttps://doi.org/10.48550/arxiv.1412.5215openalex-snapshot
Shallow Packings in Geometry
inferred← citeshttps://doi.org/10.48550/arxiv.1503.06960openalex-snapshot
Sample compression schemes for VC classes
inferred← citeshttps://doi.org/10.48550/arxiv.1804.02530openalex-snapshot
$\varepsilon$-Coresets for Clustering (with Outliers) in Doubling Metrics
inferred← citeshttps://doi.org/10.48550/arxiv.1901.08219openalex-snapshot
Greedy Strategy Works for $k$-Center Clustering with Outliers and Coreset Construction
inferred← citeshttps://doi.org/10.48550/arxiv.2002.11904openalex-snapshot
Layered Sampling for Robust Optimization Problems
inferred← citeshttps://doi.org/10.48550/arxiv.2006.07757openalex-snapshot
Defending SVMs against Poisoning Attacks: the Hardness and DBSCAN Approach
inferred← citeshttps://doi.org/10.48550/arxiv.2109.12974openalex-snapshot
Bilateral Trade: A Regret Minimization Perspective
inferred← citeshttps://doi.org/10.48550/arxiv.2111.00062openalex-snapshot
Improving Generalization Bounds for VC Classes Using the Hypergeometric Tail Inversion
inferred← citeshttps://doi.org/10.48550/arxiv.2301.09627openalex-snapshot
The Impossibility of Parallelizing Boosting
inferred← citeshttps://doi.org/10.48550/arxiv.math/0405342openalex-snapshot
Some extensions of an inequality of Vapnik and Chervonenkis
inferred← citeshttps://doi.org/10.5555/2095116.2095121openalex-snapshot
On multiplicative λ-approximations and some geometric applications
inferred← citeshttps://doi.org/10.5555/982792.982954openalex-snapshot
On finding a guard that sees most and a shop that sells most
inferred← citeshttps://doi.org/10.70675/05aecbe5zbaa6z4121z9719z797e66b4802aopenalex-snapshot
Approximation Algorithms and Sketches for Clustering
inferred← citeshttps://doi.org/10.70675/32098958z1deez4f21zb51az429b616621fdopenalex-snapshot
Efficient and privacy-preserving compressive learning
inferred← citeshttps://doi.org/10.70675/b49810c9z66a7z4dc3zaeddz8dc7fffaf3adopenalex-snapshot
Efficient Approximations of High-Dimensional Data
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.