nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Computer Science – Theory and Applications

7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings

herausgegeben von: Edward A. Hirsch, Juhani Karhumäki, Arto Lepistö, Michail Prilutskii

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the proceedings of the 7th International Computer Science Symposium in Russia, CSR 2012, held in Nizhny Novgorod in July 2012. The 28 full papers presented in this volume were carefully reviewed and selected from 66 submissions. CSR 2012 was one of the events of the Alan Turing Year 2012, the topics dealt with cover substantial parts of theoretical computer science and its applications.

Inhaltsverzeichnis

Frontmatter

Opening Talk

Can the Theory of Algorithms Ratify the “Invisible Hand of the Market”?

Abstract

”It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest.” Each participant in a competitive economy is ”led by an invisible hand to promote an end which was no part of his intention.”

Adam Smith, 1776.

With his treatise, The Wealth of Nations, 1776, Adam Smith initiated the field of economics, and his famous quote provided this field with its central guiding principle. The pioneering work of Walras (1874) gave a mathematical formulation for this statement, using his notion of market equilibrium, and opened up the possibility of a formal ratification.

Mathematical ratification came with the celebrated Arrow-Debreu Theorem (1954), which established existence of equilibrium in a very general model of the economy; however, an efficient mechanism for finding an equilibrium has remained elusive.

The latter question can clearly benefit from the powerful tools of modern complexity theory and algorithms. In this talk, we will provide an in-depth overview of the fascinating theory that has emerged around this question over the last decade.

Vijay V. Vazirani

Full Papers

Resilient Quicksort and Selection

Abstract

We consider the problem of sorting a sequence of n keys in a RAM-like environment where memory faults are possible. An algorithm is said to be δ-resilient if it can tolerate up to δ memory faults during its execution. A resilient sorting algorithm must produce a sequence where every pair of uncorrupted keys is ordered correctly. Finocchi, Grandoni, and Italiano devised a δ-resilient deterministic mergesort algorithm that runs in O(n logn + δ ²) time. We present a δ-resilient randomized algorithm (based on quicksort) that runs in $O(n \log n + \delta \sqrt{n \log n})$ expected time and its deterministic variation that runs in $O(n \log n + \delta \sqrt{n} \, \log n)$ worst-case time. This improves the previous known result for $\delta > \sqrt{n} \, \log n$.

Our deterministric sorting relies on the notion of an approximate k-th order statistic. For this auxiliary problem, we devise a deterministic algorithm that runs in $O(n + \delta \sqrt{n})$ time and produces a key (either corrupted or not) whose order rank differs from k by at most O(δ).

Maxim Babenko, Ivan Pouzyrevsky

General Quantitative Specification Theories with Modalities

Abstract

This paper proposes a new theory of quantitative specifications. It generalizes the notions of step-wise refinement and compositional design operations from the Boolean to an arbitrary quantitative setting. It is shown that this general approach permits to recast many existing problems which arise in system design.

Sebastian S. Bauer, Uli Fahrenberg, Axel Legay, Claus Thrane

The Complexity of Intersecting Finite Automata Having Few Final States

Abstract

The problem of determining whether several finite automata accept a common word is closely related to the well-studied membership problem in transformation monoids. We review the complexity of the intersection problem and raise the issue of limiting the number of final states in the automata involved. In particular, we consider commutative automata with at most two final states and we partially elucidate the complexity of their intersection nonemptiness and related problems.

Michael Blondin, Pierre McKenzie

News about Semiantichains and Unichain Coverings

Abstract

We study a min-max relation conjectured by Saks and West: For any two posets P and Q the size of a maximum semiantichain and the size of a minimum unichain covering in the product P×Q are equal. As a positive result we state conditions on P and Q that imply the min-max relation. However, we also have an example showing that in general the min-max relation is false. This disproves the Saks-West conjecture.

Bartłomiej Bosek, Stefan Felsner, Kolja Knauer, Grzegorz Matecki

Checking Tests for Read-Once Functions over Arbitrary Bases

Abstract

