https://pinboard.in/u:arsyed/public/ recent bookmarks from arsyed 2019-01-11T20:31:37+00:00 http://proceedings.mlr.press/v75/golowich18a.html arsyed neural-net complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:65ed718b5824/ 2018-11-12T20:12:50+00:00 https://arxiv.org/abs/1805.04908 arsyed nlp rnn complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:cf758803fcf0/ 2018-06-14T21:54:18+00:00 https://rjlipton.wordpress.com/2010/11/07/what-is-a-complexity-class/ arsyedcompsci complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:06fdbe92d5fd/ 2018-06-11T21:28:00+00:00 https://byorgey.wordpress.com/2018/02/28/test-your-intuition-logarithmic-time/ arsyedproblems complexity compsci intuition https://pinboard.in/ https://pinboard.in/u:arsyed/b:92323abe8a20/ 2018-05-29T16:40:26+00:00 https://arxiv.org/abs/1805.07883 arsyed neural-net convnet complexity learning-theory https://pinboard.in/ https://pinboard.in/u:arsyed/b:577820b76e6f/ 2018-04-03T19:35:22+00:00 http://ericbalkanski.com/wp-content/uploads/2018/03/The-Adaptive-Complexity-of-Maximizing-a-Submodular-Function.pdf arsyedsubmodularity complexity adaptive https://pinboard.in/ https://pinboard.in/u:arsyed/b:324d46f3c90c/ 2018-01-04T02:59:26+00:00 https://arxiv.org/abs/1108.1791 arsyed papers philosophy complexity compsci time https://pinboard.in/ https://pinboard.in/u:arsyed/b:c9afa0527d2f/ 2017-07-20T17:50:26+00:00 http://tcs.rwth-aachen.de/~sanchez/slides/Raleigh2014.pdf arsyed complexity compsci https://pinboard.in/ https://pinboard.in/u:arsyed/b:f33d2997a099/ 2017-05-03T03:17:33+00:00 https://www.cs.toronto.edu/~cebly/Papers/BrafmanEtAl_aaai07.pdf arsyedpapers subset-selection complexity preference https://pinboard.in/ https://pinboard.in/u:arsyed/b:c7ce78d0e659/ 2017-01-24T20:58:38+00:00 https://www.oreilly.com/ideas/the-hard-thing-about-deep-learning arsyedneural-net optimization complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:a32fb42fbe70/ 2016-11-06T14:26:52+00:00 https://www.quora.com/In-deep-learning-why-dont-we-use-the-whole-training-set-to-compute-the-gradient arsyed neural-net optimization gradient-descent sgd complexity mini-batch https://pinboard.in/ https://pinboard.in/u:arsyed/b:4433551120ad/ 2016-07-20T06:45:52+00:00 http://arxiv.org/abs/1405.4980 arsyed papers optimization convex algorithms complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:753ce99ce11b/ 2015-11-17T04:33:28+00:00 http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ arsyedalgorithms graph isomorphism complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:1f1c52c37b6b/ 2015-07-01T22:14:42+00:00 http://arxiv.org/abs/1304.4948 arsyed papers algorithms approximation complexity submodularity https://pinboard.in/ https://pinboard.in/u:arsyed/b:e9c9072ac807/ 2015-04-10T13:18:24+00:00 http://arxiv.org/abs/1502.01063 arsyed0, unless the Strong Exponential Time Hypothesis fails. We generalize the result to edit distance for arbitrary fixed costs of the four operations (deletion in one of the two strings, matching, substitution), by identifying trivial cases that can be solved in constant time, and proving quadratic-time hardness on binary strings for all other cost choices. This improves and generalizes the known hardness result for Levenshtein distance [Backurs, Indyk STOC'15] by the restriction to binary strings and the generalization to arbitrary costs, and adds important problems to a recent line of research showing conditional lower bounds for a growing number of quadratic time problems. As our main technical contribution, we introduce a framework for proving quadratic-time hardness of similarity measures. To apply the framework it suffices to construct a single gadget, which encapsulates all the expressive power necessary to emulate a reduction from satisfiability. Finally, we prove quadratic-time hardness for longest palindromic subsequence and longest tandem subsequence via reductions from longest common subsequence, showing that conditional lower bounds based on the Strong Exponential Time Hypothesis also apply to string problems that are not necessarily similarity measures. ]]> papers strings algorithms dtw alignment similarity visualization complexity bounds lower-bound via:Vaguery https://pinboard.in/u:arsyed/b:dd6cdfab8fc5/ 2015-02-14T18:37:26+00:00 http://arxiv.org/abs/1003.0516 arsyed papers statistics model-selection complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:d2625f9e7f90/ 2015-02-14T18:36:09+00:00 http://arxiv.org/abs/math/0702804 arsyed papers statistics model-selection complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:dc7ea5e96301/ 2014-05-20T15:54:42+00:00 http://arxiv.org/abs/1111.0952 arsyedsanjeev-arora arxiv research-article nmf linear-algebra optimization machinelearning computerscience complexity via:arthegall https://pinboard.in/u:arsyed/b:b0dc18cbf7d5/ 2014-03-10T16:02:02+00:00 http://link.springer.com/article/10.1007/s10618-013-0312-3 arsyed papers classification time-series distance complexity .se https://pinboard.in/ https://pinboard.in/u:arsyed/b:0b75b69ec9ce/ 2013-11-04T10:08:39+00:00 http://arxiv.org/abs/cs.DS/0111050 arsyed papers algorithms simplex complexity optimization linear-programming https://pinboard.in/ https://pinboard.in/u:arsyed/b:e460a51b6472/ 2013-10-23T04:30:40+00:00 http://stochastix.wordpress.com/2012/12/22/sipser-on-p-versus-np/ arsyedcomplexity talks videos .watch https://pinboard.in/ https://pinboard.in/u:arsyed/b:457cd4530ebb/ 2013-10-05T19:39:12+00:00 http://java-srv1.mpi-cbg.de/publications/getDocument.html?id=ff8080812daff75c012dc1b7bc10000c arsyedfunny von-neumann models complexity parameters https://pinboard.in/ https://pinboard.in/u:arsyed/b:de5a1f0ba72f/ 2013-09-05T22:28:15+00:00 https://blogs.princeton.edu/imabandit/orf523-the-complexities-of-optimization/ arsyednotes courses optimization machine-learning complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:93130ee8dfa0/ 2013-07-28T21:52:07+00:00 http://valis.cs.uiuc.edu/~sariel/papers/03/lloyd_kmeans/kmeans.pdf arsyed papers k-means clustering complexity algorithms https://pinboard.in/ https://pinboard.in/u:arsyed/b:1586501ed98b/ 2013-06-15T14:38:01+00:00 https://complexityzoo.uwaterloo.ca/Complexity_Zoo arsyedref wikis complexity algorithms https://pinboard.in/ https://pinboard.in/u:arsyed/b:0656fd5e1e97/ 2013-06-03T04:43:42+00:00 http://icr.uni.lu/srdjan.vesic/2012_JELIA_F.pdf arsyedpapers argumentation complexity epistemic-logic logic belief belief-revision https://pinboard.in/ https://pinboard.in/u:arsyed/b:9d3d8a2407b8/ 2013-05-28T22:07:37+00:00 http://arxiv.org/abs/1304.0828 arsyed algorithms complexity statcomp machine-learning pca sparsity sparse-pca papers https://pinboard.in/ https://pinboard.in/u:arsyed/b:a77fe105ca59/ 2013-05-28T18:33:16+00:00 http://www0.cs.ucl.ac.uk/staff/a.hunter/papers/aga.pdf arsyed papers argumentation kb construction complexity algorithms https://pinboard.in/ https://pinboard.in/u:arsyed/b:77524a2be177/ 2013-05-28T18:30:16+00:00 http://www.lamsade.dauphine.fr/scripts/FILES/publi1754.pdf arsyed argumentation vaf algorithms complexity graph-theory tree decomposition papers https://pinboard.in/ https://pinboard.in/u:arsyed/b:9c0738f11323/ 2013-05-28T18:27:32+00:00 http://arxiv.org/abs/1104.4290 arsyed argumentation algorithms complexity papers https://pinboard.in/ https://pinboard.in/u:arsyed/b:a397b2136d5b/ 2013-05-28T15:48:50+00:00 http://link.springer.com/chapter/10.1007%2F978-0-387-98197-0_5 arsyed papers complexity argumentation acceptance algorithms https://pinboard.in/ https://pinboard.in/u:arsyed/b:f4277e426dcf/ 2013-05-28T15:42:43+00:00 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.1883 arsyed papers argumentation complexity graph-theory acceptance https://pinboard.in/ https://pinboard.in/u:arsyed/b:823845dcc96a/ 2013-05-28T15:39:41+00:00 http://homepage.univie.ac.at/wolfgang.dvorak/files/argcomp.pdf arsyed papers argumentation complexity semantics acceptance https://pinboard.in/ https://pinboard.in/u:arsyed/b:218a8e84dd9a/ 2013-05-25T22:52:56+00:00 http://yinwang0.wordpress.com/2013/04/02/indexing/ arsyedcomplexity indexing search binary-search https://pinboard.in/ https://pinboard.in/u:arsyed/b:3a6cd02e2e99/ 2013-05-24T13:08:47+00:00 http://metaoptimize.com/qa/questions/1201/probability-prediction-with-supervised-learning-simple-methods arsyed svm regularization logistic-regression margin complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:960330ad7797/ 2013-05-06T16:51:34+00:00 http://bigocheatsheet.com/ arsyed algorithms via:mcherm ref cheat-sheets complexity big-oh https://pinboard.in/u:arsyed/b:a83b61a461a5/ 2013-04-30T05:08:29+00:00 http://shaffner.us/cs/papers/tarpit.pdf arsyed swdev programming complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:5172a706a3a9/ 2013-03-04T05:03:05+00:00 http://www.quora.com/For-those-who-have-used-neural-networks-or-other-machine-learning-how-much-processing-time-has-it-taken-to-train-them-and-how-large-was-the-dataset arsyed deep-learning neural-net complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:11e9eec1a728/ 2013-01-23T00:55:20+00:00 http://www.machinedlearnings.com/2012/12/do-you-really-have-big-data.html arsyed machine-learning complexity scaling big-data trade-offs https://pinboard.in/ https://pinboard.in/u:arsyed/b:1ae913ce6121/ 2012-12-28T06:34:34+00:00 http://www.stat.berkeley.edu/~bartlett/talks/201207-MMDS.pdf arsyedstatistics model-selection complexity learning-theory via:cshalizi via:arthegall https://pinboard.in/u:arsyed/b:61fe05ec0721/ 2012-10-31T21:35:11+00:00 http://www.santafe.edu/news/item/announce-mooc/ arsyed courses complexity santa-fe-institute via:nelson https://pinboard.in/ https://pinboard.in/u:arsyed/b:acf65ebdfef2/ 2012-09-22T16:54:12+00:00 http://masi.cscs.lsa.umich.edu/~crshalizi/reviews/nature-of-computation.html arsyed books rec computation complexity reviews https://pinboard.in/ https://pinboard.in/u:arsyed/b:2b971cf9cd5f/ 2012-07-09T21:41:32+00:00 http://discrete.gr/complexity/ arsyedalgorithms complexity https://pinboard.in/ https://pinboard.in/u:arsyed/b:386debd5c02f/ 2012-05-26T17:22:05+00:00 http://www.johndcook.com/blog/2012/05/25/unix-doesnt-follow-the-unix-philosophy/ arsyed unix design complexity simplicity https://pinboard.in/ https://pinboard.in/u:arsyed/b:f97d48a97ef9/ 2011-12-20T05:49:54+00:00 http://exploringcomplexity.blogspot.com/2011/12/discussion-of-thecommon-patterns-of.html arsyed science complexity statistics information-theory maxent https://pinboard.in/ https://pinboard.in/u:arsyed/b:705e733cd609/ 2011-12-08T05:36:26+00:00 http://exploringcomplexity.blogspot.com/2011/11/we-need-to-talk-about-scaling.html arsyed complexity scaling power-law via:cshalizi https://pinboard.in/ https://pinboard.in/u:arsyed/b:08c9a2dc1a93/ 2011-08-15T04:44:12+00:00 http://www.nature-of-computation.org/ arsyed books computation complexity via:vaguery .want https://pinboard.in/u:arsyed/b:ac0835c8f5b3/ 2011-06-19T16:08:36+00:00 http://homepages.cwi.nl/~paulv/learning.html arsyedpapers information-theory statistics complexity machine-learning https://pinboard.in/ https://pinboard.in/u:arsyed/b:271a1da235f2/ 2011-06-11T17:35:46+00:00 http://www.amazon.com/Favorite-Computational-Complexity-Books/lm/22R1UX0Y9YRT2/ref=cm_lm_byauthor_title_full arsyedbooks compsci complexity computing rec lance-fortnow https://pinboard.in/ https://pinboard.in/u:arsyed/b:66af2eaad7c6/ 2011-06-10T18:21:16+00:00 http://www.scottaaronson.com/democritus/lec15.html arsyedlearning-theory complexity .read https://pinboard.in/ https://pinboard.in/u:arsyed/b:352e28f3245c/ 2010-12-23T21:45:39+00:00 http://www.stephenjaygould.org/library/shermer_contingency.html arsyed evolution adaptation contingency history complexity daniel-dennet stephen-jay-gould https://pinboard.in/ https://pinboard.in/u:arsyed/b:28004c85130b/ 2010-12-02T16:30:06+00:00 http://web.cecs.pdx.edu/~mm/ arsyedpeople complexity books rec https://pinboard.in/u:arsyed/b:acb0aa44d564/ 2010-11-27T02:47:36+00:00 http://rjlipton.wordpress.com/2009/05/06/worst-case-complexity/ arsyedcompsci complexity worst-case information-theory https://pinboard.in/u:arsyed/b:099473844b64/ 2010-09-23T20:40:31+00:00 http://stats.stackexchange.com/questions/2828/measures-of-model-complexity arsyedstatistics model-selection cross-validation gdf complexity https://pinboard.in/u:arsyed/b:872907fe3456/ 2010-09-06T20:19:12+00:00 http://rjlipton.wordpress.com/2010/08/19/projections-can-be-tricky/ arsyedcompsci complexity algorithms projections math https://pinboard.in/u:arsyed/b:a040c17c0f9c/ 2010-09-04T20:42:07+00:00 http://mathoverflow.net/questions/37518/why-do-statistical-randomness-tests-seem-so-ad-hoc arsyedstatistics randomness complexity https://pinboard.in/u:arsyed/b:e44e00628e43/ 2010-08-16T23:20:22+00:00 http://www.eccc.uni-trier.de/report/2010/128/ arsyed compsci complexity sampling search https://pinboard.in/u:arsyed/b:a1f2e370397a/ 2010-08-15T21:08:24+00:00 http://gowers.wordpress.com/2009/09/22/a-conversation-about-complexity-lower-bounds/ arsyedcompsci complexity via:arthegall read https://pinboard.in/u:arsyed/b:7ba761f62285/ 2010-07-07T09:47:04+00:00 http://rjlipton.wordpress.com/2010/06/26/stating-pnp-without-turing-machines/ arsyedcomputation complexity p=np integer linear programming math https://pinboard.in/u:arsyed/b:2a9cd6052187/ 2010-04-03T02:05:30+00:00 http://www.shirky.com/weblog/2010/04/the-collapse-of-complex-business-models/ arsyed business media internet complexity sociology history clay-shirky https://pinboard.in/u:arsyed/b:9c8e97034b10/ 2010-01-14T02:47:36+00:00 http://rjlipton.wordpress.com/2010/01/12/a-course-on-complexity-theorem/ arsyedcompsci complexity https://pinboard.in/u:arsyed/b:7bd001b3f4c8/ 2009-10-07T05:20:19+00:00 http://backreaction.blogspot.com/2008/03/book-review-complex-adaptive-systems-by.html arsyedbooks reviews complexity adaptive modeling social agents https://pinboard.in/u:arsyed/b:9de8f4db8b5b/ 2009-08-05T19:29:49+00:00 http://hunch.net/~jl/projects/prediction_bounds/thesis/mathml/thesis.xml arsyed machine-learning theory complexity boundsd https://pinboard.in/u:arsyed/b:e9bff23fded0/ 2009-08-04T05:38:07+00:00 http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-and-multiple-choice-exams/ arsyedmath compsci complexity p=np https://pinboard.in/u:arsyed/b:13470438e1b4/ 2009-07-12T20:15:49+00:00 http://wiki.python.org/moin/TimeComplexity arsyed python ref algorithms internals complexity https://pinboard.in/u:arsyed/b:862ea7c0ff0f/ 2009-07-01T14:29:29+00:00 http://complexityblog.com/nucleus/index.php arsyedblogs complexity https://pinboard.in/u:arsyed/b:3b759209cb72/ 2009-06-20T10:24:14+00:00 http://blog.computationalcomplexity.org/2009/05/foundations-of-complexity.html arsyedcompsci complexity read https://pinboard.in/u:arsyed/b:b91818bead30/ 2009-06-20T10:22:22+00:00 http://blog.computationalcomplexity.org/2006/12/favorite-theorems-second-decade-recap.html arsyedcompsci complexity theorems read https://pinboard.in/u:arsyed/b:bf7661d62187/ 2009-05-28T02:06:01+00:00 http://yalepress.yale.edu/yupbooks/book.asp?isbn=9780300141733 arsyedbooks rec biology computation complexity https://pinboard.in/u:arsyed/b:135eb5542a8e/ 2009-05-13T02:09:03+00:00 http://oscarbonilla.com/2008/11/simple-guide-to-complexity-theory/ arsyedcompsci complexity np https://pinboard.in/u:arsyed/b:6059c707ab5a/