NDLI: The k-mismatch problem revisited

Please wait, while we are loading the content...

Locality-sensitive hashing without false negatives

New directions in nearest neighbor searching with applications to lattice sieving

Undirected graph exploration with Θ(log log n) pebbles

Phase transitions in group testing

Tight bounds for the distribution-free testing of monotone conjunctions

Designing networks with good equilibria under uncertainty

An improved combinatorial polynomial algorithm for the linear arrow-debreu market

Characterisation of strongly stable matchings

Learning and efficiency in games with dynamic population

The complexity of all-switches strategy improvement

Make-to-order integrated scheduling and distribution

An O(log m)-competitive algorithm for online machine minimization

Online degree-bounded steiner network design

Scheduling parallel DAG jobs online to minimize average flow time

Online pricing with impatient bidders

Distributed algorithms for planar networks II: low-congestion shortcuts, MST, and Min-Cut

Local-on-average distributed tasks

The adversarial noise threshold for distributed protocols

Expanders via local edge flips

An improved distributed algorithm for maximal independent set

Nearly tight oblivious subspace embeddings by trace inequalities

The restricted isometry property of subsampled fourier matrices

Nearly optimal deterministic algorithm for sparse walsh-hadamard transform

Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching

Simpler, faster and shorter labels for distances in graphs

Approximate distance oracles for planar graphs with improved query time-space tradeoff

New bounds for approximating extremal distances in undirected graphs

Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs

Deterministic algorithms for submodular maximization problems

Improved approximation algorithms for k-submodular function maximization

Locally adaptive optimization: adaptive seeding for monotone submodular functions

Exact and approximation algorithms for weighted matroid intersection

A fast approximation for maximum weight matroid intersection

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Bounds for random constraint satisfaction problems via spatial coupling

Evolutionary dynamics in finite populations mix rapidly

Random-cluster dynamics in $Z^{2}$

Canonical paths for MCMC: from art to science

Towards optimal algorithms for prediction with expert advice

Sparse approximation via generating point sets

Weighted SGD for $ℓ_{p}$ regression with randomized preconditioning

Non-convex compressed sensing with the sum-of-squares method

Jointly private convex programming

Time vs. information tradeoffs for leader election in anonymous trees

Markovian hitters and the complexity of blind rendezvous

Stabilizing consensus with many opinions

How to scale exponential backoff: constant throughput, polylog access attempts, and robustness

Balanced allocation: patience is not a virtue

Weighted dynamic finger in binary search trees

Faster fully dynamic matchings with small approximation ratios

Dynamic (1 + ε)-approximate matchings: a density-sensitive approach

Dynamic DFS in undirected graphs: breaking the O(m) barrier

On dynamic approximate shortest paths for planar graphs with worst-case costs

Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics

Clustering time series under the fréachet distance

Approximating capacitated k-median with (1 + ε)k open facilities

Simple and fast rounding algorithms for directed and node-weighted multiway cut

Constant factor approximation for subset feedback set problems via a new LP relaxation

Approximating low-stretch spanners

Error amplification for pairwise spanner lower bounds

Better distance preservers and additive spanners

On notions of distortion and an almost minimum spanning tree with constant average distortion

Near-optimal light spanners

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

Efficient quantum algorithms for (gapped) group testing and junta testing

Permutation patterns are hard to count

Computing in continuous space with self-assembling polygonal tiles (extended abstract)

Beyond the Richter-Thomassen conjecture

Treetopes and their graphs

Windrose planarity: embedding graphs with direction-constrained edges

Multiscale mapper: topological summarization via codomain covers

Online contention resolution schemes

Finding a stable allocation in polymatroid intersection

An improved approximation guarantee for the maximum budgeted allocation problem

The matching problem has no small symmetric SDP

On the integrality gap of degree-4 sum of squares for planted clique

Linear recognition of almost interval graphs

Subexponential parameterized algorithm for interval completion

lower bounds for the parameterized complexity of minimum fill-in and other completion problems

Raising the bar for vertex cover: fixed-parameter tractability above a higher guarantee

Directed multicut is W[1]-hard, even for four terminal pairs

An efficient algorithm for computing high-quality paths amid polygonal obstacles

Approximating the k-level in three-dimensional plane arrangements

Improved deterministic algorithms for linear programming in low dimensions