A Boolean function is called read-once over a basis B if it can be expressed by a formula over B where no variable appears more than once. A checking test for a read-once function f over B depending on all its variables is a set of input vectors distinguishing f from all other read-once functions of the same variables. We show that every read-once function f over B has a checking test containing O(n ^l) vectors, where n is the number of relevant variables of f and l is the largest arity of functions in B. For some functions, this bound cannot be improved by more than a constant factor. The employed technique involves reconstructing f from its l-variable projections and provides a stronger form of Kuznetsov’s classic theorem on read-once representations.

Dmitry V. Chistikov

Approximating Minimum Power Edge-Multi-Covers

Abstract

Given a graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph G = (V,E) with edge costs and degree bounds {r(v):v ∈ V}, the Minimum-Power Edge-Multi-Cover (MPEMC) problem is to find a minimum-power subgraph J of G such that the degree of every node v in J is at least r(v). Let k = max _v ∈ V r(v). For k = Ω(logn), the previous best approximation ratio for MPEMC was O(logn), even for uniform costs [3]. Our main result improves this ratio to O(logk) for general costs, and to O(1) for uniform costs. This also implies ratios O(logk) for the Minimum-Power k -Outconnected Subgraph and $O\left(\log k \log \frac{n}{n-k} \right)$ for the Minimum-Power k -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem. In addition, for small values of k, we improve the previously best ratio k + 1 to k + 1/2.

Nachshon Cohen, Zeev Nutov

A Lower Bound on Circuit Complexity of Vector Function in U 2

Abstract

In 1973, Lamagna and Savage proved the following result. If f _j : {0,1}ⁿ → {0,1} for 1 ≤ j ≤ m depends on at least two variables and if for i ≠ j, f _i ≠ f _j and $f_i \neq \bar{f_j}$, then for any binary basis Ω,

$$C_{\Omega}(f_1, \ldots f_m) \geq \min\limits_j C_{\Omega}(f_j) + m -1,$$

where C _Ω(f) is the minimal size of a circuit computing f in the basis Ω.

The main purpose of this paper is to give a better lower bound for the following case. Let f : {0,1}ⁿ → {0,1} and f _i = f ⊕ x _i for 1 ≤ i ≤ n. Assume that f is not a constant after any three substitutions x _i = c _i for different variables. Then

$$C_{U_2}(f_1, \ldots f_n) \geq \min\limits_{i \neq j, c_i, c_j } C_{U_2}(f\mid_{x_i = c_i, x_j = c_j})+2n-O(1),$$

where U ₂ = B ₂ ∖ { ⊕ , ≡ }. This implies a 7n lower bound on the circuit complexity over U ₂ of f ₁, …, f _n if f has circuit complexity at least 5n.

Evgeny Demenkov

Computing All MOD-Functions Simultaneously

Abstract

The fundamental symmetric functions are $\textrm{EX}_k^n$ (equal to 1 if the sum of n input bits is exactly k), $\textrm{TH}_k^n$ (the sum is at least k), and $\textrm{MOD}_{m,r}^n$ (the sum is congruent to r modulo m). It is well known that all these functions and in fact any symmetric Boolean function have linear circuit size.

Simple counting shows that the circuit complexity of computing n symmetric functions is Ω(n ^{2 − o(1)}) for almost all tuples of n symmetric functions. It is well-known that all EX and TH functions (i.e., for all 0 ≤ k ≤ n) of n input bits can be computed by linear size circuits.

In this short note, we investigate the circuit complexity of computing all MOD functions (for all 1 ≤ m ≤ n). We prove an O(n) upper bound for computing the set of functions

$$\{\ensuremath{\textrm{MOD}}_{1,r}^n, \ensuremath{\textrm{MOD}}_{2,r}^n, \dots, \ensuremath{\textrm{MOD}}_{n,r}^n\}$$

and an O(nloglogn) upper bound for

$$\{\ensuremath{\textrm{MOD}}_{1,r_1}^n, \ensuremath{\textrm{MOD}}_{2,r_2}^n, \dots, \ensuremath{\textrm{MOD}}_{n,r_n}^n\},$$

where r ₁, r ₂, …, r _n are arbitrary integers.

Evgeny Demenkov, Alexander S. Kulikov, Ivan Mihajlin, Hiroki Morizumi

