On the public citation graph

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

https://doi.org/10.1145/2728167
0 signed · 96 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1993.1057openalex-snapshot
Point Location in Arrangements of Hyperplanes
inferredcites →https://doi.org/10.1006/jcom.1997.0438openalex-snapshot
Rectangular Matrix Multiplication Revisited
inferredcites →https://doi.org/10.1007/11538462_32openalex-snapshot
The Parity Problem in the Presence of Noise, Decoding Random Linear Codes, and the Subset Sum Problem
inferredcites →https://doi.org/10.1007/3-540-45682-1_4openalex-snapshot
Secure Human Identification Protocols
inferredcites →https://doi.org/10.1007/978-3-642-22006-7_34openalex-snapshot
New Algorithms for Learning in Presence of Errors
inferredcites →https://doi.org/10.1007/978-3-642-24412-4_32openalex-snapshot
On Noise-Tolerant Learning of Sparse Parities and Related Problems
inferredcites →https://doi.org/10.1016/j.jcss.2004.04.002openalex-snapshot
Learning functions of k relevant variables
inferredcites →https://doi.org/10.1017/cbo9781107325982.004openalex-snapshot
Orthogonal Polynomials
inferredcites →https://doi.org/10.1038/ng1537openalex-snapshot
Genome-wide strategies for detecting multiple loci that influence complex diseases
inferredcites →https://doi.org/10.1093/bioinformatics/btq486openalex-snapshot
Detecting two-locus associations allowing for interactions in genome-wide association studies
inferredcites →https://doi.org/10.1109/ccc.2010.26openalex-snapshot
The Learning with Errors Problem (Invited Survey)
inferredcites →https://doi.org/10.1109/focs.2006.49openalex-snapshot
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
inferredcites →https://doi.org/10.1109/focs.2006.51openalex-snapshot
New Results for Learning Noisy Parities and Halfspaces
inferredcites →https://doi.org/10.1109/focs.2011.12openalex-snapshot
Efficient Fully Homomorphic Encryption from (Standard) LWE
inferredcites →https://doi.org/10.1109/focs.2012.27openalex-snapshot
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas
inferredcites →https://doi.org/10.1109/sfcs.1989.63486openalex-snapshot
How to recycle random bits
inferredcites →https://doi.org/10.1109/tit.2010.2050814openalex-snapshot
Bucketing Coding and Information Theory for the Statistical High-Dimensional Nearest-Neighbor Problem
inferredcites →https://doi.org/10.1137/0217052openalex-snapshot
A Randomized Algorithm for Closest-Point Queries
inferredcites →https://doi.org/10.1137/070684914openalex-snapshot
On Agnostic Learning of Parities, Monomials, and Halfspaces
inferredcites →https://doi.org/10.1137/s0097539798347177openalex-snapshot
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
inferredcites →https://doi.org/10.1145/1007352.1007371openalex-snapshot
Approximating the cut-norm via Grothendieck's inequality
inferredcites →https://doi.org/10.1145/1137856.1137881openalex-snapshot
Lower bounds on locality sensitive hashing
inferredcites →https://doi.org/10.1145/1327452.1327494openalex-snapshot
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
inferredcites →https://doi.org/10.1145/1536414.1536461openalex-snapshot
Public-key cryptosystems from the worst-case shortest vector problem
inferredcites →https://doi.org/10.1145/1568318.1568324openalex-snapshot
On lattices, learning with errors, random linear codes, and cryptography
inferredcites →https://doi.org/10.1145/195058.195147openalex-snapshot
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
inferredcites →https://doi.org/10.1145/2090236.2090271openalex-snapshot
Compressed matrix multiplication
inferredcites →https://doi.org/10.1145/2213977.2214056openalex-snapshot
Multiplying matrices faster than coppersmith-winograd
inferredcites →https://doi.org/10.1145/276698.276876openalex-snapshot
Approximate nearest neighbors
inferredcites →https://doi.org/10.1145/293347.293351openalex-snapshot
Efficient noise-tolerant learning from statistical queries
inferredcites →https://doi.org/10.1145/361002.361007openalex-snapshot
Multidimensional binary search trees used for associative searching
inferredcites →https://doi.org/10.1145/380752.380857openalex-snapshot
A sieve algorithm for the shortest lattice vector problem
inferredcites →https://doi.org/10.1145/509907.509965openalex-snapshot
Similarity estimation techniques from rounding algorithms
inferredcites →https://doi.org/10.1145/792538.792543openalex-snapshot
Noise-tolerant learning, the parity problem, and the statistical query model
inferredcites →https://doi.org/10.1145/997817.997857openalex-snapshot
Locality-sensitive hashing scheme based on p-stable distributions
inferredcites →https://doi.org/10.1184/r1/6608117openalex-snapshot
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
inferredcites →https://doi.org/10.1215/s0012-7094-42-00908-6openalex-snapshot
Positive definite functions on spheres
inferredcites →https://doi.org/10.2307/2005983openalex-snapshot
The Chebyshev Polynomials
inferredcites →https://doi.org/10.4086/toc.2012.v008a014openalex-snapshot
inferredcites →https://doi.org/10.4230/dagsemproc.08491.4openalex-snapshot
Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
inferredcites →https://doi.org/10.48550/arxiv.cs/0510088openalex-snapshot
Lower bounds on Locality Sensitive Hashing
inferredcites →https://doi.org/10.5555/1109557.1109688openalex-snapshot
Entropy based nearest neighbor search in high dimensions
inferredcites →https://doi.org/10.5555/92571.92659openalex-snapshot
Learning DNF under the uniform distribution in quasi-polynomial time
inferredcites →https://doi.org/10.5555/93335.93363openalex-snapshot
The light bulb problem

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-17659-4_24openalex-snapshot
Multi-target Attacks on the Picnic Signature Scheme and Related Protocols
inferred← citeshttps://doi.org/10.1007/978-3-319-90530-3_27openalex-snapshot
A New Algorithm for Finding Closest Pair of Vectors (Extended Abstract)
inferred← citeshttps://doi.org/10.1007/s00453-019-00664-8openalex-snapshot
High-Dimensional Approximate r-Nets
inferred← citeshttps://doi.org/10.1007/s00453-020-00727-1openalex-snapshot
Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
inferred← citeshttps://doi.org/10.1007/s00493-019-4113-1openalex-snapshot
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
inferred← citeshttps://doi.org/10.1007/s10559-018-0016-1openalex-snapshot
Index Structures for Fast Similarity Search for Real-Valued Vectors. I
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.04.026openalex-snapshot
An improved algorithm for learning sparse parities in the presence of noise
inferred← citeshttps://doi.org/10.1093/imaiai/iaw004openalex-snapshot
Detecting the large entries of a sparse covariance matrix in sub-quadratic time
inferred← citeshttps://doi.org/10.1109/bigmm.2017.76openalex-snapshot
Trend and Value Based Time Series Representation for Similarity Search
inferred← citeshttps://doi.org/10.1109/focs.2016.57openalex-snapshot
Polynomial Representations of Threshold Functions and Algorithmic Applications
inferred← citeshttps://doi.org/10.1109/focs.2017.12openalex-snapshot
Distributed PCP Theorems for Hardness of Approximation in P
inferred← citeshttps://doi.org/10.1109/focs.2017.39openalex-snapshot
Learning Graphical Models Using Multiplicative Weights
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00093openalex-snapshot
Properly learning decision trees in almost polynomial time
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00107openalex-snapshot
A strong composition theorem for junta complexity and the boosting of property testers
inferred← citeshttps://doi.org/10.1109/focs57990.2023.00108openalex-snapshot
New Lower Bounds for Adaptive Tolerant Junta Testing
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00114openalex-snapshot
Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
inferred← citeshttps://doi.org/10.1137/1.9781611974782.3openalex-snapshot
A Framework for Similarity Search with Space-Time Tradeoffs using Locality-Sensitive Filtering
inferred← citeshttps://doi.org/10.1137/1.9781611974782.4openalex-snapshot
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
inferred← citeshttps://doi.org/10.1137/1.9781611975031.138openalex-snapshot
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism
inferred← citeshttps://doi.org/10.1137/1.9781611975994.39openalex-snapshot
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
inferred← citeshttps://doi.org/10.1142/9789813272880_0182openalex-snapshot
APPROXIMATE NEAREST NEIGHBOR SEARCH IN HIGH DIMENSIONS
inferred← citeshttps://doi.org/10.1145/2902251.2902285openalex-snapshot
On the Complexity of Inner Product Similarity Join
inferred← citeshttps://doi.org/10.1145/3174804openalex-snapshot
A Faster Subquadratic Algorithm for Finding Outlier Correlations
inferred← citeshttps://doi.org/10.1145/3188745.3188916openalex-snapshot
Hardness of approximate nearest neighbor search
inferred← citeshttps://doi.org/10.1145/3196959.3196976openalex-snapshot
Distance-Sensitive Hashing
inferred← citeshttps://doi.org/10.1145/3196959.3196985openalex-snapshot
Set Similarity Search for Skewed Data
inferred← citeshttps://doi.org/10.1145/3374857.3374870openalex-snapshot
SETH vs Approximation
inferred← citeshttps://doi.org/10.1145/3448016.3457327openalex-snapshot
Active Sampling Count Sketch (ASCS) for Online Sparse Estimation of a Trillion Scale Covariance Matrix
inferred← citeshttps://doi.org/10.1145/3561047openalex-snapshot
Properly Learning Decision Trees in almost Polynomial Time
inferred← citeshttps://doi.org/10.1145/3717823.3718231openalex-snapshot
Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
inferred← citeshttps://doi.org/10.1145/3717823.3718300openalex-snapshot
A Framework for Building Data Structures from Communication Protocols
inferred← citeshttps://doi.org/10.3390/e23010079openalex-snapshot
Discovering Higher-Order Interactions Through Neural Information Decomposition
inferred← citeshttps://doi.org/10.4086/toc.2020.v016a004openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2018.14openalex-snapshot
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2021.29openalex-snapshot
Counting Short Vector Pairs by Inner Product and Relations to the Permanent
inferred← citeshttps://doi.org/10.4230/lipics.icdt.2018.13openalex-snapshot
Fast Sketch-based Recovery of Correlation Outliers
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2019.17openalex-snapshot
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
inferred← citeshttps://doi.org/10.4230/lipics.itcs.2020.84openalex-snapshot
Finding Skewed Subcubes Under a Distribution
inferred← citeshttps://doi.org/10.48550/arxiv.1605.02701openalex-snapshot
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
inferred← citeshttps://doi.org/10.48550/arxiv.1607.04755openalex-snapshot
High-dimensional approximate $r$-nets
inferred← citeshttps://doi.org/10.48550/arxiv.1612.07405openalex-snapshot
Practical linear-space Approximate Near Neighbors in high dimension
inferred← citeshttps://doi.org/10.48550/arxiv.1703.07867openalex-snapshot
Distance-Sensitive hashing
inferred← citeshttps://doi.org/10.48550/arxiv.1803.01420openalex-snapshot
Detecting Correlations with Little Memory and Communication
inferred← citeshttps://doi.org/10.48550/arxiv.1810.06740openalex-snapshot
An Illuminating Algorithm for the Light Bulb Problem
inferred← citeshttps://doi.org/10.48550/arxiv.1903.06412openalex-snapshot
A Faster Algorithm Enumerating Relevant Features over Finite Fields
inferred← citeshttps://doi.org/10.48550/arxiv.1906.09430openalex-snapshot
Algorithms for Similarity Search and Pseudorandomness
inferred← citeshttps://doi.org/10.48550/arxiv.1909.01821openalex-snapshot
Almost Optimal Tensor Sketch
inferred← citeshttps://doi.org/10.48550/arxiv.2004.00557openalex-snapshot
Statistical Queries and Statistical Algorithms: Foundations and Applications
inferred← citeshttps://doi.org/10.48550/arxiv.2011.06135openalex-snapshot
Hardness of Approximate Nearest Neighbor Search under L-infinity
inferred← citeshttps://doi.org/10.48550/arxiv.2103.15261openalex-snapshot
One Network Fits All? Modular versus Monolithic Task Formulations in Neural Networks
inferred← citeshttps://doi.org/10.5555/3039686.3039691openalex-snapshot
LSH forest: practical algorithms made theoretical
inferred← citeshttps://doi.org/10.5555/3381089.3381098openalex-snapshot
Oblivious Sketching of High-Degree Polynomial Kernels.
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.