Article
An improved optimization algorithm of ads’ allocation in sponsored search and the results of experiments
This paper describes a modified version of an algorithm suggested earlier by the authors for optimizing of ads allocation in sponsored search on the main page of search results in response to user search queries to a web search engine. It is demonstrated that the modification of the algorithm reduces appreciably the searching procedure and the algorithm complexity. And finally, the new algorithm undergoes experimental testing on real data sets provided by Yandex. © 2015, Pleiades Publishing, Ltd.
This book constitutes the proceedings of the 13th International Computer Science Symposium in Russia, CSR 2018, held in Moscow, Russia, in May 2018.
The 24 full papers presented together with 7 invited lectures were carefully reviewed and selected from 42 submissions. The papers cover a wide range of topics such as algorithms and data structures; combinatorial optimization; constraint solving; computational complexity; cryptography; combinatorics in computer science; formal languages and automata; algorithms for concurrent and distributed systems; networks; and proof theory and applications of logic to computer science.
It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in EXPNP, or even in EXP that are not computable by polynomial size circuits and hence are not reducible to a sparse set. In this paper we study this question in a more restricted setting: what is the computational complexity of sparse sets that are selfreducible? It follows from earlier work of Lozano and Torán (in: Mathematical systems theory, 1991) that EXPNP does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that NEXP does not have sparse tree-selfreducible hard sets. We also construct an oracle relative to which all of EXP is reducible to a sparse tree-selfreducible set. These lower bounds are corollaries of more general results about the computational complexity of sparse sets that are selfreducible, and can be interpreted as super-polynomial circuit lower bounds for NEXP.
t is known (from Counting curves and their projections by Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski [1, part 4]) that counting the number of points on a curve where is a sparse polynomial over
is #P-complete under randomized reductions.
We give a simple proof of a stronger result: counting roots of a sparse univariate polynomial over
is #P-complete under deterministic reductions.
We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull and any set of induced subgraphs each on at most 5 vertices.
We consider a computational model which is known as set automata.
The set automata are one-way finite automata with an additional storage—the set. There are two kinds of set automata—the deterministic and the nondeterministic ones. We denote them as DSA and NSA respectively. The model was introduced by Kutrib et al. in 2014 in [2, 3].
In this paper we characterize algorithmic complexity of the emptiness and membership problems for set automata. More definitely, we prove that both problems are PSPACEPSPACE-complete for both kinds of set automata.
The study has been funded by the Russian Academic Excellence Project ‘5-100’. Supported in part by RFBR grants 16–01–00362 and 17–51-10005.
We investigate the problem of conservative rewritability of a TBox T in a description logic (DL) L into a TBox T' in a weaker DL L'. We focus on model-conservative rewritability (T' entails T and all models of T are expandable to models of T'), subsumption-conservative rewritability (T' entails T and all subsumptions in the signature of T entailed by T' are entailed by T), and standard DLs between ALC and ALCQI. We give model-theoretic characterizations of conservative rewritability via bisimulations, inverse p-morphisms and generated subinterpretations, and use them to obtain a few rewriting algorithms and complexity results for deciding rewritability.
We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k for which there exists a MAJk o MAJk circuit that has high correlation with the majority of n bits is equal to Θ(n1/2). We then show that for a randomized MAJk o MAJk circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n2/3+o(1). We show a worst case lower bound: if a MAJk o MAJk circuit computes the majority of n bits correctly on all inputs, then k ≥ n13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k = O(n2/3) can compute MAJn correctly on all inputs.
This book constitutes the refereed proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018, held in Krems, Austria, in January/February 2018. The 48 papers presented in this volume were carefully reviewed and selected from 97 submissions. They were organized in topical sections named: foundations of computer science; software engineering: advances methods, applications, and tools; data, information and knowledge engineering; network science and parameterized complexity; model-based software engineering; computational models and complexity; software quality assurance and transformation; graph structure and computation; business processes, protocols, and mobile networks; mobile robots and server systems; automata, complexity, completeness; recognition and generation; optimization, probabilistic analysis, and sorting; filters, configurations, and picture encoding; machine learning; text searching algorithms; and data model engineering.