Bounded Synchronization Delay in Omega-Rational Expressions

Abstract

In 1965 Schützenberger published his famous result that star-free languages (SF) and aperiodic languages (AP) coincide over finite words, often written as SF = AP. Perrin generalized SF = AP to infinite words in the mid 1980s. In 1973 Schützenberger presented another (and less known) characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used. We denote this class of languages by SD. In this paper, we present a generalization of SD = AP to infinite words. This became possible via a substantial simplification of the proof for the corresponding result for finite words. Moreover, we show that SD = AP can be viewed as more fundamental than SF = AP in the sense that the classical 1965 result of Schützenberger and its 1980s extension to infinite words by Perrin are immediate consequences of SD = AP.

Volker Diekert, Manfred Kufleitner

Towards Optimal Degree-Distributions for Left-Perfect Matchings in Random Bipartite Graphs

Abstract

Consider a random bipartite multigraph G with n left nodes and m ≥ n ≥ 2 right nodes. Each left node x has d _x ≥ 1 random right neighbors. The average left degree $\bar{{\mathrm{\scriptstyle\Delta}}}$ is fixed, $\bar{{\mathrm{\scriptstyle\Delta}}}\geq2$. We ask whether for the probability that G has a left-perfect matching it is advantageous not to fix d _x for each left node x but rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If $\bar{{\mathrm{\scriptstyle\Delta}}}$ is an integer then it is optimal to use a fixed degree of $\bar{{\mathrm{\scriptstyle\Delta}}}$ for all left nodes. If $\bar{{\mathrm{\scriptstyle\Delta}}}$ is non-integral then an optimal degree-distribution has the property that each left node x has two possible degrees, $\ensuremath{\lfloor \bar{{\mathrm{\scriptstyle\Delta}}}\rfloor}$ and $\ensuremath{\lceil \bar{{\mathrm{\scriptstyle\Delta}}}\rceil}$, with probability p _x and 1 − p _x, respectively, where p _x is from the closed interval [0,1] and the average over all p _x equals $\ensuremath{\lceil \bar{{\mathrm{\scriptstyle\Delta}}}\rceil}-\bar{{\mathrm{\scriptstyle\Delta}}}$. Furthermore, if n = c·m and $\bar{{\mathrm{\scriptstyle\Delta}}}>2$ is constant, then each distribution of the left degrees that meets the conditions above determines the same threshold $c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})$ that has the following property as n goes to infinity: If $c<c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})$ then there exists a left-perfect matching with high probability. If $c>c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})$ then there exists no left-perfect matching with high probability. The threshold $c^*({\bar{{\mathrm{\scriptstyle\Delta}}}})$ is the same as the known threshold for offline k-ary cuckoo hashing for integral or non-integral $k=\bar{{\mathrm{\scriptstyle\Delta}}}$.

Martin Dietzfelbinger, Michael Rink

Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs

Abstract

We study the following problem: Given a set of points in the plane and a positive integer k > 0, construct a geometric strongly connected spanning digraph of out-degree at most k and whose longest edge length is the shortest possible. The motivation comes from the problem of replacing omnidirectional antennae in a sensor network with k directional antennae per sensor so that the resulting sensor network is strongly connected. The contribution of this is paper is twofold:

1) We introduce a notion of robustness of the radius in geometric graphs. This allows us to provide stronger lower bounds for the edge length needed to solve our problem, while nicely connecting two previously unrelated research directions (graph toughness and multiple directional antennae).

2) We present novel upper bound techniques which, in combination with stronger lower bounds, allow us to improve the previous approximation results for the edge length needed to achieve strong connectivity for k = 4 (from 2sin(π/5) to optimal) and k = 3 (from $2\sin(\frac{\pi}{4})$ to $2\sin(\frac{2\pi}{9})$).

Stefan Dobrev, Evangelos Kranakis, Oscar Morales Ponce, Milan Plžík

Worst-Case Optimal Priority Queues via Extended Regular Counters

Abstract

