https://pinboard.in/u:Vaguery/public/ recent bookmarks from Vaguery 2026-04-20T11:43:03+00:00 https://arxiv.org/abs/2309.16100 Vaguery rewriting-systems strings nonlinear-dynamics mathematical-recreations mathematics to-understand consider:feature-discovery consider:inverse-problem https://pinboard.in/ https://pinboard.in/u:Vaguery/b:90c29aada2bb/ 2026-01-01T01:34:24+00:00 https://arxiv.org/abs/2201.01268 Vaguery rewriting-systems strings rather-interesting number-theory group-theory computational-dynamics formal-languages https://pinboard.in/ https://pinboard.in/u:Vaguery/b:d7dbc0fd23fe/ 2026-01-01T01:30:54+00:00 https://arxiv.org/abs/2112.15563 Vaguery nonlinear-dynamics rewriting-systems strings looking-to-see stochastic-systems information-theory rather-interesting to-understand https://pinboard.in/ https://pinboard.in/u:Vaguery/b:6b78b87504f8/ 2025-12-31T18:17:15+00:00 https://arxiv.org/abs/1109.5635 Vaguery strings edit-distance algorithms computational-complexity rather-interesting to-understand follow-cites https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7479f24f2b7a/ 2025-12-31T17:56:32+00:00 https://arxiv.org/abs/2005.07678 Vaguery0. Our result completes a research direction set forth in the recent breakthrough paper [Chakraborty-Das-Goldenberg-Koucky-Saks, FOCS'18], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results of [Koucky-Saks, STOC'20] and [Brakensiek-Rubinstein, STOC'20] have shown near-linear time algorithms that obtain an additive approximation, near-linear in n (equivalently, constant-factor approximation when the edit distance value is close to n). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input strings. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings, of length niε for i=0,1,…,1/ε. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance. ]]> strings computational-complexity algorithms rather-interesting approximation to-write-about to-implement consider:Push-code https://pinboard.in/ https://pinboard.in/u:Vaguery/b:71df08420968/ 2025-09-11T20:39:50+00:00 https://arxiv.org/abs/2203.13545 Vaguery strings rewriting-systems automata stochastic-systems rather-interesting dynamical-systems group-theory to-understand to-simulate consider:computation quasicrystals aperiodic-tiling symbolic-dynamics https://pinboard.in/ https://pinboard.in/u:Vaguery/b:9b2124858de2/ 2025-08-17T12:19:53+00:00 https://arxiv.org/abs/2112.12678 Vaguery data-structures symbolic-dynamics strings computational-complexity rather-interesting to-understand this-might-be-just-the-thing ReQ https://pinboard.in/ https://pinboard.in/u:Vaguery/b:b2621692edf2/ 2025-08-17T12:17:13+00:00 https://arxiv.org/abs/2111.13134 Vaguery rewriting-systems strings rules representation rather-interesting to-understand symbolic-dynamics consider:approximation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:9dd60aff888a/ 2023-09-09T13:40:02+00:00 https://arxiv.org/abs/2210.02292 Vaguery strings palindromes algorithms computational-complexity data-structures rather-interesting to-understand https://pinboard.in/ https://pinboard.in/u:Vaguery/b:fa87703719d4/ 2023-05-16T11:01:30+00:00 https://arxiv.org/abs/2304.14395 Vaguery strings algorithms library rather-interesting python to-try consider:trees https://pinboard.in/ https://pinboard.in/u:Vaguery/b:92f9faee842c/ 2022-03-19T12:18:50+00:00 https://arxiv.org/abs/1703.00667 Vaguery data-structures sequences strings to-understand to-write-about consider:genetic-programming consider:runtime-search-algorithms https://pinboard.in/ https://pinboard.in/u:Vaguery/b:01cbd625ac4e/ 2022-03-11T11:37:01+00:00 https://arxiv.org/abs/1908.07846 Vaguery neural-networks strings image-processing representation rather-interesting to-write-about to-visualize consider:genetic-programming consider:robustness https://pinboard.in/ https://pinboard.in/u:Vaguery/b:eac50b22a9e5/ 2022-03-05T11:39:07+00:00 https://arxiv.org/abs/2103.02361 Vaguery rewriting-systems strings nonlinear-dynamics ergodic-systems information-theory rather-interesting to-write-about to-simulate consider:Kauffmaniac-chemistry artificial-chemistry https://pinboard.in/ https://pinboard.in/u:Vaguery/b:efdde26d0346/ 2022-03-04T11:27:07+00:00 https://arxiv.org/abs/1904.04513 Vaguery strings data-structures optimization algorithms rather-interesting performance-measure information-theory engineering-design to-write-about to-simulate consider:error https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7cd802a335d2/ 2022-03-02T11:38:43+00:00 https://arxiv.org/abs/1705.11130 Vaguery symbolic-regression rewriting-systems strings aperiodic-tiling looking-to-see enumeration rather-interesting https://pinboard.in/ https://pinboard.in/u:Vaguery/b:d13c42eaa4a8/ 2022-02-08T12:26:52+00:00 https://arxiv.org/abs/2101.10087 Vaguery strings software-engineering classification rather-interesting to-write-about consider:genetic-programming consider:clustering-ineffable-solutions https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7a910b0aa8b4/ 2022-01-29T14:04:51+00:00 https://arxiv.org/abs/2108.08613 Vaguery edit-distance computational-complexity algorithms strings rather-interesting to-write-about consider:genetic-programming consider:visualization https://pinboard.in/ https://pinboard.in/u:Vaguery/b:0462c88f827d/ 2022-01-29T13:56:16+00:00 https://arxiv.org/abs/1909.02512 Vaguery strings formal-languages biologically-inspired rewriting-systems rather-interesting to-write-about to-simulate consider:random-examples consider:dynamics consider:visualization grammar https://pinboard.in/ https://pinboard.in/u:Vaguery/b:f907e61ee423/ 2021-12-19T12:36:35+00:00 https://arxiv.org/abs/2107.06188 Vaguery symmetry combinatorics rather-interesting feature-construction group-theory strings to-understand to-write-about consider:code https://pinboard.in/ https://pinboard.in/u:Vaguery/b:497a7b1767d6/ 2021-11-16T10:27:29+00:00 https://arxiv.org/abs/2106.01190 Vaguery strings combinatorics enumeration algorithms rather-interesting to-write-about consider:implementation consider:concentration https://pinboard.in/ https://pinboard.in/u:Vaguery/b:2e21349d14e5/ 2021-07-14T11:10:42+00:00 https://arxiv.org/abs/2009.06080 Vaguery mathematical-recreations strings LOL-at-grad-school-when-I-tried-to-convince-Ewens-about-this probability-theory combinatorics formal-languages to-write-about to-visualize https://pinboard.in/ https://pinboard.in/u:Vaguery/b:62d7868af328/ 2021-07-08T19:47:40+00:00 https://arxiv.org/abs/2011.04072 Vaguery strings distance metrics edit-distance to-understand to-visualize https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7b5b52765d07/ 2021-07-08T10:49:03+00:00 https://arxiv.org/abs/2101.00332 Vaguery permutations strings to-understand enumeration feature-construction that-rationality-thing-tho https://pinboard.in/ https://pinboard.in/u:Vaguery/b:5dc2bb0caf1f/ 2021-01-21T21:08:56+00:00 https://arxiv.org/abs/1904.05459 Vaguery0 and a randomized algorithm that takes as input an integer n and two strings x,y of length at most n, and runs in time O(n1+1T) and outputs an upper bound U on the edit distance ED(x,y) that with high probability, satisfies U≤R(ED(x,y)+n1−ζ). In particular, on any input with ED(x,y)≥n1−ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (2019). ]]> strings edit-distance proof computational-complexity to-understand consider:looking-to-see consider:visualization https://pinboard.in/ https://pinboard.in/u:Vaguery/b:ba05fdb80253/ 2021-01-21T21:00:34+00:00 https://arxiv.org/abs/2002.06786 Vaguery strings bioinformatics algorithms rather-interesting hard-problems pattern-matching to-write-about to-simulate consider:representation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:9a95cb8f1ca9/ 2020-10-13T21:06:27+00:00 https://arxiv.org/abs/1902.04419 Vaguery strings DNA-computing combinatorics rather-interesting rather-odd multiobjective-optimization (would-be-better) to-write-about to-simulate consider:MO-approach permutations https://pinboard.in/ https://pinboard.in/u:Vaguery/b:cfbefc372b0b/ 2020-05-02T13:13:39+00:00 https://link.springer.com/article/10.1007/s11009-019-09706-8 Vaguery strings rewriting-systems combinatorics information-theory rather-interesting to-write-about to-simulate consider:grammars consider:parsimony consider:approximation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:305506a97f4b/ 2019-11-03T11:40:05+00:00 https://arxiv.org/abs/1605.03654 Vaguery number-theory group-theory to-understand rather-odd strings rewriting-systems combinatorics https://pinboard.in/ https://pinboard.in/u:Vaguery/b:abc5a19654b0/ 2019-09-09T11:05:16+00:00 https://arxiv.org/abs/1809.08490 Vaguery permutations strings rather-interesting mathematical-recreations dynamical-systems formal-languages constraint-satisfaction to-write-about to-simulate https://pinboard.in/ https://pinboard.in/u:Vaguery/b:614d8c6b8614/ 2019-09-08T11:42:36+00:00 https://arxiv.org/abs/1009.4061 Vaguery combinatorics rewriting-systems rather-interesting strings to-write-about to-simulate consider:performance-measures consider:approximation consider:genetic-programming consider:constraint-satisfaction https://pinboard.in/ https://pinboard.in/u:Vaguery/b:e0e0916da2d9/ 2019-06-12T13:21:04+00:00 https://arxiv.org/abs/1107.2422 Vaguery strings combinatorics patterns rather-interesting algorithms computational-complexity nudge-targets to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:32e9a0a0c82e/ 2019-03-02T01:15:07+00:00 https://arxiv.org/abs/1812.08101 Vaguery strings combinatorics algorithms patterns feature-construction rather-interesting nudge-targets https://pinboard.in/ https://pinboard.in/u:Vaguery/b:591df0e5acde/ 2019-03-02T01:14:33+00:00 https://arxiv.org/abs/1606.02868 Vaguery strings combinatorics patterns rather-interesting to-write-about consider:algorithms https://pinboard.in/ https://pinboard.in/u:Vaguery/b:6c5eef4d30df/ 2018-12-20T12:40:17+00:00 https://arxiv.org/abs/1309.3441 Vaguery strings combinatorics enumeration pattern-discovery complexity-measures information-theory rather-interesting to-write-about for-puzzles you-know-for-kids https://pinboard.in/ https://pinboard.in/u:Vaguery/b:609accd48e8f/ 2018-12-17T13:18:25+00:00 https://arxiv.org/abs/1808.06313 Vaguery combinatorics strings rather-interesting counting to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7462352c014a/ 2018-07-04T11:38:52+00:00 https://arxiv.org/abs/1710.10964 Vaguery= 3. We provide approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower- and upper- bounds for the random access problem on string attractors. Our optimal data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, our solution matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access problem for all these compressors.]]> compression strings feature-extraction representation algorithms computational-complexity to-understand nudge-targets consider:looking-to-see https://pinboard.in/ https://pinboard.in/u:Vaguery/b:9b85017a8384/ 2018-01-28T11:52:07+00:00 https://github.com/friemen/diffit Vaguery clojure strings library to-use metrics https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7e1daba044c1/ 2018-01-26T12:16:56+00:00 https://arxiv.org/abs/1709.05725 Vaguery pattern-discovery rather-interesting strings data-mining statistics nudge-targets consider:looking-to-see consider:representation consider:performance-measures https://pinboard.in/ https://pinboard.in/u:Vaguery/b:3b20b6fb4a78/ 2018-01-15T15:11:05+00:00 https://arxiv.org/abs/1712.08573 Vaguery strings computational-complexity algorithms rather-interesting nudge-targets consider:looking-to-see https://pinboard.in/ https://pinboard.in/u:Vaguery/b:fcd81ec25a1e/ 2017-11-27T20:57:46+00:00 https://arxiv.org/abs/1710.03248 Vaguery programming-language to-understand data-structures translation strings to-write-about nudge-targets? https://pinboard.in/ https://pinboard.in/u:Vaguery/b:a853f89f4ece/ 2017-11-17T13:55:31+00:00 https://arxiv.org/abs/1710.03395 Vaguery algorithms strings rather-interesting formal-languages representation rewriting-systems to-write-about consider:rediscovery nudge-targets https://pinboard.in/ https://pinboard.in/u:Vaguery/b:88225bd758af/ 2017-11-17T13:28:50+00:00 https://arxiv.org/abs/1705.01887 Vaguery0, a d-near-palindrome is a string of Hamming distance at most d from its reverse. We study the natural problem of identifying a longest d-near-palindrome in data streams. The problem is relevant to the analysis of DNA databases, and to the task of repairing recursive structures in documents such as XML and JSON. We present an algorithm that returns a d-near-palindrome whose length is within a multiplicative (1+ϵ)-factor of the longest d-near-palindrome. Our algorithm also returns the set of mismatched indices of the d-near-palindrome, using (dlog7nϵlog(1+ϵ)) bits of space, and (dlog6nϵlog(1+ϵ)) update time per arriving symbol. We show that Ω(dlogn) space is necessary for estimating the length of longest d-near-palindromes with high probability. We further obtain an additive-error approximation algorithm and a comparable lower bound, as well as an exact two-pass algorithm that solves the longest d-near-palindrome problem using (d2n‾√log6n) bits of space.]]> strings computational-complexity algorithms probability-theory inference online-learning rather-interesting to-write-about nudge-targets consider:looking-to-see consider:representation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:a55596c193ce/ 2017-11-05T14:24:06+00:00 https://arxiv.org/abs/1406.5895 Vaguery combinatorics strings to-write-about nudge-targets consider:rediscovery consider:performance-measures https://pinboard.in/ https://pinboard.in/u:Vaguery/b:285cfae33bf8/ 2017-11-05T14:01:04+00:00 https://arxiv.org/abs/1108.3615v1 Vaguery combinatorics representation rather-interesting strings tiling to-write-about domino-tiling mathematical-recreations https://pinboard.in/ https://pinboard.in/u:Vaguery/b:28edf3445129/ 2017-11-05T13:59:04+00:00 https://arxiv.org/abs/1701.00948 Vaguery strings combinatorics patterns rather-interesting to-write-about nudge-targets https://pinboard.in/ https://pinboard.in/u:Vaguery/b:232df0bcfdf6/ 2017-10-21T12:45:05+00:00 https://arxiv.org/abs/1512.03421 Vaguery combinatorics to-understand graph-theory strings optimization constraint-satisfaction looking-to-see nudge-targets consider:looking-to-see consider:classification consider:feature-discovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:df76bf4f0e9c/ 2017-10-21T12:37:12+00:00 https://arxiv.org/abs/1502.04644 Vaguery strings proof permutations looking-to-see to-write-about nudge-targets https://pinboard.in/ https://pinboard.in/u:Vaguery/b:fdce8d2bac01/ 2017-10-19T22:40:02+00:00 https://arxiv.org/abs/1406.0670 Vaguery 01 and 1 -> 0. We then recover many results about the Fibonacci word from the literature (and improve some of them), such as assertions about the occurrences in f of squares, cubes, palindromes, and so forth. As an application of our method we prove a new result: there exists an aperiodic infinite binary word avoiding the pattern x x x^R. This is the first avoidability result concerning a nonuniform morphism proven purely mechanically.]]> strings combinatorics classification nudge-targets consider:looking-to-see consider:feature-discovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:b6c028a2d38e/ 2017-10-18T12:28:51+00:00 https://arxiv.org/abs/1407.5841 Vaguery 01, 1 -> 02, 2 -> 0. We use it to reprove some old results about the Tribonacci word from the literature, such as assertions about the occurrences in T of squares, cubes, palindromes, and so forth. We also obtain some new results.]]> formal-languages strings automata representation feature-construction rather-interesting nudge-targets consider:looking-to-see consider:rediscovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:6caa8fac1070/ 2017-10-18T12:24:32+00:00 https://arxiv.org/abs/1505.00667 Vaguery continued-fractions strings number-theory rather-interesting to-understand nudge-targets consider:representation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:dc4cbf1a3da7/ 2017-10-18T12:22:24+00:00 https://arxiv.org/abs/1311.2318 Vaguery strings feature-construction classification nudge-targets consider:looking-to-see https://pinboard.in/ https://pinboard.in/u:Vaguery/b:8a68ae4595ad/ 2017-10-18T12:14:14+00:00 https://arxiv.org/abs/1612.05320 Vaguery strings feature-construction rather-interesting nudge-targets to-write-about consider:rediscovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:8422f600a045/ 2017-10-18T11:58:49+00:00 https://arxiv.org/abs/1509.05240 Vaguery probability-theory strings rather-interesting consider:Benford's-law? to-write-about to-understand https://pinboard.in/ https://pinboard.in/u:Vaguery/b:6d6f29bf1d8a/ 2017-09-28T00:22:18+00:00 https://arxiv.org/abs/1611.01479 Vaguery strings compression algorithms rather-interesting to-write-about discrete-mathematics computational-complexity nudge-targets consider:rediscovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:8345d8e06667/ 2017-09-28T00:19:45+00:00 https://arxiv.org/abs/1709.05314 Vaguery strings compression discrete-mathematics rather-interesting feature-construction to-write-about data-structures nudge-targets consider:looking-to-see combinatorics https://pinboard.in/ https://pinboard.in/u:Vaguery/b:82fe4afe6e07/ 2017-09-26T14:58:46+00:00 https://arxiv.org/abs/1709.02034 Vaguery strings pattern-discovery computational-complexity algorithms rather-interesting nudge-targets consider:looking-to-see to-write-about consider:cartooning https://pinboard.in/ https://pinboard.in/u:Vaguery/b:0a1a0ee8d2ad/ 2017-04-29T11:52:55+00:00 https://arxiv.org/abs/1604.06707 Vaguery combinatorics generative-models rather-interesting to-write-about permutations strings algorithms nudge-targets consider:rediscovery consider:variations https://pinboard.in/ https://pinboard.in/u:Vaguery/b:248874a133bc/ 2017-04-21T10:47:53+00:00 https://arxiv.org/abs/1301.5080 Vaguery permutations strings combinatorics counting nudge-targets consider:looking-to-see to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:de22f8b5f8a5/ 2017-04-20T23:07:23+00:00 https://arxiv.org/abs/1102.2480 Vaguery permutations combinatorics strings nudge-targets consider:looking-to-see consider:performance-measures consider:rediscovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:3bdee77d3e15/ 2017-04-19T14:10:21+00:00 https://arxiv.org/abs/1410.7669 Vaguery distributed-processing collective-behavior rather-interesting strings rewriting-systems engineering-design emergent-design nudge-targets consider:looking-to-see to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:d3623531d273/ 2017-04-19T14:03:58+00:00 https://arxiv.org/abs/1108.3620 Vaguery strings rewriting-systems dynamical-systems to-understand fractals to-write-about open-questions nudge-targets consider:performance-measures https://pinboard.in/ https://pinboard.in/u:Vaguery/b:7ecbd167bc80/ 2017-04-19T14:02:29+00:00 https://arxiv.org/abs/1108.5574 Vaguery dynamical-systems discrete-mathematics rewriting-systems to-understand strings representation to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:33f85a6f5cca/ 2017-04-19T14:01:01+00:00 https://arxiv.org/abs/1212.5106 Vaguery strings formal-languages to-understand dynamical-systems substitution-systems rewriting-systems nudge-targets consider:looking-to-see consider:feature-discovery https://pinboard.in/ https://pinboard.in/u:Vaguery/b:77fa865f4605/ 2017-04-18T22:36:51+00:00 https://arxiv.org/abs/1505.00707 Vaguery strings combinatorics set-theory define-your-terms to-write-about substitution-systems consider:recombination consider:genetic-algorithms https://pinboard.in/ https://pinboard.in/u:Vaguery/b:a34f30644758/ 2017-03-22T11:53:42+00:00 https://arxiv.org/abs/1511.02393 Vaguery strings bioinformatics search-algorithms algorithms computational-complexity nudge-targets consider:looking-to-see https://pinboard.in/ https://pinboard.in/u:Vaguery/b:e4f8cfc93713/ 2017-03-05T13:01:43+00:00 https://arxiv.org/abs/1702.07015 Vaguery natural-language-processing word-nets machine-learning unsupervised-learning algorithms rather-interesting to-write-about strings nudge-targets consider:representation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:227a59cae642/ 2017-02-27T12:51:11+00:00 https://arxiv.org/abs/1608.03533 Vaguery edit-distance metrics machine-learning representation rather-interesting to-understand generative-models strings time-series to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:9991719378b8/ 2017-02-11T15:31:11+00:00 https://arxiv.org/abs/1702.00318 Vaguery combinatorics bioinformatics metaheuristics strings rather-interesting nudge-targets consider:looking-to-see consider:representation https://pinboard.in/ https://pinboard.in/u:Vaguery/b:62e2723cdce4/ 2017-01-26T13:56:27+00:00 https://arxiv.org/abs/1701.00928 Vaguery combinatorics formal-languages strings proof algorithms rather-interesting nudge-targets https://pinboard.in/ https://pinboard.in/u:Vaguery/b:d2ab56782c3c/ 2017-01-10T14:39:44+00:00 https://arxiv.org/abs/1611.05537 Vaguery strings metrics edit-distance computational-complexity dynamic-programming nudge-targets consider:looking-to-see consider:robustness to-write-about https://pinboard.in/ https://pinboard.in/u:Vaguery/b:5f4784bd94c1/