Edit Distance: Sketching, Streaming, and Document Exchange (Englisch)
- Neue Suche nach: Belazzougui, Djamal
- Neue Suche nach: Zhang, Qin
- Neue Suche nach: Belazzougui, Djamal
- Neue Suche nach: Zhang, Qin
In:
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)
;
51-60
;
2016
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Elektronische Ressource
-
Titel:Edit Distance: Sketching, Streaming, and Document Exchange
-
Beteiligte:Belazzougui, Djamal ( Autor:in ) / Zhang, Qin ( Autor:in )
-
Erschienen in:
-
Verlag:
- Neue Suche nach: IEEE
-
Erscheinungsdatum:01.10.2016
-
Format / Umfang:289618 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
-
Bounded-Communication Leakage Resilience via Parity-Resilient CircuitsGoyal, Vipul / Ishai, Yuval / Maji, Hemanta K. / Sahai, Amit / Sherstov, Alexander A. et al. | 2016
- 11
-
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded EncodingsLin, Huijia / Vaikuntanathan, Vinod et al. | 2016
- 21
-
Breaking the Three Round Barrier for Non-malleable CommitmentsGoyal, Vipul / Khurana, Dakshita / Sahai, Amit et al. | 2016
- 31
-
Zero-Knowledge Proof Systems for QMABroadbent, Anne / Ji, Zhengfeng / Song, Fang / Watrous, John et al. | 2016
- 41
-
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream StatisticsChakrabarti, Amit / Kale, Sagar et al. | 2016
- 51
-
Edit Distance: Sketching, Streaming, and Document ExchangeBelazzougui, Djamal / Zhang, Qin et al. | 2016
- 61
-
Heavy Hitters via Cluster-Preserving ClusteringLarsen, Kasper Green / Nelson, Jelani / Nguyen, Huy L. / Thorup, Mikkel et al. | 2016
- 71
-
Optimal Quantile Approximation in StreamsKarnin, Zohar / Lang, Kevin / Liberty, Edo et al. | 2016
- 79
-
An Average-Case Depth Hierarchy Theorem for Higher DepthHastad, Johan et al. | 2016
- 89
-
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit FunctionFind, Magnus Gausdal / Golovnev, Alexander / Hirsch, Edward A. / Kulikov, Alexander S. et al. | 2016
- 99
-
Depth-Reduction for CompositesChen, Shiteng / Papakonstantinou, Periklis A. et al. | 2016
- 109
-
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity TestingGarg, Ankit / Gurvits, Leonid / Oliveira, Rafael / Wigderson, Avi et al. | 2016
- 118
-
The Salesman's Improved Paths: A 3/2+1/34 ApproximationSebo, Andras / Zuylen, Anke Van et al. | 2016
- 128
-
Hopsets with Constant Hopbound, and Applications to Approximate Shortest PathsElkin, Michael / Neiman, Ofer et al. | 2016
- 138
-
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform DistributionsIm, Sungjin / Li, Shi et al. | 2016
- 148
-
Online Algorithms for Covering and Packing Problems with Convex ObjectivesAzar, Yossi / Buchbinder, Niv / Chan, T-H. Hubert / Chen, Shahar / Cohen, Ilan Reuven / Gupta, Anupam / Huang, Zhiyi / Kang, Ning / Nagarajan, Viswanath / Naor, Joseph et al. | 2016
- 158
-
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification ProtocolsChattopadhyay, Eshan / Li, Xin et al. | 2016
- 168
-
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic EntropyLi, Xin et al. | 2016
- 178
-
Extractors for Near Logarithmic Min-EntropyCohen, Gil / Schulman, Leonard J. et al. | 2016
- 188
-
Making the Most of Advice: New Correlation Breakers and Their ApplicationsCohen, Gil et al. | 2016
- 197
-
The Hilbert Function, Algebraic Extractors, and Recursive Fourier SamplingRemscrim, Zachary et al. | 2016
- 209
-
Computational Efficiency Requires Simple TaxationDobzinski, Shahar et al. | 2016
- 219
-
Learning in Auctions: Regret is Hard, Envy is EasyDaskalakis, Constantinos / Syrgkanis, Vasilis et al. | 2016
- 229
-
On the Communication Complexity of Approximate Fixed PointsRoughgarden, Tim / Weinstein, Omri et al. | 2016
- 239
-
Informational SubstitutesChen, Yiling / Waggoner, Bo et al. | 2016
- 248
-
Constrained Submodular Maximization: Beyond 1/eEne, Alina / Nguyen, Huy L. et al. | 2016
- 258
-
Settling the Complexity of Computing Approximate Two-Player Nash EquilibriaRubinstein, Aviad et al. | 2016
- 266
-
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity LearningRaz, Ran et al. | 2016
- 276
-
Ramanujan Graphs in Polynomial TimeCohen, Michael B. et al. | 2016
- 282
-
Structure of Protocols for XOR FunctionsHatami, Hamed / Hosseini, Kaave / Lovett, Shachar et al. | 2016
- 289
-
The Multiparty Communication Complexity of Interleaved Group ProductsGowers, W.T. / Viola, Emanuele et al. | 2016
- 295
-
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)de Rezende, Susanna F. / Nordstrom, Jakob / Vinyals, Marc et al. | 2016
- 305
-
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party CommunicationWeinstein, Omri / Yu, Huacheng et al. | 2016
- 315
-
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update TimeChechik, Shiri / Hansen, Thomas Dueholm / Italiano, Giuseppe F. / Lacki, Jakub / Parotsidis, Nikos et al. | 2016
- 325
-
Fully Dynamic Maximal Matching in Constant Update TimeSolomon, Shay et al. | 2016
- 335
-
On Fully Dynamic Graph SparsifiersAbraham, Ittai / Durfee, David / Koutis, Ioannis / Krinninger, Sebastian / Peng, Richard et al. | 2016
- 345
-
Linear Hashing Is AwesomeKnudsen, Mathias Bak Tejs et al. | 2016
- 353
-
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free MetricsCohen-Addad, Vincent / Klein, Philip N. / Mathieu, Claire et al. | 2016
- 365
-
Local Search Yields a PTAS for k-Means in Doubling MetricsFriggstad, Zachary / Rezapour, Mohsen / Salavatipour, Mohammad R. et al. | 2016
- 375
-
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus ProductBringmann, Karl / Grandoni, Fabrizio / Saha, Barna / Williams, Virginia Vassilevska et al. | 2016
- 385
-
Knuth Prize Lecture: Complexity of Communication in MarketsNisan, Noam et al. | 2016
- 386
-
No Occurrence Obstructions in Geometric Complexity TheoryBurgisser, Peter / Ikenmeyer, Christian / Panova, Greta et al. | 2016
- 396
-
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity TheoryIkenmeyer, Christian / Panova, Greta et al. | 2016
- 406
-
Exponential Lower Bounds for Monotone Span ProgramsRobere, Robert / Pitassi, Toniann / Rossman, Benjamin / Cook, Stephen A. et al. | 2016
- 416
-
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of AgentsAziz, Haris / Mackenzie, Simon et al. | 2016
- 428
-
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique ProblemBarak, Boaz / Hopkins, Samuel B. / Kelner, Jonathan / Kothari, Pravesh / Moitra, Ankur / Potechin, Aaron et al. | 2016
- 438
-
Polynomial-Time Tensor Decompositions with Sum-of-SquaresMa, Tengyu / Shi, Jonathan / Steurer, David et al. | 2016
- 447
-
Towards Strong Reverse Minkowski-Type Inequalities for LatticesDadush, Daniel / Regev, Oded et al. | 2016
- 457
-
Which Regular Expression Patterns Are Hard to Match?Backurs, Arturs / Indyk, Piotr et al. | 2016
- 467
-
Polynomial Representations of Threshold Functions and Algorithmic ApplicationsAlman, Josh / Chan, Timothy M. / Williams, Ryan et al. | 2016
- 477
-
Popular Conjectures as a Barrier for Dynamic Planar Graph AlgorithmsAbboud, Amir / Dahlgaard, Soren et al. | 2016
- 487
-
Max-Information, Differential Privacy, and Post-selection Hypothesis TestingRogers, Ryan / Roth, Aaron / Smith, Adam / Thakkar, Om et al. | 2016
- 495
-
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential MechanismRaskhodnikova, Sofya / Smith, Adam et al. | 2016
- 505
-
The Constant Inapproximability of the Parameterized Dominating Set ProblemChen, Yijia / Lin, Bingkai et al. | 2016
- 515
-
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern CoveringFomin, Fedor V. / Lokshtanov, Daniel / Marx, Daniel / Pilipczuk, Marcin / Pilipczuk, Michal / Saurabh, Saket et al. | 2016
- 525
-
Testing Assignments to Constraint Satisfaction ProblemsChen, Hubie / Valeriote, Matt / Yoshida, Yuichi et al. | 2016
- 535
-
Compressing Interactive Communication under Product DistributionsSherstov, Alexander A. et al. | 2016
- 545
-
Decidability of Non-interactive Simulation of Joint DistributionsGhazi, Badih / Kamath, Pritish / Sudan, Madhu et al. | 2016
- 555
-
Separations in Communication Complexity Using Cheat Sheets and Information ComplexityAnshu, Anurag / Belovs, Aleksandrs / Ben-David, Shalev / Goos, Mika / Jain, Rahul / Kothari, Robin / Lee, Troy / Santha, Miklos et al. | 2016
- 565
-
Extension Complexity of Independent Set PolytopesGoos, Mika / Jain, Rahul / Watson, Thomas et al. | 2016
- 573
-
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and SimpleKyng, Rasmus / Sachdeva, Sushant et al. | 2016
- 583
-
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and MoreCohen, Michael B. / Kelner, Jonathan / Peebles, John / Peng, Richard / Sidford, Aaron / Vladu, Adrian et al. | 2016
- 593
-
Computing Maximum Flow with Augmenting Electrical FlowsMadry, Aleksander et al. | 2016
- 603
-
Optimizing Star-Convex FunctionsLee, Jasper C.H. / Valiant, Paul et al. | 2016
- 615
-
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL ModelChang, Yi-Jun / Kopelowitz, Tsvi / Pettie, Seth et al. | 2016
- 625
-
Local Conflict ColoringFraigniaud, Pierre / Heinrich, Marc / Kosowski, Adrian et al. | 2016
- 635
-
A Fast and Simple Unbiased Estimator for Network (Un)reliabilityKarger, David R. et al. | 2016
- 645
-
A New Framework for Distributed Submodular MaximizationBarbosa, Rafael Da Ponte / Ene, Alina / Nguyen, Huy L. / Ward, Justin et al. | 2016
- 655
-
Robust Estimators in High Dimensions without the Computational IntractabilityDiakonikolas, Ilias / Kamath, Gautam / Kane, Daniel M. / Li, Jerry / Moitra, Ankur / Stewart, Alistair et al. | 2016
- 665
-
Agnostic Estimation of Mean and CovarianceLai, Kevin A. / Rao, Anup B. / Vempala, Santosh et al. | 2016
- 675
-
Noisy Population Recovery in Polynomial TimeDe, Anindya / Saks, Michael / Tang, Sijian et al. | 2016
- 685
-
A New Approach for Testing Properties of Discrete DistributionsDiakonikolas, Ilias / Kane, Daniel M. et al. | 2016
- 695
-
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant ComponentJoos, Felix / Perarnau, Guillem / Rautenbach, Dieter / Reed, Bruce et al. | 2016
- 704
-
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core ModelEfthymiou, Charilaos / Hayes, Thomas P. / Stefankovic, Daniel / Vigoda, Eric / Yin, Yitong et al. | 2016
- 714
-
Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated AnnealingCrosson, Elizabeth / Harrow, Aram W. et al. | 2016
- 724
-
The Number of Solutions for Random Regular NAE-SATSly, Allan / Sun, Nike / Zhang, Yumeng et al. | 2016
- 732
-
Accelerated Newton Iteration for Roots of Black Box PolynomialsLouis, Anand / Vempala, Santosh S. et al. | 2016
- 741
-
Fourier-Sparse Interpolation without a Frequency GapChen, Xue / Kane, Daniel M. / Price, Eric / Song, Zhao et al. | 2016
- 751
-
Robust Fourier and Polynomial Curve FittingGuruswami, Venkatesan / Zuckerman, David et al. | 2016
- 760
-
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott ProblemGandikota, Venkata / Ghazi, Badih / Grigorescu, Elena et al. | 2016
- 770
-
Amplification and Derandomization without SlowdownGrossman, Ofer / Moshkovitz, Dana et al. | 2016
- 780
-
Commutativity in the Algorithmic Lovász Local LemmaKolmogorov, Vladimir et al. | 2016
- 788
-
An Algorithm for Komlós Conjecture Matching Banaszczyk's BoundBansal, Nikhil / Dadush, Daniel / Garg, Shashwat et al. | 2016
- 800
-
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires UndirectednessHendricks, Jacob / Patitz, Matthew J. / Rogers, Trent A. et al. | 2016
- 810
-
A PTAS for the Steiner Forest Problem in Doubling MetricsChan, T-H. Hubert / Hu, Shuguang / Jiang, Shaofeng H.-C. et al. | 2016
- 820
-
On Approximating Maximum Independent Set of RectanglesChuzhoy, Julia / Ene, Alina et al. | 2016
- 830
-
Author Index| 2016
- 834
-
Publisher's Information| 2016
- c1
-
Cover Art| 2016
- i
-
Title Page i| 2016
- iii
-
Title Page iii| 2016
- iv
-
Copyright Page| 2016
- v
-
Table of Contents| 2016
- xiii
-
Preface| 2016
- xiv
-
Organizing Committee and Sponsors| 2016
- xix
-
Awards| 2016
- xv
-
Program Committee| 2016
- xvi
-
External Reviewers| 2016