We consider the classical problem of representing a collection of priority queues under the operations find-min, insert, decrease, meld, delete, and delete-min. In the comparison-based model, if the first four operations are to be supported in constant time, the last two operations must take at least logarithmic time. Brodal showed that his worst-case efficient priority queues achieve these worst-case bounds. Unfortunately, this data structure is involved and the time bounds hide large constants. We describe a new variant of the worst-case efficient priority queues that relies on extended regular counters and provides the same asymptotic time and space bounds as the original. Due to the conceptual separation of the operations on regular counters and all other operations, our data structure is simpler and easier to describe and understand. Also, the constants in the time and space bounds are smaller.

Amr Elmasry, Jyrki Katajainen

The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs

Abstract

Robertson and Seymour (in work starting with [15]) demonstrated that any minor-ancestral graph property can be decided in polynomial time. Lewis and Yannakakis [14] showed that for any nontrivial node-hereditary graph property, the problem of given a graph, finding the size of the largest induced subgraph of the graph that has the property, is NP-hard. In this paper, we completely characterize those minor-ancestral properties for which the problem of deciding if a given graph contains a subgraph with the property that respects a given set of forbidden vertex pairs (i.e., if one vertex from a pair is in the subgraph then the other isn’t) is in P and for which such properties the problem is NP-complete. In particular, we show that if a given minor-ancestral property can be characterized by the containment of one of a finite set of graphs as a subgraph, the corresponding decision problem with forbidden vertex pairs is in P, otherwise its NP-complete. Unfortunately, we further show that the problem of deciding if a minor-ancestral property (presented as a set of characteristic minors) can be so characterized is NP-hard. Finally we observe that a similar characterization holds for the case of finding subgraphs satisfying a set of forbidden edge pairs and that our problems are all fixed parameter tractable.

Eli Fox-Epstein, Danny Krizanc

Satisfiability Thresholds beyond k −XORSAT

Abstract

We consider random systems of equations x ₁ + … + x _k = a, 0 ≤ a ≤ 2 which are interpreted as equations modulo 3. We show for k ≥ 15 that the satisfiability threshold of such systems occurs where the 2 −core has density 1. We show a similar result for random uniquely extendible constraints over 4 elements. Our results extend previous results of Dubois/Mandler for equations mod 2 and k = 3 and Connamacher/Molloy for uniquely extendible constraints over a domain of 4 elements with k = 3 arguments.

The proof is based on variance calculations, using a technique introduced by Dubois/Mandler. However, several additional observations (of independent interest) are necessary.

Andreas Goerdt, Lutz Falke

Finding Vertex-Surjective Graph Homomorphisms

Abstract

The Surjective Homomorphism problem is to test whether a given graph G called the guest graph allows a vertex-surjective homomorphism to some other given graph H called the host graph. The bijective and injective homomorphism problems can be formulated in terms of spanning subgraphs and subgraphs, and as such their computational complexity has been extensively studied. What about the surjective variant? Because this problem is NP-complete in general, we restrict the guest and the host graph to belong to graph classes ${\cal G}$ and ${\cal H}$, respectively. We determine to what extent a certain choice of ${\cal G}$ and ${\cal H}$ influences its computational complexity. We observe that the problem is polynomial-time solvable if ${\cal H}$ is the class of paths, whereas it is NP-complete if ${\cal G}$ is the class of paths. Moreover, we show that the problem is even NP-complete on many other elementary graph classes, namely linear forests, unions of complete graphs, cographs, proper interval graphs, split graphs and trees of pathwidth at most 2. In contrast, we prove that the problem is fixed-parameter tractable in k if ${\cal G}$ is the class of trees and ${\cal H}$ is the class of trees with at most k leaves, or if ${\cal G}$ and ${\cal H}$ are equal to the class of graphs with vertex cover number at most k.

Petr A. Golovach, Bernard Lidický, Barnaby Martin, Daniël Paulusma

Broadcast Domination on Block Graphs in Linear Time

Abstract

A broadcast domination on a graph assigns an integer value f(u) ≥ 0 to each vertex u, such that every vertex u with f(u) = 0 is within distance f(v) from a vertex v with f(v) > 0. The Broadcast Domination problem seeks to compute a broadcast domination where the sum of the assigned values is minimized. We show that Broadcast Domination can be solved in linear time on block graphs. For general graphs the best known algorithm runs in time $\mathcal{O}(n^6)$. For trees and interval graphs, linear-time algorithms are known. As block graphs form a superclass of trees, our result extends the classes of graphs on which this problem is solvable in linear time.

