@article{849,
  abstract     = {Understanding the principles that led to the current complexity of the genetic code is a central question in evolution. Expansion of the genetic code required the selection of new transfer RNAs (tRNAs) with specific recognition signals that allowed them to be matured, modified, aminoacylated, and processed by the ribosome without compromising the fidelity or efficiency of protein synthesis. We show that saturation of recognition signals blocks the emergence of new tRNA identities and that the rate of nucleotide substitutions in tRNAs is higher in species with fewer tRNA genes. We propose that the growth of the genetic code stalled because a limit was reached in the number of identity elements that can be effectively used in the tRNA structure.},
  author       = {Saint-Léger, Adélaïde and Bello, Carla and Dans, Pablo D and Torres, Adrian G and Novoa, Eva M and Camacho, Noelia and Orozco, Modesto and Fyodor Kondrashov and Ribas De Pouplana, Lluís},
  journal      = {Science advances},
  number       = {4},
  pages        = {e1501860 -- e1501860},
  publisher    = {American Association for the Advancement of Science},
  title        = {{Saturation of recognition elements blocks evolution of new tRNA identities}},
  doi          = {10.1126/sciadv.1501860},
  volume       = {2},
  year         = {2016},
}

@article{8493,
  abstract     = {In this paper we study a so-called separatrix map introduced by Zaslavskii–Filonenko (Sov Phys JETP 27:851–857, 1968) and studied by Treschev (Physica D 116(1–2):21–43, 1998; J Nonlinear Sci 12(1):27–58, 2002), Piftankin (Nonlinearity (19):2617–2644, 2006) Piftankin and Treshchëv (Uspekhi Mat Nauk 62(2(374)):3–108, 2007). We derive a second order expansion of this map for trigonometric perturbations. In Castejon et al. (Random iteration of maps of a cylinder and diffusive behavior. Preprint available at arXiv:1501.03319, 2015), Guardia and Kaloshin (Stochastic diffusive behavior through big gaps in a priori unstable systems (in preparation), 2015), and Kaloshin et al. (Normally Hyperbolic Invariant Laminations and diffusive behavior for the generalized Arnold example away from resonances. Preprint available at http://www.terpconnect.umd.edu/vkaloshi/, 2015), applying the results of the present paper, we describe a class of nearly integrable deterministic systems with stochastic diffusive behavior.},
  author       = {Guardia, M. and Kaloshin, Vadim and Zhang, J.},
  issn         = {0010-3616},
  journal      = {Communications in Mathematical Physics},
  pages        = {321--361},
  publisher    = {Springer Nature},
  title        = {{A second order expansion of the separatrix map for trigonometric perturbations of a priori unstable systems}},
  doi          = {10.1007/s00220-016-2705-9},
  volume       = {348},
  year         = {2016},
}

@article{8494,
  abstract     = {We prove a form of Arnold diffusion in the a-priori stable case. Let
H0(p)+ϵH1(θ,p,t),θ∈Tn,p∈Bn,t∈T=R/T,
be a nearly integrable system of arbitrary degrees of freedom n⩾2 with a strictly convex H0. We show that for a “generic” ϵH1, there exists an orbit (θ,p) satisfying
∥p(t)−p(0)∥>l(H1)>0,
where l(H1) is independent of ϵ. The diffusion orbit travels along a codimension-1 resonance, and the only obstruction to our construction is a finite set of additional resonances.

For the proof we use a combination of geometric and variational methods, and manage to adapt tools which have recently been developed in the a-priori unstable case.},
  author       = {Bernard, Patrick and Kaloshin, Vadim and Zhang, Ke},
  issn         = {0001-5962},
  journal      = {Acta Mathematica},
  number       = {1},
  pages        = {1--79},
  publisher    = {Institut Mittag-Leffler},
  title        = {{Arnold diffusion in arbitrary degrees of freedom and normally hyperbolic invariant cylinders}},
  doi          = {10.1007/s11511-016-0141-5},
  volume       = {217},
  year         = {2016},
}

@article{8496,
  author       = {Avila, Artur and De Simoi, Jacopo and Kaloshin, Vadim},
  issn         = {0003-486X},
  journal      = {Annals of Mathematics},
  number       = {2},
  pages        = {527--558},
  publisher    = {Princeton University Press},
  title        = {{An integrable deformation of an ellipse of small eccentricity is an ellipse}},
  doi          = {10.4007/annals.2016.184.2.5},
  volume       = {184},
  year         = {2016},
}

@article{8497,
  abstract     = {We study the dynamics of the restricted planar three-body problem near mean motion resonances, i.e. a resonance involving the Keplerian periods of the two lighter bodies revolving around the most massive one. This problem is often used to model Sun–Jupiter–asteroid systems. For the primaries (Sun and Jupiter), we pick a realistic mass ratio μ=10−3 and a small eccentricity e0>0. The main result is a construction of a variety of non local diffusing orbits which show a drastic change of the osculating (instant) eccentricity of the asteroid, while the osculating semi major axis is kept almost constant. The proof relies on the careful analysis of the circular problem, which has a hyperbolic structure, but for which diffusion is prevented by KAM tori. In the proof we verify certain non-degeneracy conditions numerically.

Based on the work of Treschev, it is natural to conjecture that the time of diffusion for this problem is ∼−ln(μe0)μ3/2e0. We expect our instability mechanism to apply to realistic values of e0 and we give heuristic arguments in its favor. If so, the applicability of Nekhoroshev theory to the three-body problem as well as the long time stability become questionable.

It is well known that, in the Asteroid Belt, located between the orbits of Mars and Jupiter, the distribution of asteroids has the so-called Kirkwood gaps exactly at mean motion resonances of low order. Our mechanism gives a possible explanation of their existence. To relate the existence of Kirkwood gaps with Arnol'd diffusion, we also state a conjecture on its existence for a typical ϵ-perturbation of the product of the pendulum and the rotator. Namely, we predict that a positive conditional measure of initial conditions concentrated in the main resonance exhibits Arnol’d diffusion on time scales −lnϵϵ2.},
  author       = {Féjoz, Jacques and Guàrdia, Marcel and Kaloshin, Vadim and Roldán, Pablo},
  issn         = {1435-9855},
  journal      = {Journal of the European Mathematical Society},
  number       = {10},
  pages        = {2315--2403},
  publisher    = {European Mathematical Society Publishing House},
  title        = {{Kirkwood gaps and diffusion along mean motion resonances in the restricted planar three-body problem}},
  doi          = {10.4171/jems/642},
  volume       = {18},
  year         = {2016},
}

@article{850,
  abstract     = {Fitness landscapes depict how genotypes manifest at the phenotypic level and form the basis of our understanding of many areas of biology, yet their properties remain elusive. Previous studies have analysed specific genes, often using their function as a proxy for fitness, experimentally assessing the effect on function of single mutations and their combinations in a specific sequence or in different sequences. However, systematic high-throughput studies of the local fitness landscape of an entire protein have not yet been reported. Here we visualize an extensive region of the local fitness landscape of the green fluorescent protein from Aequorea Victoria (avGFP) by measuring the native function (fluorescence) of tens of thousands of derivative genotypes of avGFP. We show that the fitness landscape of avGFP is narrow, with 3/4 of the derivatives with a single mutation showing reduced fluorescence and half of the derivatives with four mutations being completely non-fluorescent. The narrowness is enhanced by epistasis, which was detected in up to 30% of genotypes with multiple mutations and mostly occurred through the cumulative effect of slightly deleterious mutations causing a threshold-like decrease in protein stability and a concomitant loss of fluorescence. A model of orthologous sequence divergence spanning hundreds of millions of years predicted the extent of epistasis in our data, indicating congruence between the fitness landscape properties at the local and global scales. The characterization of the local fitness landscape of avGFP has important implications for several fields including molecular evolution, population genetics and protein design.},
  author       = {Karen Sarkisyan and Bolotin, Dmitry A and Meer, Margarita V and Usmanova, Dinara R and Mishin, Alexander S and Sharonov, George V and Ivankov, Dmitry N and Bozhanova, Nina G and Baranov, Mikhail S and Soylemez, Onuralp and Bogatyreva, Natalya S and Vlasov, Peter K and Egorov, Evgeny S and Logacheva, Maria D and Kondrashov, Alexey S and Chudakov, Dmitriy M and Putintseva, Ekaterina V and Mamedov, Ilgar Z and Tawfik, Dan S and Lukyanov, Konstantin A and Fyodor Kondrashov},
  journal      = {Nature},
  pages        = {397 -- 401},
  publisher    = {Nature Publishing Group},
  title        = {{Local fitness landscape of the green fluorescent protein}},
  doi          = {10.1038/nature17995},
  volume       = {533},
  year         = {2016},
}

@article{853,
  abstract     = {A comparative analysis of the metagenomes from two 30 000-year-old permafrost samples, one of lake-alluvial origin and the other from late Pleistocene Ice Complex sediments, revealed significant differences within microbial communities. The late Pleistocene Ice Complex sediments (which have been characterized by the absence of methane with lower values of redox potential and Fe2+ content) showed a low abundance of methanogenic archaea and enzymes from both the carbon and nitrogen cycles, but a higher abundance of enzymes associated with the sulfur cycle. The metagenomic and geochemical analyses described in the paper provide evidence that the formation of the sampled late Pleistocene Ice Complex sediments likely took place under much more aerobic conditions than lake-alluvial sediments.},
  author       = {Rivkina, Elizaveta and Petrovskaya, Lada E and Vishnivetskaya, Tatiana A and Krivushin, Kirill V and Shmakova, Lyubov A and Tutukina, Maria and Meyers, Arthur J and Fyodor Kondrashov},
  journal      = {Biogeosciences},
  number       = {7},
  pages        = {2207 -- 2219},
  publisher    = {European Geosciences Union},
  title        = {{Metagenomic analyses of the late Pleistocene permafrost - Additional tools for reconstruction of environmental conditions}},
  doi          = {10.5194/bg-13-2207-2016},
  volume       = {13},
  year         = {2016},
}

@article{896,
  abstract     = {Multicellular eukaryotes have evolved a range of mechanisms for immune recognition. A widespread family involved in innate immunity are the NACHT-domain and leucine-rich-repeat-containing (NLR) proteins.Mammals have small numbers of NLR proteins, whereas in some species, mostly those without adaptive immune systems, NLRs have expanded into very large families.We describe a family of nearly 400NLR proteins encoded in the zebrafish genome. The proteins share a defining overall structure, which arose in fishes after a fusion of the core NLR domains with a B30.2 domain, but can be subdivided into four groups based on their NACHT domains. Gene conversion acting differentially on the NACHT and B30.2 domains has shaped the family and created the groups. Evidence of positive selection in the B30.2 domain indicates that this domain rather than the leucine-rich repeats acts as the pathogen recognition module. In an unusual chromosomal organization, the majority of the genes are located on one chromosome arm, interspersed with other large multigene families, including a new family encoding zinc-finger proteins. The NLR-B30.2 proteins represent a new family with diversity in the specific recognition module that is present in fishes in spite of the parallel existence of an adaptive immune system.},
  author       = {Howe, Kerstin L and Schiffer, Philipp H and Zielinski, Julia G and Wiehe, Thomas H and Laird, Gavin K and Marioni, John C and Soylemez, Onuralp and Fyodor Kondrashov and Leptin, Maria},
  journal      = {Open Biology},
  number       = {4},
  publisher    = {Royal Society, The},
  title        = {{Structure and evolutionary history of a large family of NLR proteins in the zebrafish}},
  doi          = {10.1098/rsob.160009},
  volume       = {6},
  year         = {2016},
}

@article{1616,
  abstract     = {The hippocampus plays a key role in learning and memory. Previous studies suggested that the main types of principal neurons, dentate gyrus granule cells (GCs), CA3 pyramidal neurons, and CA1 pyramidal neurons, differ in their activity pattern, with sparse firing in GCs and more frequent firing in CA3 and CA1 pyramidal neurons. It has been assumed but never shown that such different activity may be caused by differential synaptic excitation. To test this hypothesis, we performed high-resolution whole-cell patch-clamp recordings in anesthetized rats in vivo. In contrast to previous in vitro data, both CA3 and CA1 pyramidal neurons fired action potentials spontaneously, with a frequency of ∼3–6 Hz, whereas GCs were silent. Furthermore, both CA3 and CA1 cells primarily fired in bursts. To determine the underlying mechanisms, we quantitatively assessed the frequency of spontaneous excitatory synaptic input, the passive membrane properties, and the active membrane characteristics. Surprisingly, GCs showed comparable synaptic excitation to CA3 and CA1 cells and the highest ratio of excitation versus hyperpolarizing inhibition. Thus, differential synaptic excitation is not responsible for differences in firing. Moreover, the three types of hippocampal neurons markedly differed in their passive properties. While GCs showed the most negative membrane potential, CA3 pyramidal neurons had the highest input resistance and the slowest membrane time constant. The three types of neurons also differed in the active membrane characteristics. GCs showed the highest action potential threshold, but displayed the largest gain of the input-output curves. In conclusion, our results reveal that differential firing of the three main types of hippocampal principal neurons in vivo is not primarily caused by differences in the characteristics of the synaptic input, but by the distinct properties of synaptic integration and input-output transformation.},
  author       = {Kowalski, Janina and Gan, Jian and Jonas, Peter M and Pernia-Andrade, Alejandro},
  issn         = {1098-1063},
  journal      = {Hippocampus},
  number       = {5},
  pages        = {668 -- 682},
  publisher    = {Wiley},
  title        = {{Intrinsic membrane properties determine hippocampal differential firing pattern in vivo in anesthetized rats}},
  doi          = {10.1002/hipo.22550},
  volume       = {26},
  year         = {2016},
}

@article{1617,
  abstract     = {We study the discrepancy of jittered sampling sets: such a set P⊂ [0,1]d is generated for fixed m∈ℕ by partitioning [0,1]d into md axis aligned cubes of equal measure and placing a random point inside each of the N=md cubes. We prove that, for N sufficiently large, 1/10 d/N1/2+1/2d ≤EDN∗(P)≤ √d(log N) 1/2/N1/2+1/2d, where the upper bound with an unspecified constant Cd was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in N. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime N≳dd. We also prove a partition principle showing that every partition of [0,1]d combined with a jittered sampling construction gives rise to a set whose expected squared L2-discrepancy is smaller than that of purely random points.},
  author       = {Pausinger, Florian and Steinerberger, Stefan},
  journal      = {Journal of Complexity},
  pages        = {199 -- 216},
  publisher    = {Academic Press},
  title        = {{On the discrepancy of jittered sampling}},
  doi          = {10.1016/j.jco.2015.11.003},
  volume       = {33},
  year         = {2016},
}

@article{1620,
  abstract     = {We consider the Bardeen–Cooper–Schrieffer free energy functional for particles interacting via a two-body potential on a microscopic scale and in the presence of weak external fields varying on a macroscopic scale. We study the influence of the external fields on the critical temperature. We show that in the limit where the ratio between the microscopic and macroscopic scale tends to zero, the next to leading order of the critical temperature is determined by the lowest eigenvalue of the linearization of the Ginzburg–Landau equation.},
  author       = {Frank, Rupert and Hainzl, Christian and Seiringer, Robert and Solovej, Jan},
  journal      = {Communications in Mathematical Physics},
  number       = {1},
  pages        = {189 -- 216},
  publisher    = {Springer},
  title        = {{The external field dependence of the BCS critical temperature}},
  doi          = {10.1007/s00220-015-2526-2},
  volume       = {342},
  year         = {2016},
}

@article{1622,
  abstract     = {We prove analogues of the Lieb–Thirring and Hardy–Lieb–Thirring inequalities for many-body quantum systems with fractional kinetic operators and homogeneous interaction potentials, where no anti-symmetry on the wave functions is assumed. These many-body inequalities imply interesting one-body interpolation inequalities, and we show that the corresponding one- and many-body inequalities are actually equivalent in certain cases.},
  author       = {Lundholm, Douglas and Nam, Phan and Portmann, Fabian},
  journal      = {Archive for Rational Mechanics and Analysis},
  number       = {3},
  pages        = {1343 -- 1382},
  publisher    = {Springer},
  title        = {{Fractional Hardy–Lieb–Thirring and related Inequalities for interacting systems}},
  doi          = {10.1007/s00205-015-0923-5},
  volume       = {219},
  year         = {2016},
}

@article{1631,
  abstract     = {Ancestral processes are fundamental to modern population genetics and spatial structure has been the subject of intense interest for many years. Despite this interest, almost nothing is known about the distribution of the locations of pedigree or genetic ancestors. Using both spatially continuous and stepping-stone models, we show that the distribution of pedigree ancestors approaches a travelling wave, for which we develop two alternative approximations. The speed and width of the wave are sensitive to the local details of the model. After a short time, genetic ancestors spread far more slowly than pedigree ancestors, ultimately diffusing out with radius ## rather than spreading at constant speed. In contrast to the wave of pedigree ancestors, the spread of genetic ancestry is insensitive to the local details of the models.},
  author       = {Kelleher, Jerome and Etheridge, Alison and Véber, Amandine and Barton, Nicholas H},
  journal      = {Theoretical Population Biology},
  pages        = {1 -- 12},
  publisher    = {Academic Press},
  title        = {{Spread of pedigree versus genetic ancestry in spatially distributed populations}},
  doi          = {10.1016/j.tpb.2015.10.008},
  volume       = {108},
  year         = {2016},
}

@article{1641,
  abstract     = {The plant hormone auxin (indole-3-acetic acid) is a major regulator of plant growth and development including embryo and root patterning, lateral organ formation and growth responses to environmental stimuli. Auxin is directionally transported from cell to cell by the action of specific auxin influx [AUXIN-RESISTANT1 (AUX1)] and efflux [PIN-FORMED (PIN)] transport regulators, whose polar, subcellular localizations are aligned with the direction of the auxin flow. Auxin itself regulates its own transport by modulation of the expression and subcellular localization of the auxin transporters. Increased auxin levels promote the transcription of PIN2 and AUX1 genes as well as stabilize PIN proteins at the plasma membrane, whereas prolonged auxin exposure increases the turnover of PIN proteins and their degradation in the vacuole. In this study, we applied a forward genetic approach, to identify molecular components playing a role in the auxin-mediated degradation. We generated EMS-mutagenized Arabidopsis PIN2::PIN2:GFP, AUX1::AUX1:YFP eir1aux1 populations and designed a screen for mutants with persistently strong fluorescent signals of the tagged PIN2 and AUX1 after prolonged treatment with the synthetic auxin 2,4-dichlorophenoxyacetic acid (2,4-D). This approach yielded novel auxin degradation mutants defective in trafficking and degradation of PIN2 and AUX1 proteins and established a role for auxin-mediated degradation in plant development.},
  author       = {Zemová, Radka and Zwiewka, Marta and Bielach, Agnieszka and Robert, Hélène and Friml, Jirí},
  journal      = {Journal of Plant Growth Regulation},
  number       = {2},
  pages        = {465 -- 476},
  publisher    = {Springer},
  title        = {{A forward genetic screen for new regulators of auxin mediated degradation of auxin transport proteins in Arabidopsis thaliana}},
  doi          = {10.1007/s00344-015-9553-2},
  volume       = {35},
  year         = {2016},
}

@inproceedings{1653,
  abstract     = {A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO).

The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.},
  author       = {Okamoto, Tatsuaki and Pietrzak, Krzysztof Z and Waters, Brent and Wichs, Daniel},
  location     = {Auckland, New Zealand},
  pages        = {121 -- 145},
  publisher    = {Springer},
  title        = {{New realizations of somewhere statistically binding hashing and positional accumulators}},
  doi          = {10.1007/978-3-662-48797-6_6},
  volume       = {9452},
  year         = {2016},
}

@article{1662,
  abstract     = {We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.},
  author       = {Edelsbrunner, Herbert and Pausinger, Florian},
  journal      = {Advances in Mathematics},
  pages        = {674 -- 703},
  publisher    = {Academic Press},
  title        = {{Approximation and convergence of the intrinsic volume}},
  doi          = {10.1016/j.aim.2015.10.004},
  volume       = {287},
  year         = {2016},
}

@article{1705,
  abstract     = {Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.},
  author       = {Bogomolov, Sergiy and Donzé, Alexandre and Frehse, Goran and Grosu, Radu and Johnson, Taylor and Ladan, Hamed and Podelski, Andreas and Wehrle, Martin},
  journal      = {International Journal on Software Tools for Technology Transfer},
  number       = {4},
  pages        = {449 -- 467},
  publisher    = {Springer},
  title        = {{Guided search for hybrid systems based on coarse-grained space abstractions}},
  doi          = {10.1007/s10009-015-0393-y},
  volume       = {18},
  year         = {2016},
}

@inproceedings{1707,
  abstract     = {Volunteer supporters play an important role in modern crisis and disaster management. In the times of mobile Internet devices, help from thousands of volunteers can be requested within a short time span, thus relieving professional helpers from minor chores or geographically spread-out tasks. However, the simultaneous availability of many volunteers also poses new problems. In particular, the volunteer efforts must be well coordinated, or otherwise situations might emerge in which too many idle volunteers at one location become more of a burden than a relief to the professionals.
In this work, we study the task of optimally assigning volunteers to selected locations, e.g. in order to perform regular measurements, to report on damage, or to distribute information or resources to the population in a crisis situation. We formulate the assignment tasks as an optimization problem and propose an effective and efficient solution procedure. Experiments on real data of the Team Österreich, consisting of over 36,000 Austrian volunteers, show the effectiveness and efficiency of our approach.},
  author       = {Pielorz, Jasmin and Lampert, Christoph},
  location     = {Rennes, France},
  publisher    = {IEEE},
  title        = {{Optimal geospatial allocation of volunteers for crisis management}},
  doi          = {10.1109/ICT-DM.2015.7402041},
  year         = {2016},
}

@article{173,
  abstract     = {We calculate admissible values of r such that a square-free polynomial with integer coefficients, no fixed prime divisor and irreducible factors of degree at most 3 takes infinitely many values that are a product of at most r distinct primes.},
  author       = {Browning, Timothy D and Booker, Andrew},
  journal      = {Discrete Analysis},
  pages        = {1 -- 18},
  title        = {{Square-free values of reducible polynomials}},
  doi          = {10.19086/da.732},
  volume       = {8},
  year         = {2016},
}

@article{1794,
  abstract     = {We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.},
  author       = {Kolmogorov, Vladimir and Takhanov, Rustem},
  journal      = {Algorithmica},
  number       = {1},
  pages        = {17 -- 46},
  publisher    = {Springer},
  title        = {{Inference algorithms for pattern-based CRFs on sequence data}},
  doi          = {10.1007/s00453-015-0017-7},
  volume       = {76},
  year         = {2016},
}