Parameterized complexity of coloring problems: Treewidth versus vertex cover

We compare the fixed parameter complexity of various variants of coloring problems (including List Coloring, Precoloring Extension, Equitable Coloring, L(p,1)-Labeling and Channel Assignment) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.     

NC图形验证与仿真技术的研究概况

数控程序图形验证与仿真技术的研究对保证加工质量提高加工效率具有重要意义,同时也是虚拟制造技术的主要研究内容之一,该文从国外NC几何验证、NC物理验证以及我国的NC图形验证三个方面对NC图形验证技术的发展概况作了较全面的论述,并指出其中存在的不足和尚待解决的问题。最后提出一种新的复杂曲面NC图形验证的体系结构。     

Convergence analysis of convex incremental neural networks

Recently, a convex incremental algorithm (CI-ELM) has been proposed in Huang and Chen (Neurocomputing 70:3056–3062, 2007), which randomly chooses hidden neurons and then analytically determines the output weights connecting with the hidden layer and the output layer. Though hidden neurons are generated randomly, the network constructed by CI-ELM is still based on the principle of universal approximation. The random approximation theory breaks through the limitation of most conventional theories, eliminating the need for tuning hidden neurons. However, due to the random characteristic, some of the neurons contribute little to decrease the residual error, which eventually increase the complexity and computation of neural networks. Thus, CI-ELM cannot precisely give out its convergence rate. Based on Lee’s results (Lee et al., IEEE Trans Inf Theory 42(6):2118–2132, 1996), we first show the convergence rate of a maximum CI-ELM, and then systematically analyze the convergence rate of an enhanced CI-ELM. Different from CI-ELM, the hidden neurons of the two algorithms are chosen by following the maximum or optimality principle under the same structure as CI-ELM. Further, the proof process also demonstrates that our algorithms achieve smaller residual errors than CI-ELM. Since the proposed neural networks remove these “useless” neurons, they improve the efficiency of neural networks. The experimental results on benchmark regression problems will support our conclusions. The work is under the funding of Singapore MOE AcRF Tier 1 grant WBS No: R 252-000-221-112.     

An adaptive learning approach for 3-D surface reconstruction from point clouds.

In this paper, we propose a multiresolution approach for surface reconstruction from clouds of unorganized points representing an object surface in 3-D space. The proposed method uses a set of mesh operators and simple rules for selective mesh refinement, with a strategy based on Kohonen's self-organizing map (SOM). Basically, a self-adaptive scheme is used for iteratively moving vertices of an initial simple mesh in the direction of the set of points, ideally the object boundary. Successive refinement and motion of vertices are applied leading to a more detailed surface, in a multiresolution, iterative scheme. Reconstruction was experimented on with several point sets, including different shapes and sizes. Results show generated meshes very close to object final shapes. We include measures of performance and discuss robustness.     

The Power of Nondeterminism and Randomness for Oblivious Branching Programs

Abstract. This paper abstracts and generalizes the known approaches for proving lower bounds on the size of various variants of oblivious branching programs (oblivious BPs for short), providing an easy-to-use technique which works for all nondeterministic and randomized modes of acceptance. The technique is applied to obtain the following results concerning the power of nondeterminism and randomness for oblivious BPs: <p>— Oblivious read-once BPs, better known as OBDDs (ordered binary decision diagrams), are used in many applications and their structure is well understood in the deterministic case. It has been open so far to compare the power of nondeterministic OBDDs with so-called partitioned BDDs which are a variant of nondeterministic branching programs also used in practice. A k -partitioned BDD has a nondeterministic node at the top by which one out of k deterministic OBDDs with possibly different variable orders is chosen. It is proven here that the two models are incomparable as long as k is bounded by a logarithmic function in the input length. <p>— It is shown that deterministic oblivious read-k -times BPs for an explicitly defined function require superpolynomial size, for k logarithmic in the input length, while there are Las Vegas oblivious read-twice BPs of linear size for this function. This is in contrast to the situation for OBDDs, for which the respective size measures are polynomially related. <p>— Furthermore, an explicitly defined function is presented for which randomized oblivious read-k -times BPs with bounded error require exponential size, while the function as well as its complement can be represented in polynomial size by nondeterministic oblivious read-k -times BPs and deterministic oblivious read-(k+1) -times BPs, where k=o(log n) .     

Detection and Tracking of Multiple,Partially Occluded Humans by Bayesian Combination of Edgelet based Part Detectors

