On the degree of boolean functions as real polynomials

Every Boolean function may be represented as a real polynomial. In this paper, we characterize the degree of this polynomial in terms of certain combinatorial properties of the Boolean function. Our first result is a tight lower bound of Ω(logn) on the degree needed to represent any Boolean function that depends onn variables. Our second result states that for every Boolean functionf, the following measures are all polynomially related:

o The decision tree complexity off.

o The degree of the polynomial representingf.

o The smallest degree of a polynomialapproximating f in theL _max norm.

     

Sulla complessità di alcuni problemi di conteggio

This paper is intended to show that an algebraic approach can give useful suggestions to design efficient algorithms solving combinatorial problems. The problems we discusses in the paper are:

1. Counting strings of given length generated by a regular grammar. For this problem, we give an exact algorithm whose complexity is 0 (logn) (with respect to the number of executed operations), and an approximate algorithm which however still has the same order of complexity;
2. counting trees recognized by a tree automaton. For this problem, we give an exact algorithm of complexity 0(n) and an approximate one of complexity 0 (logn). For this approximate algorithm the relative error is shown to be 0 (1/n).

     

Drawing planar graphs using the canonical ordering

We introduce a new method to optimize the required area, minimum angle, and number of bends of planar graph drawings on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. Using this method linear-time-and-space algorithms can be designed for many graph-drawing problems. Our main results are as follows:

Every triconnected planar graphG admits a planar convex grid drawing with straight lines on a (2n?4)×(n?2) grid, wheren is the number of vertices.

Every triconnected planar graph with maximum degree 4 admits a planar orthogonal grid drawing on ann×n grid with at most [3n/2]+4 bends, and ifn>6, then every edge has at most two bends.

Every planar graph with maximum degree 3 admits a planar orthogonal grid drawing with at most [n/2]+1 bends on an [n/2]×[n/2] grid.

Every triconnected planar graphG admits a planar polyline grid drawing on a (2n?6)×(3n?9) grid with minimum angle larger than 2/d radians and at most 5n?15 bends, withd the maximum degree.

These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g., concerning visibility representations, are included.     

On the power of unambiguity in log-space

We report progress on the NL versus UL problem.

We show that counting the number of s-t paths in graphs where the number of s-v paths for any v is bounded by a polynomial can be done in FUL: the unambiguous log-space function class. Several new upper bounds follow from this including ${{{ReachFewL} \subseteq {UL}}}$ and ${{{LFew} \subseteq {UL}^{FewL}}}$

We investigate the complexity of min-uniqueness—a central notion in studying the NL versus UL problem. In this regard we revisit the class OptL[log n] and introduce UOptL[log n], an unambiguous version of OptL[log n]. We investigate the relation between UOptL[log n] and other existing complexity classes.

We consider the unambiguous hierarchies over UL and UOptL[log n]. We show that the hierarchy over UOptL[log n] collapses. This implies that ${{{ULH} \subseteq {L}^{{promiseUL}}}}$ thus collapsing the UL hierarchy.

We show that the reachability problem over graphs embedded on 3 pages is complete for NL. This contrasts with the reachability problem over graphs embedded on 2 pages, which is log-space equivalent to the reachability problem in planar graphs and hence is in UL.

     

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Appl. Math., 42(1):51–63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:

• Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution.
• Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs.
• If T is a given tree, deciding whether a circle graph G has a dominating set inducing a graph isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by t=|V(T)|. We prove that the FPT algorithm runs in subexponential time, namely $2^{\mathcal{O}(t \cdot\frac{\log\log t}{\log t})} \cdot n^{\mathcal{O}(1)}$ , where n=|V(G)|.

     

Linear-time snapshot implementations in unbalanced systems

Anatomic snapshot memory object in shared memory systems enables a set of processes, calledscanners, to obtain a consistent picture of the shared memory while other processes, calledupdaters, keep updating memory locations concurrently. In this paper we present two conversion methods of snapshot implementations. Using the first conversion method we obtain a new snapshot implementation in which the scan operation has linear time complexity and the time complexity of the update operation becomes the sum of the time complexities of the original implementation. Applying the second conversion method yields similar results, where in this case the time complexity of the update protocol becomes linear. Although our conversion methods use unbounded space, their space complexity can be bounded using known techniques. One of the most intriguing open problems in distributed wait-free computing is the existence of a linear-time implementation of this object. Using our conversion methods and known constructions we obtain the following results:

?Consider a system ofn processes, each an updater and a scanner. We present an implementation in which the time complexity of either the update or the scan operation is linear, while the time complexity of the second operation isO(n logn).

?We present an implementation with linear time complexity when the number of either updaters or scanners isO(n/logn), wheren is the total number of processes.

?We present an implementation with amortized linear time complexity when one of the protocols (either upate or scan) is executed significantly more often than the other protocol.

     

Optimal parallel algorithms for rectilinear link-distance problems

We provide optimal parallel solutions to several link-distance problems set in trapezoided rectilinear polygons. All our main parallel algorithms are deterministic and designed to run on the exclusive read exclusive write parallel random access machine (EREW PRAM). LetP be a trapezoided rectilinear simple polygon withn vertices. InO(logn) time usingO(n/logn) processors we can optimally compute:

1. Minimum réctilinear link paths, or shortest paths in theL ₁ metric from any point inP to all vertices ofP.
2. Minimum rectilinear link paths from any segment insideP to all vertices ofP.
3. The rectilinear window (histogram) partition ofP.
4. Both covering radii and vertex intervals for any diagonal ofP.
5. A data structure to support rectilinear link-distance queries between any two points inP (queries can be answered optimally inO(logn) time by uniprocessor).

Our solution to 5 is based on a new linear-time sequential algorithm for this problem which is also provided here. This improves on the previously best-known sequential algorithm for this problem which usedO(n logn) time and space.5 We develop techniques for solving link-distance problems in parallel which are expected to find applications in the design of other parallel computational geometry algorithms. We employ these parallel techniques, for example, to compute (on a CREW PRAM) optimally the link diameter, the link center, and the central diagonal of a rectilinear polygon.     

Ray shooting on triangles in 3-space

We present a uniform approach to problems involving lines in 3-space. This approach is based on mapping lines inR ³ into points and hyperplanes in five-dimensional projective space (Plücker space). We obtain new results on the following problems:

1. Preprocessn triangles so as to answer efficiently the query: “Given a ray, which is the first triangle hit?” (Ray- shooting problem). We discuss the ray-shooting problem for both disjoint and nondisjoint triangles.
2. Construct the intersection of two nonconvex polyhedra in an output sensitive way with asubquadratic overhead term.
3. Construct the arrangement ofn intersecting triangles in 3-space in an output-sensitive way, with asubquadratic overhead term.
4. Efficiently detect the first face hit by any ray in a set of axis-oriented polyhedra.
5. Preprocessn lines (segments) so as to answer efficiently the query “Given two lines, is it possible to move one into the other without crossing any of the initial lines (segments)?” (Isotopy problem). If the movement is possible produce an explicit representation of it.

     

Regular prefix relations

We define a class ofn-ary relations on strings called the regular prefix relations, and give four alternative characterizations of this class:

1. the relations recognized by a new type of automaton, the prefix automata,
2. the relations recognized by tree automata specialized to relations on strings,
3. the relations between strings definable in the second order theory ofk successors,
4. the smallest class containing the regular sets and the prefix relation, and closed under the Boolean operations, Cartesian product, projection, explicit transformation, and concatenation with Cartesian products of regular sets.

We give concrete examples of regular prefix relations, and a pumping argument for prefix automata. An application of these results to the study of inductive inference of regular sets is described.     

Trial and error

A pac-learning algorithm isd-space bounded, if it stores at mostd examples from the sample at any time. We characterize thed-space learnable concept classes. For this purpose we introduce the compression parameter of a concept classb and design our Trial and Error Learning Algorithm. We show: b isd-space learnable if and only if the compression parameter ofb is at mostd. This learning algorithm does not produce a hypothesis consistent with the whole sample as previous approaches e.g. by Floyd, who presents consistent space bounded learning algorithms, but has to restrict herself to very special concept classes. On the other hand our algorithm needs large samples; the compression parameter appears as exponent in the sample size. We present several examples of polynomial time space bounded learnable concept classes:

- all intersection closed concept classes with finite VC-dimension.