Pinar Heggernes, Sigve H. Sæther

Characterizing Certain Topological Specifications

Abstract

We prove a characterization theorem à la van Benthem for a particular modal system called topologic, which is, among other things, suitable for specifying the interrelation between knowledge and topology. The comparison language arising naturally from the relevant semantics is well-known from the beginnings of topological model theory, and subset space bisimulations provide for the proper notion of invariance of formulas here.

Bernhard Heinemann

Descriptional Complexity of Operations on Alternating and Boolean Automata

Abstract

The paper shows that the tight bound for the conversion of alternating finite automata into nondeterministic finite automata with a single initial state is 2ⁿ + 1. This solves an open problem stated by Fellah et al. (Intern. J. Computer Math. 35, 1990, 117–132). Then we examine the complexity of basic operations on languages represented by boolean and alternating finite automata. We get tight bounds for intersection and union, and for concatenation and reversal of languages represented by boolean automata. In the case of star, and of concatenation and reversal of AFA languages, our upper and lower bounds differ by one.

Galina Jirásková

Consistency of Multidimensional Combinatorial Substitutions

Abstract

Multidimensional combinatorial substitutions are rules that replace symbols by finite patterns of symbols in ℤ^d. We focus on the case where the patterns are not necessarily rectangular, which requires a specific description of the way they are glued together in the image by a substitution. Two problems can arise when defining a substitution in such a way: it can fail to be consistent, and the patterns in an image by the substitution might overlap.

We prove that it is undecidable whether a two-dimensional substitution is consistent or overlapping, and we provide practical algorithms to decide these properties in some particular cases.

Timo Jolivet, Jarkko Kari

Two-Way Automata Characterizations of L/poly versus NL

Abstract

Let L/poly and NL be the standard complexity classes, of languages recognizable in logarithmic space by Turing machines which are deterministic with polynomially-long advice and nondeterministic without advice, respectively. We recast the question whether L/poly⊇NL in terms of deterministic and nondeterministic two-way finite automata (2dfas and 2nfas). We prove it equivalent to the question whether every s-state unary 2nfa has an equivalent poly(s)-state 2dfa, or whether a poly(h)-state 2dfa, can check accessibility in h-vertex graphs (even under unary encoding) or check two-way liveness in h-tall, h-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages (even unary ones), use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecture that implies L/poly $\nsupseteq$ NL.

Christos A. Kapoutsis, Giovanni Pighizzini

Cutting through Regular Post Embedding Problems

Abstract

The Regular Post Embedding Problem extended with partial (co)directness is shown decidable. This extends to universal and/or counting versions. It is also shown that combining directness and codirectness in Post Embedding problems leads to undecidability.

Prateek Karandikar, Philippe Schnoebelen

On the Advice Complexity of the Set Cover Problem

Abstract

Recently, a new approach to get a deeper understanding of online computation has been introduced: the study of the advice complexity of online problems. The idea is to measure the information that online algorithms need to be supplied with to compute high-quality solutions and to overcome the drawback of not knowing future input requests. In this paper, we study the advice complexity of an online version of the well-known set cover problem introduced by Alon et al.: for a ground set of size n and a set family of m subsets of the ground set, we obtain bounds in both n and m. We prove that a linear number of advice bits is both sufficient and necessary to perform optimally. Furthermore, for any constant c, we prove that n − c bits are enough to construct a c-competitive online algorithm and this bound is tight up to a constant factor (only depending on c). Moreover, we show that a linear number of advice bits is both necessary and sufficient to be optimal with respect to m, as well. We further show lower and upper bounds for achieving c-competitiveness also in m.

Dennis Komm, Richard Královič, Tobias Mömke

Constraint Satisfaction with Counting Quantifiers

Abstract

We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers, which may be seen as variants of CSPs in the mould of quantified CSPs (QCSPs).

We show that a single counting quantifier strictly between ∃ ^≥ 1: = ∃ and ∃ ^≥ n: = ∀ (the domain being of size n) already affords the maximal possible complexity of QCSPs (which have both ∃ and ∀), being Pspace-complete for a suitably chosen template.

