Interactive clustering of linear classes and cryptographic lower bounds

DOI10.1007/978-3-319-24486-0_11MaRDI QIDQ2835625zbMATH OpenOpenAlexFDO

Authors Á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

cryptographic lower boundsinteractive clusteringparity functionquery learning

Mathematics Subject Classification ID

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

Recommendations

• Clustering with Interactive Feedback
• New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
• Cryptographic hardness for learning intersections of halfspaces
• scientific article; zbMATH DE number 1301787
• scientific article; zbMATH DE number 1024063

Cites work

• A constant-factor approximation algorithm for the k-median problem
• A new greedy approach for facility location problems
• A theory of the learnable
• Approximating min-sum k -clustering in metric spaces
• Approximation schemes for clustering problems
• Clustering with Interactive Feedback
• Cryptographic limitations on learning Boolean formulae and finite automata
• Greedy Strikes Back: Improved Facility Location Algorithms
• scientific article; zbMATH DE number 1775394 (Why is no real title available?)
• scientific article; zbMATH DE number 5485581 (Why is no real title available?)
• Linear-time approximation schemes for clustering problems in any dimensions
• Local Search Heuristics for k-Median and Facility Location Problems
• Number-theoretic constructions of efficient pseudo-random functions
• Prediction-preserving reducibility
• Pseudorandom functions and lattices
• Spectral Clustering by Recursive Partitioning
• Which clustering do you want? inducing your ideal clustering with minimal feedback

Cited in

(3)

• Clustering and Categorization Applied to Cryptanalysis
• Clustering with Interactive Feedback
• Local algorithms for interactive clustering

This page was built for publication: Interactive clustering of linear classes and cryptographic lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835625)