Detection and tracking of humans in video streams is important for many applications. We present an approach to automatically detect and track multiple, possibly partially occluded humans in a walking or standing pose from a single camera, which may be stationary or moving. A human body is represented as an assembly of body parts. Part detectors are learned by boosting a number of weak classifiers which are based on edgelet features. Responses of part detectors are combined to form a joint likelihood model that includes an analysis of possible occlusions. The combined detection responses and the part detection responses provide the observations used for tracking. Trajectory initialization and termination are both automatic and rely on the confidences computed from the detection responses. An object is tracked by data association and meanshift methods. Our system can track humans with both inter-object and scene occlusions with static or non-static backgrounds. Evaluation results on a number of images and videos and comparisons with some previous methods are given. Electronic Supplementary Material Supplementary material is available in the online version of this article at     

Poetics of performative space

The TGarden is a genre of responsive environment in which actor–spectators shape dense media sensitive to their movements. These dense fields of light, sound, and material also evolve according to their own composed dynamics, so the agency is distributed throughout the multiple media. These TGardens explore open-ended questions like the following: what makes some time-based, responsive environments compelling, and others flat? How can people improvise gestures without words, that are individually or collectively meaningful? When and how is a movement intentional, or collectively intentional? This paper introduces what has been at stake behind the experimental work: subjectivation, moving from technologies of representation to technologies of performance, and the potential for ethico-aesthetic novelty.     

The tauola-photos-F environment for the TAUOLA and PHOTOS packages, release II

We present the system for maintaining the versions of two packages: the TAUOLA of τ-lepton decay and PHOTOS for radiative corrections in decays. The following features can be chosen in an automatic or semi-automatic way: (1) format of the common block HEPEVT; (2) version of the physics input (for TAUOLA): as published, as initialized by the CLEO collaboration, as initialized by the ALEPH collaboration (it is suggested to use this version only with the help of the collaboration advice), new optional parametrization of matrix elements in 4π decay channels; (3) type of application: stand-alone, universal interface based on the information stored in the HEPEVT common block including longitudinal spin effects in the elementary Z/γ^∗→τ⁺τ⁻ process, extended version of the standard universal interface including full spin effects in the H/A→τ⁺τ⁻ decay, interface for KKMC Monte Carlo, (4) random number generators; (5) compiler options. The last section of the paper contains documentation of the programs updates introduced over the last two years.

Program summary

Title of program:tauola-photos-F, release IICatalogue identifier:ADXO_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXO_v1_0Programs obtainable from: CPC Program Library, Queen's University of Belfast, N. IrelandComputer: PC running GNU/Linux operating systemProgramming languages and tools used:CPP: standard C-language preprocessor, GNU Make builder tool, also FORTRAN compilerNo. of lines in distributed program, including test data, etc.: 194 118No. of bytes in distributed program, including test data, etc.:2 481 234Distribution format: tar.gzCatalogue identifier:ADXO_v2_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/ADXO_v2_0No. of lines in distributed program, including test data, etc.:308 235No. of bytes in distributed program, including test data, etc.:2 988 363Distribution format:tar.gzDoes the new version supersede the previous version:YesNature of the physical problem: The code of Monte Carlo generators often has to be tuned to the needs of large HEP Collaborations and experiments. Usually, these modifications do not introduce important changes in the algorithm, but rather modify the initialization and form of the hadronic current in τ decays. The format of the event record (HEPEVT common block) used to exchange information between building blocks of Monte Carlo systems often needs modification. Thus, there is a need to maintain various, slightly modified versions of the same code. The package presented here allows the production of ready-to-compile versions of TAUOLA [S. Jadach, Z. Wa?s, R. Decker, J.H. Kühn, Comput. Phys. Comm. 76 (1993) 361; A.E. Bondar, et al., Comput. Phys. Comm. 146 (2002) 139] and PHOTOS [E. Barberio, Z. Wa?s, Comput. Phys. Comm. 79 (1994) 291] Monte Carlo generators with appropriate demonstration programs. The new algorithm, universal interface of TAUOLA to work with the HEPEVT common block, is also documented here. Finally, minor technical improvements of TAUOLA and PHOTOS are also listed.Method of solution: The standard UNIX tool: the C-language preprocessor is used to produce a ready-to-distribute version of TAUOLA and PHOTOS code. The final FORTRAN code is produced from the library of ‘pre-code’ that is included in the package.Reasons for new version: The functionality of the version of TAUOLA and PHOTOS changed over the last two years. The changes, and their reasons, are documented in Section 9, and our new papers cited in this section.Additional comments: The updated version includes new features described in Section 9 of the paper. PHOTOS and TAUOLA were first submitted to the library as separate programs. Summary details of these previous programs are obtainable from the CPC Program Library.Typical running time: Depends on the speed of the computer used and the demonstration program chosen. Typically a few seconds.