(1 + eps)-Approximate Sparse Recovery (Englisch)
- Neue Suche nach: Price, E.
- Neue Suche nach: Woodruff, D. P.
- Neue Suche nach: Price, E.
- Neue Suche nach: Woodruff, D. P.
In:
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
;
295-304
;
2011
-
ISSN:
- Aufsatz (Konferenz) / Elektronische Ressource
-
Titel:(1 + eps)-Approximate Sparse Recovery
-
Beteiligte:Price, E. ( Autor:in ) / Woodruff, D. P. ( Autor:in )
-
Erschienen in:
-
Verlag:
- Neue Suche nach: IEEE
-
Erscheinungsdatum:01.10.2011
-
Format / Umfang:536660 byte
-
ISBN:
-
ISSN:
-
DOI:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Elektronische Ressource
-
Sprache:Englisch
-
Datenquelle:
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 1
-
The Promise of Differential Privacy: A Tutorial on Algorithmic TechniquesDwork, C. et al. | 2011
- 3
-
Green Computing AlgorithmicsPruhs, K. et al. | 2011
- 5
-
Computing Blindfolded: New Developments in Fully Homomorphic EncryptionVaikuntanathan, Vinod et al. | 2011
- 17
-
Min-max Graph Partitioning and Small Set ExpansionBansal, N. / Feige, U. / Krauthgamer, R. / Makarychev, K. / Nagarajan, V. / Naor, J. / Schwartz, R. et al. | 2011
- 27
-
The Graph Minor Algorithm with Parity ConditionsKawarabayashi, K. / Reed, B. / Wollan, P. et al. | 2011
- 37
-
Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with ApplicationsWulff-Nilsen, C. et al. | 2011
- 47
-
A Constant Factor Approximation Algorithm for Unsplittable Flow on PathsBonsma, P. / Schulz, J. / Wiese, A. et al. | 2011
- 57
-
How Bad is Forming Your Own Opinion?Bindel, D. / Kleinberg, J. / Oren, S. et al. | 2011
- 67
-
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson SolutionsGoldberg, P. W. / Papadimitriou, C. H. / Savani, R. et al. | 2011
- 77
-
Welfare and Profit Maximization with Production CostsBlum, A. / Gupta, A. / Mansour, Y. / Sharma, A. et al. | 2011
- 87
-
Mechanism Design with Set-Theoretic BeliefsJing Chen, / Micali, S. et al. | 2011
- 97
-
Efficient Fully Homomorphic Encryption from (Standard) LWEBrakerski, Z. / Vaikuntanathan, V. et al. | 2011
- 107
-
Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic CircuitsGentry, C. / Halevi, S. et al. | 2011
- 110
-
Coin Flipping with Constant Bias Implies One-Way FunctionsHaitner, I. / Omri, E. et al. | 2011
- 120
-
How to Garble Arithmetic CircuitsApplebaum, B. / Ishai, Y. / Kushilevitz, E. et al. | 2011
- 130
-
Sharp Mixing Time Bounds for Sampling Random SurfacesCaputo, P. / Martinelli, F. / Toninelli, F. L. et al. | 2011
- 140
-
Improved Mixing Condition on the Grid for Counting and Sampling Independent SetsRestrepo, R. / Jinwoo Shin, / Tetali, P. / Vigoda, E. / Linji Yang, et al. | 2011
- 150
-
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential TimeCygan, M. / Nederlof, J. / Pilipczuk, M. / van Rooij, Joham M. M. / Wojtaszczyk, J. O. et al. | 2011
- 160
-
The Minimum k-way Cut of Bounded Size is Fixed-Parameter TractableKawarabayashi, K. / Thorup, M. et al. | 2011
- 170
-
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear TimeBorradaile, G. / Klein, P. N. / Mozes, S. / Nussbaum, Y. / Wulff-Nilsen, C. et al. | 2011
- 180
-
Minimum Weight Cycles and Triangles: Equivalences and AlgorithmsRoditty, L. / Williams, V. V. et al. | 2011
- 190
-
Graph Connectivities, Network Coding, and Expander GraphsHo Yee Cheung, / Lap Chi Lau, / Kai Man Leung, et al. | 2011
- 200
-
Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2Seguin-Charbonneau, L. / Shepherd, F. B. et al. | 2011
- 210
-
Online Node-Weighted Steiner Tree and Related ProblemsNaor, J. / Panigrahi, D. / Singh, M. et al. | 2011
- 220
-
Extractors for Circuit SourcesViola, E. et al. | 2011
- 230
-
Randomness Buys Depth for Approximate CountingViola, E. et al. | 2011
- 240
-
Pseudorandomness for Read-Once FormulasBogdanov, A. / Papakonstaninou, P. A. / Wan, A. et al. | 2011
- 247
-
Dispersers for Affine Sources with Sub-polynomial EntropyShaltiel, R. et al. | 2011
- 257
-
A Small PRG for Polynomial Threshold Functions of GaussiansKane, Daniel M. et al. | 2011
- 267
-
A Polylogarithmic-Competitive Algorithm for the k-Server ProblemBansal, N. / Buchbinder, N. / Madry, A. / Naor, J. et al. | 2011
- 277
-
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in GeneralHertli, Timon et al. | 2011
- 285
-
On the Power of Adaptivity in Sparse RecoveryIndyk, P. / Price, E. / Woodruff, D. P. et al. | 2011
- 295
-
(1 + eps)-Approximate Sparse RecoveryPrice, E. / Woodruff, D. P. et al. | 2011
- 305
-
Near Optimal Column-Based Matrix ReconstructionBoutsidis, C. / Drineas, P. / Magdon-Ismail, Malik et al. | 2011
- 315
-
Near Linear Lower Bound for Dimension Reduction in L1Andoni, A. / Charikar, M. S. / Neiman, O. / Nguyen, H. L. et al. | 2011
- 324
-
The 1D Area Law and the Complexity of Quantum States: A Combinatorial ApproachAharonov, D. / Arad, I. / Landau, Z. / Vazirani, U. et al. | 2011
- 334
-
On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such SystemsAharonov, D. / Eldar, L. et al. | 2011
- 344
-
Quantum Query Complexity of State ConversionLee, T. / Mittal, R. / Reichardt, B. W. / Spalek, R. / Szegedy, M. et al. | 2011
- 354
-
Optimal Bounds for Quantum Bit CommitmentChailloux, A. / Kerenidis, I. et al. | 2011
- 363
-
Streaming Algorithms via Precision SamplingAndoni, A. / Krauthgamer, R. / Onak, K. et al. | 2011
- 373
-
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning OnesElkin, M. / Solomon, S. et al. | 2011
- 383
-
Fully Dynamic Maximal Matching in O (log n) Update TimeBaswana, S. / Gupta, M. / Sen, S. et al. | 2011
- 393
-
Which Networks are Least Susceptible to Cascading Failures?Blume, L. / Easley, D. / Kleinberg, J. / Kleinberg, R. / Tardos, E. et al. | 2011
- 403
-
The Power of Linear EstimatorsValiant, G. / Valiant, P. et al. | 2011
- 413
-
An Algebraic Proof of a Robust Social Choice Impossibility TheoremFalik, D. / Friedgut, E. et al. | 2011
- 423
-
Planar Graphs: Random Walks and Bipartiteness TestingCzumaj, A. / Monemizadeh, M. / Onak, K. / Sohler, C. et al. | 2011
- 433
-
Testing and Reconstruction of Lipschitz Functions with Applications to Data PrivacyJha, M. / Raskhodnikova, S. et al. | 2011
- 443
-
How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique GamesKolla, A. / Makarychev, K. / Makarychev, Y. et al. | 2011
- 453
-
The Grothendieck Constant is Strictly Smaller than Krivine's BoundBraverman, M. / Makarychev, K. / Makarychev, Y. / Naor, A. et al. | 2011
- 463
-
A Parallel Approximation Algorithm for Positive Semidefinite ProgrammingJain, R. / Penghui Yao, et al. | 2011
- 472
-
Rounding Semidefinite Programming Hierarchies via Global CorrelationBarak, B. / Raghavendra, P. / Steurer, D. et al. | 2011
- 482
-
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD ObjectivesGuruswami, V. / Sinop, A. K. et al. | 2011
- 492
-
Markov LayoutChierichetti, F. / Kumar, R. / Raghavan, P. et al. | 2011
- 502
-
Limitations of Randomized Mechanisms for Combinatorial AuctionsDughmi, S. / Vondrak, Jan et al. | 2011
- 512
-
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many BuyersAlaei, S. et al. | 2011
- 522
-
Extreme-Value Theorems for Optimal Multidimensional PricingYang Cai, / Daskalakis, C. et al. | 2011
- 532
-
Efficient Computation of Approximate Pure Nash Equilibria in Congestion GamesCaragiannis, I. / Fanelli, A. / Gravin, N. / Skopalik, A. et al. | 2011
- 542
-
On Range Searching in the Group Model and Combinatorial DiscrepancyLarsen, K. G. et al. | 2011
- 550
-
A Randomized Rounding Approach to the Traveling Salesman ProblemGharan, S. O. / Saberi, A. / Singh, M. et al. | 2011
- 560
-
Approximating Graphic TSP by MatchingsMomke, T. / Svensson, O. et al. | 2011
- 570
-
A Unified Continuous Greedy Algorithm for Submodular MaximizationFeldman, M. / Naor, Joseph / Schwartz, R. et al. | 2011
- 580
-
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid CoveringsDadush, D. / Peikert, C. / Vempala, S. et al. | 2011
- 590
-
A Nearly-m log n Time Solver for SDD Linear SystemsKoutis, I. / Miller, G. L. / Peng, R. et al. | 2011
- 599
-
Balls and Bins: Smaller Hash Families and Faster EvaluationCelis, L. E. / Reingold, O. / Segev, G. / Wieder, U. et al. | 2011
- 609
-
Lexicographic Products and the Power of Non-linear Network CodingBlasiak, A. / Kleinberg, R. / Lubetzky, E. et al. | 2011
- 619
-
Quadratic Goldreich-Levin TheoremsTulsiani, M. / Wolf, J. et al. | 2011
- 629
-
Optimal Testing of Multivariate Polynomials over Small Prime FieldsHaramaty, E. / Shpilka, A. / Sudan, M. et al. | 2011
- 638
-
Tight Lower Bounds for 2-query LCCs over Finite FieldsBhattacharyya, A. / Dvir, Z. / Shpilka, A. / Saraf, S. et al. | 2011
- 648
-
A Two Prover One Round Game with Strong SoundnessKhot, S. / Safra, M. et al. | 2011
- 658
-
The Randomness Complexity of Parallel RepetitionKai-Min Chung, / Pass, R. et al. | 2011
- 668
-
Privacy Amplification and Non-malleable Extractors via Character SumsDodis, Y. / Xin Li, / Wooley, T. D. / Zuckerman, D. et al. | 2011
- 678
-
Stateless Cryptographic ProtocolsGoyal, V. / Maji, H. K. et al. | 2011
- 688
-
Storing Secrets on Continually Leaky DevicesDodis, Y. / Lewko, A. / Waters, B. / Wichs, D. et al. | 2011
- 698
-
Medium Access Using QueuesShah, D. / Jinwoo Shin, / Tetali, P. et al. | 2011
- 708
-
Local Distributed DecisionFraigniaud, P. / Korman, A. / Peleg, D. et al. | 2011
- 718
-
The Complexity of RenamingAlistarh, D. / Aspnes, J. / Gilbert, S. / Guerraoui, R. et al. | 2011
- 728
-
Mutual Exclusion with O(log^2 Log n) Amortized WorkBender, M. A. / Gilbert, S. et al. | 2011
- 738
-
Algorithms for the Generalized Sorting ProblemZhiyi Huang, / Kannan, S. / Khanna, S. et al. | 2011
- 748
-
Information Equals Amortized CommunicationBraverman, Mark / Rao, A. et al. | 2011
- 758
-
Delays and the Capacity of Continuous-Time ChannelsKhanna, S. / Sudan, M. et al. | 2011
- 768
-
Efficient and Explicit Coding for Interactive CommunicationGelles, R. / Moitra, A. / Sahai, A. et al. | 2011
- 778
-
Efficient Reconstruction of Random Multilinear FormulasGupta, A. / Kayal, N. / Lokam, S. et al. | 2011
- 788
-
New Extension of the Weil Bound for Character Sums with Applications to CodingKaufman, T. / Lovett, S. et al. | 2011
- 797
-
Maximizing Expected Utility for Stochastic Combinatorial Optimization ProblemsJian Li, / Deshpande, A. et al. | 2011
- 807
-
Approximation Algorithms for Submodular Multiway PartitionChekuri, C. / Ene, A. et al. | 2011
- 817
-
An FPTAS for #Knapsack and Related Counting ProblemsGopalan, P. / Klivans, A. / Meka, R. / Stefankovic, D. / Vempala, S. / Vigoda, E. et al. | 2011
- 827
-
Approximation Algorithms for Correlated Knapsacks and Non-martingale BanditsGupta, A. / Krishnaswamy, R. / Molinaro, M. / Ravi, R. et al. | 2011
- 837
-
Evolution with RecombinationKanade, Varun et al. | 2011
- 847
-
Author index| 2011
- 850
-
[Publishers information]| 2011
- C1
-
[Front cover]| 2011
- i
-
[Title page i]| 2011
- iii
-
[Title page iii]| 2011
- iv
-
[Copyright notice]| 2011
- v
-
Table of contents| 2011
- xiii
-
Organizing Committee| 2011
- xiv
-
Program Committee| 2011
- xv
-
Reviewers| 2011