Search results for "halfspaces"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
157	Adam R. Klivans, Alexander A. Sherstov	Unconditional lower bounds for learning intersections of halfspaces.	Mach. Learn.	2007	DBLP DOI BibTeX RDF	Intersections of halfspaces, Halfspace learning, SQ learning, Lower bounds for learning, Harmonic sieve, PAC learning, Query learning, Statistical queries, Polynomial threshold functions
146	Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio	Testing halfspaces.	SODA	2009	DBLP DOI BibTeX RDF
130	Adam R. Klivans, Alexander A. Sherstov	Improved Lower Bounds for Learning Intersections of Halfspaces.	COLT	2006	DBLP DOI BibTeX RDF
99	Nader H. Bshouty, Ehab Wattad	On Exact Learning Halfspaces with Random Consistent Hypothesis Oracle.	ALT	2006	DBLP DOI BibTeX RDF
99	Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio	Learning Intersections and Thresholds of Halfspaces.	FOCS	2002	DBLP DOI BibTeX RDF
95	Prahladh Harsha, Adam R. Klivans, Raghu Meka	An invariance principle for polytopes.	STOC	2010	DBLP DOI BibTeX RDF	average sensitivity, invariance principles, polytopes, pseudorandom generators, contingency tables, noise sensitivity, limit theorems, agnostic learning
89	Raghu Meka, David Zuckerman	Pseudorandom generators for polynomial threshold functions.	STOC	2010	DBLP DOI BibTeX RDF	invariance principles, polynomials, pseudorandom generators, branching programs, threshold functions, halfspaces
83	Adam R. Klivans, Alexander A. Sherstov	Cryptographic Hardness for Learning Intersections of Halfspaces.	FOCS	2006	DBLP DOI BibTeX RDF
78	Subhash Khot, Rishi Saket	On hardness of learning intersection of two halfspaces.	STOC	2008	DBLP DOI BibTeX RDF	learning, approximation, hardness, halfspaces
67	Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami	New Results for Learning Noisy Parities and Halfspaces.	FOCS	2006	DBLP DOI BibTeX RDF
67	Venkatesan Guruswami, Prasad Raghavendra	Hardness of Learning Halfspaces with Noise.	FOCS	2006	DBLP DOI BibTeX RDF
63	Ryan O'Donnell, Rocco A. Servedio	The chow parameters problem.	STOC	2008	DBLP DOI BibTeX RDF	chow parameters, boolean function, fourier analysis, threshold function
52	Adam R. Klivans, Philip M. Long, Alex K. Tang	Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
52	Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio	Agnostically Learning Halfspaces.	FOCS	2005	DBLP DOI BibTeX RDF
52	Adam R. Klivans, Rocco A. Servedio	Learning Intersections of Halfspaces with a Margin.	COLT	2004	DBLP DOI BibTeX RDF
47	Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi	Learnability and Automatizability.	FOCS	2004	DBLP DOI BibTeX RDF
47	Klaus-Uwe Höffgen, Hans Ulrich Simon	Robust Trainability of Single Neurons.	COLT	1992	DBLP DOI BibTeX RDF
46	Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola	Bounded Independence Fools Halfspaces.	FOCS	2009	DBLP DOI BibTeX RDF	k-wise independent distributions, pseudorandomness, halfspaces
46	Alexander A. Sherstov	The Intersection of Two Halfspaces Has High Threshold Degree.	FOCS	2009	DBLP DOI BibTeX RDF	intersections of halfspaces, polynomial representations of Boolean functions, PAC learning, rational approximation, direct product theorems
46	Avrim Blum, Ravi Kannan	Learning an Intersection of k Halfspaces over a Uniform Distribution	FOCS	1993	DBLP DOI BibTeX RDF	geometric learning, k halfspaces, bounding hyperplanes, polynomial-time algorithm, intersection, uniform distribution
42	Boris Aronov, Sariel Har-Peled, Micha Sharir	On approximate halfspace range counting and relative epsilon-approximations.	SCG	2007	DBLP DOI BibTeX RDF	approximate range queries, epsilon-approximations, partition trees, range spaces, queries, discrepancy, range, VC-dimension, halfspaces
36	Adam R. Klivans, Philip M. Long, Rocco A. Servedio	Learning Halfspaces with Malicious Noise.	ICALP (1)	2009	DBLP DOI BibTeX RDF
36	Adam Tauman Kalai	Learning Nested Halfspaces and Uphill Decision Trees.	COLT	2007	DBLP DOI BibTeX RDF
36	Ryan C. Harkins, John M. Hitchcock	Dimension, Halfspaces, and the Density of Hard Sets.	COCOON	2007	DBLP DOI BibTeX RDF
36	Tatsuya Akutsu, Sascha Ott	Inferring a Union of Halfspaces from Examples.	COCOON	2002	DBLP DOI BibTeX RDF
36	Jirí Matousek 0001, Raimund Seidel, Emo Welzl	How to Net a Lot with Little: Small epsilon-Nets for Disks and Halfspaces.	SCG	1990	DBLP DOI BibTeX RDF
32	Timothy M. Chan	On the bichromatic k-set problem.	SODA	2008	DBLP BibTeX RDF
32	Alexander A. Sherstov	Halfspace Matrices.	CCC	2007	DBLP DOI BibTeX RDF
32	Haim Kaplan, Micha Sharir	Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting.	SODA	2006	DBLP DOI BibTeX RDF
32	Haim Kaplan, Micha Sharir, Elad Verbin	Colored intersection searching via sparse rectangular matrix multiplication.	SCG	2006	DBLP DOI BibTeX RDF	colored intersection searching, generalized intersection searching, matrix multiplication, range searching
32	Yulai Xie, Jack Snoeyink, Jinhui Xu 0001	Efficient algorithm for approximating maximum inscribed sphere in high dimensional polytope.	SCG	2006	DBLP DOI BibTeX RDF	chebyshev center, maximum inscribed sphere, approximation, polytope, core-set
32	Abdullah Bade, Norhaida Mohd. Suaib, Abdullah Mohd Zin, Tengku M. T. Sembok	Oriented convex polyhedra for collision detection in 3D computer animation.	GRAPHITE	2006	DBLP DOI BibTeX RDF	virtual environments, collision detection, bounding volumes
32	Suzanne F. Buchele, Richard H. Crawford	Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations.	Symposium on Solid Modeling and Applications	2003	DBLP DOI BibTeX RDF	product and assembly modeling, representation conversion, reverse engineering, geometric and topological representations
32	Nader H. Bshouty, Lynn Burroughs	Maximizing Agreements and CoAgnostic Learning.	ALT	2002	DBLP DOI BibTeX RDF
32	Takeshi Tokuyama	Efficient Algorithms for the Minimum Diameter Bridge Problem.	JCDCG	2000	DBLP DOI BibTeX RDF
32	Tibor Hegedüs	Geometrical Concept Learning and Convex Polytopes.	COLT	1994	DBLP DOI BibTeX RDF
26	Nader H. Bshouty, Zhixiang Chen 0001, Steven Homer	On Learning Discretized Geometric Concepts (Extended Abstract)	FOCS	1994	DBLP DOI BibTeX RDF	finite injury priority method, online learning algorithm, geometric concept, discretized geometric concepts, classes of rectangles, polynomial time, PAC-learning, equivalence queries, halfspaces
20	Jinyan Su, Jinhui Xu, Di Wang 0015	PAC learning halfspaces in non-interactive local differential privacy model with public unlabeled data.	J. Comput. Syst. Sci.	2024	DBLP DOI BibTeX RDF
20	Stefan Tiegel	Improved Hardness Results for Learning Intersections of Halfspaces.	CoRR	2024	DBLP DOI BibTeX RDF
20	Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, Felix Zhou 0002	Replicable Learning of Large-Margin Halfspaces.	CoRR	2024	DBLP DOI BibTeX RDF
20	Yinan Li, Chicheng Zhang	Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach.	AISTATS	2024	DBLP BibTeX RDF
20	Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan	Tester-Learners for Halfspaces: Universal Algorithms.	CoRR	2023	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis	Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise.	CoRR	2023	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Sihan Liu, Nikos Zarifis	Efficient Testable Learning of Halfspaces with Adversarial Label Noise.	CoRR	2023	DBLP DOI BibTeX RDF
20	Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan	An Efficient Tester-Learner for Halfspaces.	CoRR	2023	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren	Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.	CoRR	2023	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis	Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise.	CoRR	2023	DBLP DOI BibTeX RDF
20	Yinan Li, Chicheng Zhang	Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach.	CoRR	2023	DBLP DOI BibTeX RDF
20	Anindya De, Shivam Nadimpalli, Rocco A. Servedio	Gaussian Approximation of Convex Sets by Intersections of Halfspaces.	CoRR	2023	DBLP DOI BibTeX RDF
20	Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan	Tester-Learners for Halfspaces: Universal Algorithms.	NeurIPS	2023	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel Kane 0001, Vasilis Kontonis, Sihan Liu, Nikos Zarifis	Efficient Testable Learning of Halfspaces with Adversarial Label Noise.	NeurIPS	2023	DBLP BibTeX RDF
20	Ilias Diakonikolas, Jelena Diakonikolas, Daniel Kane 0001, Puqian Wang, Nikos Zarifis	Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise.	NeurIPS	2023	DBLP BibTeX RDF
20	Stefan Tiegel	Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems.	COLT	2023	DBLP BibTeX RDF
20	Ilias Diakonikolas, Jelena Diakonikolas, Daniel M. Kane, Puqian Wang, Nikos Zarifis	Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise.	COLT	2023	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel Kane 0001, Lisheng Ren	Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals.	ICML	2023	DBLP BibTeX RDF
20	Lies Hadjadj, Massih-Reza Amini, Sana Louhichi	Generalization Guarantees of Self-Training of Halfspaces under Label Noise Corruption.	IJCAI	2023	DBLP DOI BibTeX RDF
20	Jie Shen	PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time.	AISTATS	2023	DBLP BibTeX RDF
20	Ziwei Ji, Kwangjun Ahn, Pranjal Awasthi, Satyen Kale, Stefani Karp	Agnostic Learnability of Halfspaces via Logistic Loss.	CoRR	2022	DBLP BibTeX RDF
20	Stefan Tiegel	Hardness of Agnostically Learning Halfspaces from Worst-Case Lattice Problems.	CoRR	2022	DBLP DOI BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, Lisheng Ren	Cryptographic Hardness of Learning Halfspaces with Massart Noise.	CoRR	2022	DBLP DOI BibTeX RDF
20	Jinyan Su, Jinhui Xu 0001, Di Wang 0015	On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data.	CoRR	2022	DBLP DOI BibTeX RDF
20	Daniel Hsu 0001, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis	Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals.	CoRR	2022	DBLP BibTeX RDF
20	Rajai Nasser, Stefan Tiegel	Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise.	CoRR	2022	DBLP BibTeX RDF
20	Xi Chen, Shyamal Patel	Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning.	SODA	2022	DBLP DOI BibTeX RDF
20	Jinyan Su, Jinhui Xu 0001, Di Wang 0015	On PAC Learning Halfspaces in Non-interactive Local Privacy Model with Public Unlabeled Data.	ACML	2022	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel Kane 0001, Pasin Manurangsi, Lisheng Ren	Cryptographic Hardness of Learning Halfspaces with Massart Noise.	NeurIPS	2022	DBLP BibTeX RDF
20	Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis	Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals.	COLT	2022	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel Kane 0001	Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise.	COLT	2022	DBLP BibTeX RDF
20	Rajai Nasser, Stefan Tiegel	Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise.	COLT	2022	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Learning general halfspaces with general Massart noise under the Gaussian distribution.	STOC	2022	DBLP DOI BibTeX RDF
20	Ziwei Ji, Kwangjun Ahn, Pranjal Awasthi, Satyen Kale, Stefani Karp	Agnostic Learnability of Halfspaces via Logistic Loss.	ICML	2022	DBLP BibTeX RDF
20	Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent.	ICML	2022	DBLP BibTeX RDF
20	Difan Zou, Spencer Frei, Quanquan Gu	Provable Robustness of Adversarial Training for Learning Halfspaces with Noise.	CoRR	2021	DBLP BibTeX RDF
20	Lies Hadjadj, Massih-Reza Amini, Sana Louhichi, Alexis Deschamps	Self-Training of Halfspaces with Generalization Guarantees under Massart Mislabeling Noise Model.	CoRR	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Christos Tzamos	Forster Decomposition and Learning Halfspaces with Noise.	CoRR	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Agnostic Proper Learning of Halfspaces under Gaussian Marginals.	CoRR	2021	DBLP BibTeX RDF
20	Chicheng Zhang, Yinan Li	Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise.	CoRR	2021	DBLP BibTeX RDF
20	Jie Shen 0005	Sample-Optimal PAC Learning of Halfspaces with Malicious Noise.	CoRR	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Threshold Phenomena in Learning Halfspaces with Massart Noise.	CoRR	2021	DBLP BibTeX RDF
20	Ning Ding 0001, Dawu Gu	New cryptographic hardness for learning intersections of halfspaces over boolean cubes with membership queries.	Inf. Comput.	2021	DBLP DOI BibTeX RDF
20	Xingyi Du, Qingnan Zhou, Nathan Carr 0001, Tao Ju	Boundary-sampled halfspaces: a new representation for constructive solid modeling.	ACM Trans. Graph.	2021	DBLP DOI BibTeX RDF
20	Jie Shen 0005, Chicheng Zhang	Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance.	ALT	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel Kane 0001, Christos Tzamos	Forster Decomposition and Learning Halfspaces with Noise.	NeurIPS	2021	DBLP BibTeX RDF
20	Maximilian Thiessen, Thomas Gärtner 0001	Active Learning of Convex Halfspaces on Graphs.	NeurIPS	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Agnostic Proper Learning of Halfspaces under Gaussian Marginals.	COLT	2021	DBLP BibTeX RDF
20	Mark Braverman, Gillat Kol, Shay Moran, Raghuvansh R. Saxena	Near Optimal Distributed Learning of Halfspaces with Two Parties.	COLT	2021	DBLP BibTeX RDF
20	Chicheng Zhang, Yinan Li	Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov Noise.	COLT	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Efficiently learning halfspaces with Tsybakov noise.	STOC	2021	DBLP DOI BibTeX RDF
20	Suprovat Ghoshal, Rishi Saket	Hardness of learning DNFs using halfspaces.	STOC	2021	DBLP DOI BibTeX RDF
20	Difan Zou, Spencer Frei, Quanquan Gu	Provable Robustness of Adversarial Training for Learning Halfspaces with Noise.	ICML	2021	DBLP BibTeX RDF
20	Spencer Frei, Yuan Cao 0006, Quanquan Gu	Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins.	ICML	2021	DBLP BibTeX RDF
20	Jie Shen 0005	Sample-Optimal PAC Learning of Halfspaces with Malicious Noise.	ICML	2021	DBLP BibTeX RDF
20	Jie Shen 0005	On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise.	ICML	2021	DBLP BibTeX RDF
20	Badih Ghazi, Ravi Kumar 0001, Pasin Manurangsi, Thao Nguyen	Robust and Private Learning of Halfspaces.	AISTATS	2021	DBLP BibTeX RDF
20	Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Learning Halfspaces with Massart Noise Under Structured Distributions.	CoRR	2020	DBLP BibTeX RDF
20	Max Hopkins, Daniel M. Kane, Shachar Lovett, Gaurav Mahajan	Point Location and Active Learning: Learning Halfspaces Almost Optimally.	CoRR	2020	DBLP BibTeX RDF
20	Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	Learning Halfspaces with Tsybakov Noise.	CoRR	2020	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi	The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise.	CoRR	2020	DBLP BibTeX RDF
20	Jie Shen 0005	On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise.	CoRR	2020	DBLP BibTeX RDF
20	Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, Nikos Zarifis	A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise.	CoRR	2020	DBLP BibTeX RDF