Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions (English)
- New search for: Klivans, Adam R.
- New search for: Long, Philip M.
- New search for: Tang, Alex K.
- New search for: Klivans, Adam R.
- New search for: Long, Philip M.
- New search for: Tang, Alex K.
In:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
2
;
588-600
;
2009
- Article/Chapter (Book) / Electronic Resource
-
Title:Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions
-
Contributors:
-
Published in:Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 2 ; 588-600Lecture Notes in Computer Science ; 5687, 2 ; 588-600
-
Publisher:
- New search for: Springer Berlin Heidelberg
-
Place of publication:Berlin, Heidelberg
-
Publication date:2009-01-01
-
Size:13 pages
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Article/Chapter (Book)
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Source:
Table of contents eBook
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar GraphsAazami, Ashkan / Cheriyan, Joseph / Jampani, Krishnam Raju et al. | 2009
- 15
-
Adaptive Sampling for k-Means ClusteringAggarwal, Ankit / Deshpande, Amit / Kannan, Ravi et al. | 2009
- 29
-
Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal GraphsCarroll, Douglas E. / Meyerson, Adam / Tagiku, Brian et al. | 2009
- 42
-
Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer ProgramsChekuri, Chandra / Ene, Alina / Korula, Nitish et al. | 2009
- 56
-
Truthful Mechanisms via Greedy Iterative PackingChekuri, Chandra / Gamzu, Iftah et al. | 2009
- 70
-
Resource Minimization Job SchedulingChuzhoy, Julia / Codenotti, Paolo et al. | 2009
- 84
-
The Power of Preemption on Unrelated Machines and Applications to Scheduling OrdersCorrea, José R. / Skutella, Martin / Verschae, José et al. | 2009
- 98
-
New Hardness Results for Diophantine ApproximationEisenbrand, Friedrich / Rothvoß, Thomas et al. | 2009
- 111
-
PASS ApproximationFeige, Uriel / Immorlica, Nicole / Mirrokni, Vahab S. / Nazerzadeh, Hamid et al. | 2009
- 125
-
Optimal Sherali-Adams Gaps from Pairwise IndependenceGeorgiou, Konstantinos / Magen, Avner / Tulsiani, Madhur et al. | 2009
- 140
-
An Approximation Scheme for Terrain GuardingGibson, Matt / Kanade, Gaurav / Krohn, Erik / Varadarajan, Kasturi et al. | 2009
- 149
-
Scheduling with OutliersGupta, Anupam / Krishnaswamy, Ravishankar / Kumar, Amit / Segev, Danny et al. | 2009
- 163
-
Improved Inapproximability Results for Maximum k-Colorable SubgraphGuruswami, Venkatesan / Sinop, Ali Kemal et al. | 2009
- 177
-
Improved Absolute Approximation Ratios for Two-Dimensional Packing ProblemsHarren, Rolf / Stee, Rob et al. | 2009
- 190
-
On the Optimality of Gluing over ScalesJaffe, Alex / Lee, James R. / Moharrami, Mohammad et al. | 2009
- 202
-
On Hardness of Pricing Items for Single-Minded BiddersKhandekar, Rohit / Kimbrel, Tracy / Makarychev, Konstantin / Sviridenko, Maxim et al. | 2009
- 217
-
Real-Time Message Routing and SchedulingKoch, Ronald / Peis, Britta / Skutella, Martin / Wiese, Andreas et al. | 2009
- 231
-
Approximating Some Network Design Problems with Node CostsKortsarz, Guy / Nutov, Zeev et al. | 2009
- 244
-
Submodular Maximization over Multiple Matroids via Generalized Exchange PropertiesLee, Jon / Sviridenko, Maxim / Vondrák, Jan et al. | 2009
- 258
-
Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams HierarchyMagen, Avner / Moharrami, Mohammad et al. | 2009
- 272
-
Minimizing Average Shortest Path Distances via Shortcut Edge AdditionMeyerson, Adam / Tagiku, Brian et al. | 2009
- 286
-
Approximating Node-Connectivity Augmentation ProblemsNutov, Zeev et al. | 2009
- 298
-
A 7/9 - Approximation Algorithm for the Maximum Traveling Salesman ProblemPaluch, Katarzyna / Mucha, Marcin / Ma̧dry, Aleksander et al. | 2009
- 312
-
Approximation Algorithms for Domatic Partitions of Unit Disk GraphsPandit, Saurav / Pemmaraju, Sriram V. / Varadarajan, Kasturi et al. | 2009
- 326
-
On the Complexity of the Asymmetric VPN ProblemRothvoß, Thomas / Sanità, Laura et al. | 2009
- 339
-
Deterministic Approximation Algorithms for the Nearest Codeword ProblemAlon, Noga / Panigrahy, Rina / Yekhanin, Sergey et al. | 2009
- 352
-
Strong Parallel Repetition Theorem for Free Projection GamesBarak, Boaz / Rao, Anup / Raz, Ran / Rosen, Ricky / Shaltiel, Ronen et al. | 2009
- 366
-
Random Low Degree Polynomials are Hard to ApproximateBen-Eliezer, Ido / Hod, Rani / Lovett, Shachar et al. | 2009
- 378
-
Composition of Semi-LTCs by Two-Wise Tensor ProductsBen-Sasson, Eli / Viderman, Michael et al. | 2009
- 392
-
On the Security of Goldreich’s One-Way FunctionBogdanov, Andrej / Qiao, Youming et al. | 2009
- 406
-
Random Tensors and Planted CliquesBrubaker, S. Charles / Vempala, Santosh S. et al. | 2009
- 420
-
Sampling s-Concave Functions: The Limit of Convexity Based IsoperimetryChandrasekaran, Karthekeyan / Deshpande, Amit / Vempala, Santosh et al. | 2009
- 434
-
Average-Case Analyses of Vickrey CostsChebolu, Prasad / Frieze, Alan / Melsted, Páll / Sorkin, Gregory B. et al. | 2009
- 448
-
A Hypergraph Dictatorship Test with Perfect CompletenessChen, Victor et al. | 2009
- 462
-
Extractors Using Hardness AmplificationDe, Anindya / Trevisan, Luca et al. | 2009
- 476
-
How Well Do Random Walks Parallelize?Efremenko, Klim / Reingold, Omer et al. | 2009
- 490
-
An Analysis of Random-Walk Cuckoo HashingFrieze, Alan / Melsted, Páll / Mitzenmacher, Michael et al. | 2009
- 504
-
Hierarchy Theorems for Property TestingGoldreich, Oded / Krivelevich, Michael / Newman, Ilan / Rozenberg, Eyal et al. | 2009
- 520
-
Algorithmic Aspects of Property Testing in the Dense Graphs ModelGoldreich, Oded / Ron, Dana et al. | 2009
- 534
-
Succinct Representation of Codes with Applications to TestingGrigorescu, Elena / Kaufman, Tali / Sudan, Madhu et al. | 2009
- 548
-
Efficient Quantum Tensor Product Expanders and k-DesignsHarrow, Aram W. / Low, Richard A. et al. | 2009
- 562
-
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of ANDJayram, T. S. et al. | 2009
- 574
-
Pseudorandom Generators and Typically-Correct DerandomizationKinne, Jeff / Melkebeek, Dieter / Shaltiel, Ronen et al. | 2009
- 588
-
Baum’s Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave DistributionsKlivans, Adam R. / Long, Philip M. / Tang, Alex K. et al. | 2009
- 601
-
Tolerant Linearity Testing and Locally Testable CodesKopparty, Swastik / Saraf, Shubhangi et al. | 2009
- 615
-
Pseudorandom Bit Generators That Fool Modular SumsLovett, Shachar / Reingold, Omer / Trevisan, Luca / Vadhan, Salil et al. | 2009
- 631
-
The Glauber Dynamics for Colourings of Bounded Degree TreesLucier, Brendan / Molloy, Michael / Peres, Yuval et al. | 2009
- 646
-
Testing ±1-weight halfspaceMatulef, Kevin / O’Donnell, Ryan / Rubinfeld, Ronitt / Servedio, Rocco A. et al. | 2009
- 658
-
Small-Bias Spaces for Group ProductsMeka, Raghu / Zuckerman, David et al. | 2009
- 673
-
Small Clique Detection and Approximate Nash EquilibriaMinder, Lorenz / Vilenchik, Dan et al. | 2009
- 686
-
Testing Computability by Width Two OBDDsRon, Dana / Tsur, Gilad et al. | 2009
- 700
-
Improved Polynomial Identity Testing for Read-Once FormulasShpilka, Amir / Volkovich, Ilya et al. | 2009
- 714
-
Smooth Analysis of the Condition Number and the Least Singular ValueTao, Terence / Vu, Van et al. | 2009
- E1
-
Erratum: Resource Minimization Job SchedulingChuzhoy, Julia / Codenotti, Paolo et al. | 2009