Next, we focus on the complexity of subsets of counting quantifiers on clique and cycle templates. For cycles we give a full trichotomy – all such problems are in L, NP-complete or Pspace-complete. For cliques we come close to a similar trichotomy, but one class remains outstanding.

Afterwards, we consider the generalisation of CSPs in which we augment the extant quantifier ∃ ^≥ 1: = ∃ with the quantifier ∃ ^≥ j (j ≠ 1). Such a CSP is already NP-hard on non-bipartite graph templates. We explore the situation of this generalised CSP on bipartite templates, giving various conditions for both tractability and hardness – culminating in a classification theorem for general graphs.

Finally, we use counting quantifiers to solve the complexity of a concrete QCSP whose complexity was previously open.

Florent Madelaine, Barnaby Martin, Juraj Stacho

Space-Bounded Kolmogorov Extractors

Abstract

An extractor is a function that receives some randomness and either “improves” it or produces “new” randomness. There are statistical and algorithmical specifications of this notion. We study an algorithmical one called Kolmogorov extractors and modify it to resource-bounded version of Kolmogorov complexity. Following Zimand we prove the existence of such objects with certain parameters. The utilized technique is “naive” derandomization: we replace random constructions employed by Zimand by pseudo-random ones obtained by Nisan-Wigderson generator.

Daniil Musatov

Some Results on more Flexible Versions of Graph Motif

Abstract

The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a multiset of colors occurs in a connected subgraph of a vertex-colored graph. Due to the high rate of noise in the biological data, more flexible definitions of the problem have been outlined. We present in this paper two inapproximability results for two different optimization variants of Graph Motif. We also study another definition of the problem, when the connectivity constraint is replaced by modularity. While the problem stays NP-complete, it allows algorithms in FPT for biologically relevant parameterizations.

Romeo Rizzi, Florian Sikora

A Characterization of Cellular Automata Generated by Idempotents on the Full Shift

Abstract

In this article, we discuss the family of cellular automata generated by so-called idempotent cellular automata (CA G such that G ² = G) on the full shift. We prove a characterization of products of idempotent CA, and show examples of CA which are not easy to directly decompose into a product of idempotents, but which are trivially seen to satisfy the conditions of the characterization. Our proof uses ideas similar to those used in the well-known Embedding Theorem and Lower Entropy Factor Theorem in symbolic dynamics. We also consider some natural decidability questions for the class of products of idempotent CA.

Ville Salo

Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time

Abstract

We show how to check in linear time if a function $f:{\mathbb Z}_k^n \to{\mathbb Z}_k$, where k = p ^m, p is a prime number, and m ≥ 2, specified by its values, can be represented by a polinomial in the ring ℤ_k[x ₁, …, x _n]. If so, our algorithm also constructs (in linear time) its canonical polynomial representation. We also show how to extend our techniques (with linear time) to the cases of an arbitrary composite number k.

More precisely, we prove that the circuit-size complexity of solving the problem, if a given function $f:{\mathbb Z}_k^n \to{\mathbb Z}_k$, where k is a fixed composite number, specified by its values, is represented by a polynomial in the ring ℤ_k[x ₁, …, x _n] and, if so, finding its polynomial, is linear.

Svetlana N. Selezneva

Boolean Composition of Visual Secret Sharing Schemes

Abstract

In this paper, we analyze the disjunction and the conjunction of two access structures for visual secret sharing schemes. The latter operation, when applied to k-out-of-n schemes, leads to schemes with multiple thresholds. We precisely determine the maximum relative contrast for schemes of this type. As in the case of classical schemes with a single threshold, the analysis proceeds by revealing a central relation between the relative contrast in a visual secret sharing scheme and the error-term in a related problem of approximation-theoretic flavor.

Hans Ulrich Simon

Backmatter

Titel: Computer Science – Theory and Applications
herausgegeben von: Edward A. Hirsch
Juhani Karhumäki
Arto Lepistö
Michail Prilutskii
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-30642-6
Print ISBN: 978-3-642-30641-9
DOI: https://doi.org/10.1007/978-3-642-30642-6