Add a filter

Of all publications in the section: 124

Sort:

by name

by year

Working paper

We study properties of Markov chain Monte Carlo simulations of classical spin models with local updates. We derive analytic expressions for the mean value of the acceptance rate of the single-spin-flip algorithms for the one-dimensional Ising model. We find that for the Metropolis algorithm the average acceptance rate is a linear function of energy. We further provide numerical results for the energy dependence of the average acceptance rate for the 3- and 4-state Potts model, and the XY model in one and two spatial dimensions. In all cases, the acceptance rate is an almost linear function of the energy in the critical region. The variance of the acceptance rate is studied as a function of the specific heat.

Added: Jul 17, 2019

Working paper

A Computational Model That Recovers Depth from Stereo-Input without Using Any Oculomotor Information

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

Added: Apr 8, 2015

Working paper

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

Branzei S.,

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

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

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

We consider an initial-boundary value problem for a 2D time-dependent Schrödinger equation on a semi-infinite strip. For the Numerov-Crank-Nicolson finite-difference 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 effective 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 effect 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.,

, 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

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

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.,

, 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

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.,

math. arxive. Cornell University, 2015
Added: Oct 30, 2015

Working paper

Ovchinnikov A.,

, 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

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

Working paper

We propose a new method for assessing agents’ influence in network structures, which takes into consideration nodes attributes, individual and group influences of nodes, and the intensity of interactions. This approach helps us to identify both explicit and hidden central elements which cannot be detected by classical centrality measures or other indices.

Added: Jul 13, 2016

Working paper

The paper analyzes legal issues associated with application of existing contract law provisions to so-called Smart contracts, defined in the paper as “agreements existing in the form of software code implemented on the Blockchain platform, which ensures autonomy and self-executive nature of Smart contract terms based on predetermined set of factors”. The paper consists of several sections. In the first section, the paper outlines peculiarities of Blockchain technology as currently implemented in Bitcoin cryptocurrency and which forms the core of Smart contracts. In the second section, the main characteristic features of Smart contracts are described. Finally, the paper outlines key tensions between classic contract law and Smart contracts.. The conclusion section sets the core question for analysis of the perspectives of implementation of this technology by governments: “How to align the powers of the government with Blockchain if there is no central authority but only distributed technologies”. The author suggests two solutions, which are not optimal: 1) providing the state authorities with the status of a Superuser with extra powers and 2) relying on traditional remedies and enforcement practices, by pursuing specific individuals – parties to Smart contract - in offline mode. It is emphasized that those jurisdictions, which have the most Blockchain-friendly regulations will have competitive advantage in attraction of new innovative business models and companies willing to exploit them in a legal way.

Added: Dec 22, 2016

Working paper

Hierarchical structures are frequently used to formalize complex multicriteria decision analysis problems. The analytic hierarchy process (AHP) of Saaty (1980) is an established method used to solve practical multicriteria problems of the hierarchical nature. It is also well-known that AHP, and its modifications and generalizations poses a number of fundamental drawbacks that cannot in principle be overcome. The main drawbacks are the independence of the evaluation procedure of the criteria importance from the normalization of criterion values – this violates the requirement of the mathematical theory of measurement, and the lack of a formal definition of the notion of criteria importance. Furthermore, the use of ratio scales in AHP for the expression of importance of criteria is theoretically unsubstantiated. We suggest a new methodology suitable for the analysis of multicriteria problems with hierarchical structures. It is based on criteria importance theory.

Added: Apr 24, 2014

Working paper

Positive-Unlabeled Learning is an analog of supervised binary classification for the case when the Negative (N) sample in the training set is contaminated with latent instances of the Positive (P) class and hence is Unlabeled (U). We develop DEDPUL1 , a method able to solve two problems: first, to estimate the proportions of the mixing components (P and N) in U, and then, to classify U. The main steps are to reduce dimensionality of the data using Non-Traditional Classifier [11], to estimate densities of the reduced data in both P and U samples, and to apply the Bayes rule to density ratio. We experimentally show that DEDPUL outperforms current state-of-the-art methods for both problems. Additionally, we improve current state-of-the-art method for PU Classification [16].

Added: May 31, 2019

Working paper

Amzallag E., Minchenko A.,

Working papers by Cornell University. Cornell University, 2019
Algorithms working with linear algebraic groups often represent them via defining polynomial equations. One can always choose defining equations for an algebraic group to be of the degree at most the degree of the group as an algebraic variety. However, the degree of a linear algebraic group G⊂GLn(C) can be arbitrarily large even for n=1. One of the key ingredients of Hrushovski's algorithm for computing the Galois group of a linear differential equation was an idea to `approximate' every algebraic subgroup of GLn(C) by a `similar' group so that the degree of the latter is bounded uniformly in n. Making this uniform bound computationally feasible is crucial for making the algorithm practical.
In this paper, we derive a single-exponential degree bound for such an approximation (we call it toric envelope), which is qualitatively optimal. As an application, we improve the quintuply exponential bound for the first step of the Hrushovski's algorithm due to Feng to a single-exponential bound. For the cases n=2,3 often arising in practice, we further refine our general bound.

Added: Nov 1, 2019