- convexn-gons in ?².

- halfspaces in ?ⁿ.

- unions of triangles in ?².

We further relate the compression parameter to the VC-dimension, and discuss variants of this parameter.     

Le cylindre des langages linéaires

Define a cylinder to be a family of languages which is closed under inverse homomorphisms and intersection with regular sets. A number of well-known families of languages are cylinders:

—CFL, the family of context-free languages, is a principal cylinder, i.e. the smallest cylinder containing a languageL _O described in [6].

—the family of deterministic context-free languages is proved to be a nonprincipal cylinder in [7].

—the family of unambiguous context-free languages is a cylinder: to prove that it is not principal seems to be a very hard problem.

In this paper we prove that Lin, the family of linear context-free languages, is a nonprincipal cylinder. This is achieved in the standard way by exhibiting a sequence of languages S_n, n∈N, such that Lin is the union of all the principal cylinders generated by these languages and is not the union of any finite number of these cylinders. This leaves open the problem raised by Sheila Greibach of whether there exists a languageL such that every linear context-free language is the image ofL in some inverse gsm mapping.     

Average time behavior of distributive sorting algorithms

In this paper we investigate the expected complexityE(C) of distributive (“bucket”) sorting algorithms on a sampleX ₁, ...,X _n drawn from a densityf onR ¹. Assuming constant time bucket membership determination and assuming the use of an average timeg(n) algorithm for subsequent sorting within each bucket (whereg is convex,g(n)/n↑∞,g(n)/n ² is nonincreasing andg is independent off), the following is shown:

1. Iff has compact support, then ∫g(f(x))dx<∞ if and only ifE(C)=0(n).
2. Iff does not have compact support, then \(E(C)/n\xrightarrow{n}\infty \) .

No additional restrictions are put onf.     

Association Fields via Cuspless Sub-Riemannian Geodesics in SE(2)

To model association fields that underly perceptional organization (gestalt) in psychophysics we consider the problem P _curve of minimizing $\int _{0}^{\ell} \sqrt{\xi^{2} +\kappa^{2}(s)} {\rm d}s $ for a planar curve having fixed initial and final positions and directions. Here κ(s) is the curvature of the curve with free total length ?. This problem comes from a model of geometry of vision due to Petitot (in J. Physiol. Paris 97:265–309, 2003; Math. Inf. Sci. Humaines 145:5–101, 1999), and Citti & Sarti (in J. Math. Imaging Vis. 24(3):307–326, 2006). In previous work we proved that the range $\mathcal{R} \subset\mathrm{SE}(2)$ of the exponential map of the underlying geometric problem formulated on SE(2) consists of precisely those end-conditions (x _fin,y _fin,θ _fin) that can be connected by a globally minimizing geodesic starting at the origin (x _in,y _in,θ _in)=(0,0,0). From the applied imaging point of view it is relevant to analyze the sub-Riemannian geodesics and $\mathcal{R}$ in detail. In this article we

• show that $\mathcal{R}$ is contained in half space x≥0 and (0,y _fin)≠(0,0) is reached with angle π,
• show that the boundary $\partial\mathcal{R}$ consists of endpoints of minimizers either starting or ending in a cusp,
• analyze and plot the cones of reachable angles θ _fin per spatial endpoint (x _fin,y _fin),
• relate the endings of association fields to $\partial\mathcal {R}$ and compute the length towards a cusp,
• analyze the exponential map both with the common arc-length parametrization t in the sub-Riemannian manifold $(\mathrm{SE}(2),\mathrm{Ker}(-\sin\theta{\rm d}x +\cos\theta {\rm d}y), \mathcal{G}_{\xi}:=\xi^{2}(\cos\theta{\rm d}x+ \sin\theta {\rm d}y) \otimes(\cos\theta{\rm d}x+ \sin\theta{\rm d}y) + {\rm d}\theta \otimes{\rm d}\theta)$ and with spatial arc-length parametrization s in the plane $\mathbb{R}^{2}$ . Surprisingly, s-parametrization simplifies the exponential map, the curvature formulas, the cusp-surface, and the boundary value problem,
• present a novel efficient algorithm solving the boundary value problem,
• show that sub-Riemannian geodesics solve Petitot’s circle bundle model (cf. Petitot in J. Physiol. Paris 97:265–309, [2003]),
• show a clear similarity with association field lines and sub-Riemannian geodesics.

     

