• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 145
Sort:
by name
by year
Working paper
Baklanov A., Garimidi P., Gkatzelis V. et al. arxiv.org. Computer Science. Cornell University, 2020
Added: Oct 22, 2020
Working paper
Zlotnik A., Čiegis R. math. arxive. Cornell University, 2020. No. 2012.01000 [math.NA].
We study necessary conditions for stability of a Numerov-type compact higher-order finite-diffe\-rence scheme for the 1D homogeneous wave equation in the case of non-uniform spatial meshes. We first show that the uniform in time stability cannot be valid in any spatial norm provided that the complex eigenvalues appear in the associated mesh eigenvalue problem. Moreover, we prove that then the solution norm grows exponentially in time making the scheme strongly non-dissipative and therefore impractical. Numerical results confirm this conclusion. In addition, for some sequences of refining spatial meshes, an excessively strong condition between steps in time and space is necessary (even for the non-uniform in time stability) which is familiar for explicit schemes in the parabolic case.
Added: Dec 3, 2020
Working paper
Sawada T. Psychology. PSY. Высшая школа экономики, 2019
It is commonly believed that the visual system requires oculomotor information to perceive depth from binocular disparity. However, any effect of the oculomotor information on depth perception is too restricted to explain depth perception under natural viewing conditions. In this study, I describe a computational model that can recover depth from a stereo-pair of retinal images without using any oculomotor information. The model shows that, at least from a computational perspective, any oculomotor information is not necessary for perceiving depth from the stereo retinal images.
Added: Apr 20, 2019
Working paper
Ivanova A., Стонякин Ф., Пасечнюк Д. et al. Optimization and Control. Working papers by Cornell University., 2019
Network utility maximization is the most important problem in network traffic management. Given the growth of modern communication networks, we consider the utility maximization problem in a network with a large number of connections (links) that are used by a huge number of users. To solve this problem an adaptive mirror descent algorithm for many constraints is proposed. The key feature of the algorithm is that it has a dimension-free convergence rate. The convergence of the proposed scheme is proved theoretically. The theoretical analysis is verified with numerical simulations. We compare the algorithm with another approach, using the ellipsoid method (EM) for the dual problem. Numerical experiments showed that the performance of the proposed algorithm against EM is significantly better in large networks and when very high solution accuracy is not required. Our approach can be used in many network design paradigms, in particular, in software-defined networks.
Added: Oct 25, 2020
Working paper
Vereshchagin N. arxiv.org. math. Cornell University, 2020
We consider tilings of the plane by two prototiles which are right triangles. They are called the small and the large tiles. The small tile is similar to the large tile with some similarity coefficient ψ. The large tile can be cut into two pieces so that one piece is a small tile and the other one is similar to the small tile with the same similarity coefficient ψ. Using this cut we define in a standard way the substitution scheme, in which the large tile is replaced by a large and a small tile and the small tile is replaced by a large tile. To every substitution of this kind, there corresponds a family of the so-called substitution tilings of the plane in the sense of [C. Goodman-Strauss, Matching Rules and Substitution Tilings, Annals of Mathematics 147 (1998) 181-223]. All tilings in this family are non-periodic. It was shown in the paper [N. Vereshchagin. Aperiodic Tilings by Right Triangles. In: Proc. of DCFS 2014, LNCS vol. 8614 (2014) 29--41] that this family of substitution tilings is not an SFT. This means that looking at a given tiling trough a bounded window, we cannot determine whether that tiling belongs to the family or not, however large the size of the window is. In the present paper, we prove that this family of substitution tilings is sofic. This means that we can color the prototiles ina finite number of colors and define some local rules for colored prototiles so that the following holds. For any tiling from the family, we can color its tiles so that the resulting tiling (by colored tiles) satisfies local rules. And conversely, for any tiling of the plane satisfying the local rules, by removing colors we obtain a tiling from the family. Besides, the considered substitution can be generalized to colored tiles so that the family of substitution tilings for the resulting substitution coincides with the family of tilings satisfying our local rules.
Added: Jul 24, 2020
Working paper
Bronevich A. Математические методы анализа решений в экономике, бизнесе и политике. WP7. Издательский дом ВШЭ, 2015. No. 1.
Added: Apr 8, 2015
Working paper
Maxim Borisyak, Ustyuzhanin A. arxiv :: cs :: Cornell University. arxiv :: cs :: Cornell University. Cornell University, 2015
The problem of autonomous navigation is one of the basic problems for robotics. Although, in general, it may be challenging when an autonomous vehicle is placed into partially observable domain. In this paper we consider simplistic environment model and introduce a navigation algorithm based on Learning Classifier System.
Added: Nov 9, 2015
Working paper
Russkov A., Roman Chulkevich, Shchur L. math. arxive. Cornell University, 2020. No. 2006.00561.
The parallel annealing method is one of the promising approaches for large scale simulations as potentially scalable on any parallel architecture. We present an implementation of the algorithm on the hybrid program architecture combining CUDA and MPI. The problem is to keep all general-purpose graphics processing unit devices as busy as possible redistributing replicas and to do that efficiently. We provide details of the testing on Intel Skylake/Nvidia V100 based hardware running in parallel more than two million replicas of the Ising model sample. The results are quite optimistic because the acceleration grows toward the perfect line with the growing complexity of the simulated system.
Added: Jun 2, 2020
Working paper
Branzei S., Sandomirskiy F. Computer Science and Game Theory (cs.GT), arXiv:1907.01766. arxiv. Cornell university, 2019
We study the problem of allocating divisible bads (chores) among multiple agents with additive utilities, when money transfers are not allowed. The competitive rule is known to be the best mechanism for goods with additive utilities and was recently extended to chores by Bogomolnaia et al (2017). For both goods and chores, the rule produces Pareto optimal and envy-free allocations. In the case of goods, the outcome of the competitive rule can be easily computed. Competitive allocations solve the Eisenberg-Gale convex program; hence the outcome is unique and can be approximately found by standard gradient methods. An exact algorithm that runs in polynomial time in the number of agents and goods was given by Orlin. In the case of chores, the competitive rule does not solve any convex optimization problem; instead, competitive allocations correspond to local minima, local maxima, and saddle points of the Nash Social Welfare on the Pareto frontier of the set of feasible utilities. The rule becomes multivalued and none of the standard methods can be applied to compute its outcome. In this paper, we show that all the outcomes of the competitive rule for chores can be computed in strongly polynomial time if either the number of agents or the number of chores is fixed. The approach is based on a combination of three ideas: all consumption graphs of Pareto optimal allocations can be listed in polynomial time; for a given consumption graph, a candidate for a competitive allocation can be constructed via explicit formula; and a given allocation can be checked for being competitive using a maximum flow computation as in Devanur et al (2002). Our algorithm immediately gives an approximately-fair allocation of indivisible chores by the rounding technique of Barman and Krishnamurthy (2018).
Added: Sep 24, 2019
Working paper
Subochev A., Zakhlebin I. V. Математические методы анализа решений в экономике, бизнесе и политике. WP7. Издательский дом ВШЭ, 2014. No. 6.
The Competitive Industrial Performance index (developed by experts of the UNIDO) is designed as a measure of national competitiveness. Index is an aggregate of eight observable variables, representing different dimensions of competitive industrial performance. Instead of using a cardinal aggregation function, what CIP’s authors do, it is proposed to apply ordinal ranking methods borrowed from social choice: either direct ranking methods based on the majority relation (e.g. the Copeland rule, the Markovian method) or a multistage procedure of selection and exclusion of the best alternatives, as determined by a majority relation-based social choice solution concept (tournament solution), such as the uncovered set and the minimal externally stable set. The same method of binary comparisons based on the majority rule is used to analyse rank correlations. It is demonstrated that the ranking is robust but some of the new aggregate rankings represent the set of criteria better than the original ranking based on the CIP.
Added: Sep 25, 2014
Working paper
Batsyn M.V., Kalyagin V.A., Tulyakov D. Институт прикладной математики им. М.В. Келдыша Российской академии наук, 2015. No. 91.
The Protein Structure Alignment Problem (PSAP) consists in finding the best alignment of two proteins defined by their primary structures. It finds the most similar substructure of two proteins. This problem is polynomially reducible to the Maximum Clique Problem (MCP) for the protein alignment graph. In this paper we present an efficient algorithm for the PSAP based on our recent ILS&MCS algorithm (Batsyn et al., 2014) for the MCP. To reduce the alignment problem to the MCP we follow the DAST method introduced by Malod-Dognin et al. (2010). Our main contributions include: applying the ILS heuristic to obtain a lower bound and make preprocessing of an alignment graph to reduce its size; efficient implementation of the algorithm for large but sparse alignment graphs including memory preallocation and bit representation of adjacency matrix. The computational results are provided for the popular Skolnick test set of 40 proteins and show that the suggested algorithm is more efficient than one of the fastest PSAP solvers - the ACF algorithm by Malod- Dognin et al. (2010).
Added: Oct 24, 2016
Working paper
Zlotnik A., Romanova A. V. arxiv.org. math. Cornell University, 2013. No. arxiv: 1307.5398.
We consider an initial-boundary value problem for a 2D time-dependent Schrödinger equation on a semi-infi nite strip. For the Numerov-Crank-Nicolson finite-di fference scheme with discrete transparent boundary conditions, the Strang-type splitting with respect to the potential is applied. For the resulting method, the uniqueness of a solution and the uniform in time L_2-stability (in particular, L_2-conservativeness) are proved. Due to the splitting, an eff ective direct algorithm using FFT in the direction perpendicular to the strip is developed to implement the splitting method for general potential. Numerical results on the tunnel eff ect for smooth and rectangular barriers together with the practical error analysis on refining meshes are included as well.
Added: Jul 24, 2013
Working paper
Aziz H., Moulin H., Sandomirskiy F. Computer Science and Game Theory (cs.GT), arXiv:1909.00740. arXiv. Cornell university, 2019
We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.
Added: Sep 24, 2019
Working paper
Maxim Borisyak, Zykov R., Noskov A. arxiv :: cs :: Cornell University. arxiv :: cs :: Cornell University. Cornell University, 2015
Classical approaches in recommender systems such as collaborative filtering are concentrated mainly on static user preference extraction. This approach works well as an example for music recommendations when a user behavior tends to be stable over long period of time, however the most common situation in e-commerce is different which requires reactive algorithms based on a short-term user activity analysis. This paper introduces a small mathematical framework for short-term user interest detection formulated in terms of item properties and its application for recommender systems enhancing. The framework is based on the fundamental concept of information theory --- Kullback-Leibler divergence.
Added: Nov 9, 2015
Working paper
Starchenko A., Kazakevich L., Lyashevskaya O. Linguistics. WP BRP. НИУ ВШЭ, 2018. No. 76.
The poetic texts pose a challenge to full morphological tagging and lemmatization since the authors seek to extend the vocabulary, employ morphologically and semantically deficient forms, go beyond standard syntactic templates, use non-projective constructions and non-standard word order, among other techniques of the creative language game. In this paper we evaluate a number of probabilistic taggers based on decision trees, CRF and neural network algorithms as well as one state-of-the-art dictionary-based tagger. The taggers were trained on prosaic texts and tested on three poetic samples of different complexity. Firstly, we discuss the method to compile the gold standard datasets for the Russian poetry. Secondly, we evaluate the taggers’ performance in the identification of the part of speech tags and lemmas. Finally, we analyze different types of errors in the taggers’ output. We analyse the confusion matrix of the parts of speech and mismatches in lemma annotation.
Added: Dec 12, 2018
Working paper
Ducomet B., Zlotnik A., Romanova A. V. arxiv.org. math. Cornell University, 2013. No. 1309.7280 .
An initial-boundary value problem for the $n$-dimensional ($n\geq 2$) time-dependent Schrödinger equation in a semi-infinite (or infinite) parallelepiped is considered. Starting from the Numerov-Crank-Nicolson finite-difference scheme, we first construct higher order scheme with splitting space averages having much better spectral properties for $n\geq 3$. Next we apply the Strang-type splitting with respect to the potential and, third, construct discrete transparent boundary conditions (TBC). For the resulting method, the uniqueness of solution and the unconditional uniform in time $L^2$-stability (in particular, $L^2$-conservativeness) are proved. Owing to the splitting, an effective direct algorithm using FFT (in the coordinate directions perpendicular to the leading axis of the parallelepiped) is applicable for general potential. Numerical results on the 2D tunnel effect for a P\"{o}schl-Teller-like potential-barrier and a rectangular potential-well are also included.
Added: Oct 1, 2013
Working paper
Dagaev N., Roads B. D., Luo X. et al. arxiv.org. Computer Science. Cornell University, 2021
Despite their impressive performance in object recognition and other tasks under standard testing conditions, deep networks often fail to generalize to out-of-distribution (o.o.d.) samples. One cause for this shortcoming is that modern architectures tend to rely on "shortcuts" - superficial features that correlate with categories without capturing deeper invariants that hold across contexts. Real-world concepts often possess a complex structure that can vary superficially across contexts, which can make the most intuitive and promising solutions in one context not generalize to others. One potential way to improve o.o.d. generalization is to assume simple solutions are unlikely to be valid across contexts and avoid them, which we refer to as the too-good-to-be-true prior. A low-capacity network (LCN) with a shallow architecture should only be able to learn surface relationships, including shortcuts. We find that LCNs can serve as shortcut detectors. Furthermore, an LCN's predictions can be used in a two-stage approach to encourage a high-capacity network (HCN) to rely on deeper invariant features that should generalize broadly. In particular, items that the LCN can master are downweighted when training the HCN. Using a modified version of the CIFAR-10 dataset in which we introduced shortcuts, we found that the two-stage LCN-HCN approach reduced reliance on shortcuts and facilitated o.o.d. generalization.
Added: Sep 16, 2021
Working paper
Lyashevskaya O., Пантелеева И. М. Linguistics. WP BRP. НИУ ВШЭ, 2017
The paper presents a Universal Dependencies (UD) annotation scheme for a learner English corpus. The REALEC dataset consists of essays written in English by Russian-speaking university students in the course of general English. The essays are a part of students' preparation for the independent final examination similar to the international English exam. While adjusting existing dependency parsing tools to a learner data, one has to take into account to what extent students' mistakes provoke errors in the parser output. The ungrammatical and stylistically inappropriate utterances may challenge parsers' algorithms trained on grammatically appropriate written texts. In our experiments, we compared the output of the dependency parser UDpipe (trained on UD-English 2.0) with the results of manual parsing, placing a particular focus on parses of ungrammatical English clauses. We show how mistakes made by students influence the work of the parser. Overall, UDpipe performed reasonably well (UAS 92.9, LAS 91.7). The following cases cause the errors in automatic annotation a) incorrect detection of a head, b) incorrect detection of the relation type, as well as c) both. We propose some solutions which could improve the automatic output and thus make the assessment of syntactic complexity more reliable.
Added: Dec 15, 2017
Working paper
Granin S., Maximov Y. math. arxive. Cornell University, 2015
Added: Oct 30, 2015
Working paper
Ovchinnikov A., Pogudin G., Vo T. Working papers by Cornell University. Cornell University, 2018
Elimination of unknowns in systems of equations, starting with Gaussian elimination, is a problem of general interest. The problem of finding an a priori upper bound for the number of differentiations in elimination of unknowns in a system of differential-algebraic equations (DAEs) is an important challenge, going back to Ritt (1932). The first characterization of this via an asymptotic analysis is due to Grigoriev's result (1989) on quantifier elimination in differential fields, but the challenge still remained. In this paper, we present a new bound, which is a major improvement over the previously known results. We also present a new lower bound, which shows asymptotic tightness of our upper bound in low dimensions, which are frequently occurring in applications. Finally, we discuss applications of our results to designing new algorithms for elimination of unknowns in systems of DAEs.
Added: Nov 1, 2019
Working paper
Bartunov S., Кондрашкин Д. А., Osokin A. et al. Computation and language. arXiv:1502.07257. Arxiv.org, 2015
Recently proposed Skip-gram model is a powerful method for learning high-dimensional word representations that capture rich semantic relationships between words. However, Skip-gram as well as most prior work on learning word representations does not take into account word ambiguity and maintain only single representation per word. Although a number of Skip-gram modifications were proposed to overcome this limitation and learn multi-prototype word representations, they either require a known number of word meanings or learn them using greedy heuristic approaches. In this paper we propose the Adaptive Skip-gram model which is a nonparametric Bayesian extension of Skip-gram capable to automatically learn the required number of representations for all words at desired semantic resolution. We derive efficient online variational learning algorithm for the model and empirically demonstrate its efficiency on word-sense induction task.
Added: Nov 5, 2015