A fast and simple algorithm for computing approximate euclidean minimum spanning trees

Persistent homology and nested dissection

Deterministic APSP, orthogonal vectors, and more: quickly derandomizing razborov-smolensky

Subtree isomorphism revisited

Higher lower bounds from the 3SUM conjecture

A faster subquadratic algorithm for finding outlier correlations

Algorithmic complexity of power law networks

Kernelization via sampling with applications to finding matchings and related problems in dynamic graph streams

Maximum matchings in dynamic graph streams and the simultaneous communication model

Incidence geometries and the pass complexity of semi-streaming set cover

Clustering problems on sliding windows

Gowers norm, function limits, and parameter estimation

On the economic efficiency of the combinatorial clock auction

Approximately efficient double auctions with strong budget balance

Interpolating between truthful and non-truthful mechanisms for combinatorial auctions

On the complexity of dynamic mechanism design

Simple pricing schemes for consumers with evolving values

On approximating strip packing with a better ratio than 3/2

Packing small vectors

Approximation schemes for machine scheduling with resource (in-)dependent processing times

Integrality gaps and approximation algorithms for dispersers and bipartite expanders

Improved approximation for vector bin packing

Connectivity in bridge-addable graph classes: the mcdiarmid-steger-welsh conjecture

Recovery and rigidity in a regular stochastic block model

Distance in the forest fire model how far are you from eve?

Species trees from gene trees despite a high rate of lateral genetic transfer: a tight bound

The power of two choices with simple tabulation

Tight bounds for graph homomorphism and subgraph isomorphism

Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

Discovering archipelagos of tractability for constraint satisfaction and counting

Blocking optimal k-arborescences

Constructive algorithm for path-width of matroids

Approximation of non-boolean 2CSP

An FPTAS for minimizing indefinite quadratic forms over integers in polyhedra

Nearly optimal NP-hardness of unique coverage

Algorithms and adaptivity gaps for stochastic probing

Discrete gaussian sampling reduces to CVP and SVP

An algorithmic hypergraph regularity lemma

Obstructions for three-coloring graphs with one forbidden induced subgraph

Independence and efficient domination on $P_{6}-free$ graphs

Sparsity and dimension

Finding perfect matchings in bipartite hypergraphs

Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver

How to round subspaces: a new spectral clustering algorithm

Improved Cheeger's inequality and analysis of local graph partitioning using vertex expansion and expansion profile

Approximate undirected maximum flows in o(mpolylog(n)) time

Natural algorithms for flow problems

Efficient low-redundancy codes for correcting multiple deletions

An improved bound on the fraction of correctable deletions

Communication complexity of permutation-invariant functions

Towards optimal deterministic coding for interactive communication

Robust positioning patterns

Sampling on lattices with free boundary conditions using randomized extensions

On the switch markov chain for perfect matchings

Partial resampling to approximate covering integer programs

Algorithmic and enumerative aspects of the moser-tardos distribution

Focused stochastic local search and the lovász local lemma

The k-mismatch problem revisited

Range predecessor and lempel-ziv parsing

Communication with contextual uncertainty

Weak duality for packing edge-disjoint odd (u, v)-trails

On the maximum quartet distance between phylogenetic trees

The k-mismatch problem revisited

Content Provider	ACM Digital Library
Author	Starikovskaya, Tatiana Sach, Benjamin Clifford, Raphaël Fontaine, Allyx Porat, Ely
Abstract	We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output "No". We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows: • Our first result is a deterministic $O(nk^{2}$ log k/m + n polylog m) time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000 [9, 10]. • We then give a randomised and online algorithm which runs in the same time complexity but requires only $O(k^{2}$ polylog m) space in total. • Next we give a randomised (1 + ε)-approximation algorithm for the streaming k-mismatch problem which uses $O(k^{2}$ polylog $m/ε^{2})$ space and runs in O(polylog $m/ε^{2})$ worst-case time per arriving symbol. • Finally we combine our new results to derive a randomised $O(k^{2}$ polylog m) space algorithm for the streaming k-mismatch problem which runs in O([EQUATION] log k + polylog m) worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 [26] by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).
Starting Page	2039
Ending Page	2052
Page Count	14
File Format	PDF
ISBN	9781611974331
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-10
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in