Interactive Clustering of Linear Classes and Cryptographic Lower Bounds

DOI10.1007/978-3-319-24486-0_11zbMath1471.68219OpenAlexW2259817753MaRDI QIDQ2835625

Ádám D. Lelkes, Lev Reyzin

Publication date: 30 November 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-24486-0_11

zbMATH Keywords

parity functionquery learningcryptographic lower boundsinteractive clustering

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Prediction-preserving reducibility
• A constant-factor approximation algorithm for the \(k\)-median problem
• Pseudorandom Functions and Lattices
• Which Clustering Do You Want? Inducing Your Ideal Clustering with Minimal Feedback
• Number-theoretic constructions of efficient pseudo-random functions
• Clustering with Interactive Feedback
• Linear-time approximation schemes for clustering problems in any dimensions
• A new greedy approach for facility location problems
• Approximation schemes for clustering problems
• A theory of the learnable
• Greedy Strikes Back: Improved Facility Location Algorithms
• Cryptographic limitations on learning Boolean formulae and finite automata
• Local Search Heuristics for k-Median and Facility Location Problems
• Approximating min-sum k -clustering in metric spaces
• Spectral Clustering by Recursive Partitioning

This page was built for publication: Interactive Clustering of Linear Classes and Cryptographic Lower Bounds