On Bounded Rational Trace Languages

In this paper, for a finitely generated monoid M, we tackle the following three questions:

1. Is it possible to give a characterization of rational subsets of M which have polynomial growth?
2. What is the structure of the counting function of rational sets which have polynomial growth?
3. Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds?

We give a positive answer to all the previous questions in the case that M is a direct product of free monoids. Some of the proved results also extend to trace monoid.     

Two-Way Automata Versus Logarithmic Space

We strengthen a previously known connection between the size complexity of two-way finite automata ( ) and the space complexity of Turing machines (tms). Specifically, we prove that

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL?L/poly, and

every s-state has a poly(s)-state that agrees with it on all inputs of length ≤2 ^s if and only if NLL?LL/polylog.

Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice.     

The Kissing Problem: How to End a Gathering When Everyone Kisses Everyone Else Goodbye

This paper introduces the kissing problem: given a rectangular room with n people in it, what is the most efficient way for each pair of people to kiss each other goodbye? The room is viewed as a set of pixels that form a subset of the integer grid. At most one person can stand on a pixel at once, and people move horizontally or vertically. In order to move into a pixel in time step t, the pixel must be empty in time step t?1. The paper gives one algorithm for kissing everyone goodbye.

1. This algorithm is a 4+o(1)-approximation algorithm in a crowded room (e.g., only one unoccupied pixel).
2. It is a 45+o(1)-approximation algorithm for kissing in a comfortable room (e.g., at most half the pixels are empty).
3. It is a 25+o(1)-approximation for kissing in a sparse room (more than half the pixels are empty) with two people abutting the far walls of the room.

This paper gives optimal solutions for small cases, which were found using a heuristic state space search (IDA*).     

Collecting coupons on trees,and the cover time of random walks

We consider the cover timeE _u [G], the expected time it takes a random walk that starts at vertexu to visit alln vertices of a connected graphG. Aleliunas et al introduced the spanning tree argument: for any spanning treeT of the graphG, E _u [G]≤W[T], whereW[T] is the sum of commute times along the edges ofT. By refining the spanning tree argument we obtain: $$E_u [G] \leqslant \frac{1}{2}(\mathop {\min }\limits_T [W[T]] + \mathop {\max }\limits_{\upsilon \in G} [H[u,\upsilon ] - H[\upsilon ,u]])$$ whereH[u,v] is the hitting time fromu tov. We use this bound to show:

1. max _G min _u E _u [G]=(1+o(1))2n ³/27. This answers an open question of Aldous.
2. Then-path is then-vertex tree on which the cover time is maximized. This confirms a conjecture of Brightwell and Winkler.
3. For regular graphs,E _u [G]<2n ². This improves the leading constant in previously known upper bounds.

We also provide upper bounds onE _u ⁺ [G], the expected time to coverG and return tou.     

Contrary to time conditionals in Talmudic logic

We consider conditionals of the form A ? B where A depends on the future and B on the present and past. We examine models for such conditional arising in Talmudic legal cases. We call such conditionals contrary to time conditionals. Three main aspects will be investigated:

1. Inverse causality from future to past, where a future condition can influence a legal event in the past (this is a man made causality).
2. Comparison with similar features in modern law.
3. New types of temporal logics arising from modelling the Talmudic examples.

We shall see that we need a new temporal logic,which we call Talmudic temporal logic with linear open advancing future and parallel changing past, based on two parameters for time.     

Sweep methods for parallel computational geometry

In this paper we give efficient parallel algorithms for a number of problems from computational geometry by using versions of parallel plane sweeping. We illustrate our approach with a number of applications, which include:

General hidden-surface elimination (even if the overlap relation contains cycles).

CSG boundary evaluation.

Computing the contour of a collection of rectangles.

Hidden-surface elimination for rectangles.

There are interesting subproblems that we solve as a part of each parallelization. For example, we give an optimal parallel method for building a data structure for line-stabbing queries (which, incidentally, improves the sequential complexity of this problem). Our algorithms are for the CREW PRAM, unless otherwise noted.