The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC⁰, and thus cannot be hard for AC⁰(2) or any superclass like NC¹, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP. Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174.     

Analysis of Galerkin Methods for the Fully Nonlinear Monge-Ampère Equation

This paper develops and analyzes finite element Galerkin and spectral Galerkin methods for approximating viscosity solutions of the fully nonlinear Monge-Ampère equation det (D ² u ⁰)=f (>0) based on the vanishing moment method which was developed by the authors in Feng and Neilan (J. Sci. Comput. 38:74–98, 2009) and Feng (Convergence of the vanishing moment method for the Monge-Ampère equation, submitted). In this approach, the Monge-Ampère equation is approximated by the fourth order quasilinear equation −εΔ² u ^ε +det D ² u ^ε =f accompanied by appropriate boundary conditions. This new approach enables us to construct convergent Galerkin numerical methods for the fully nonlinear Monge-Ampère equation (and other fully nonlinear second order partial differential equations), a task which has been impracticable before. In this paper, we first develop some finite element and spectral Galerkin methods for approximating the solution u ^ε of the regularized problem. We then derive optimal order error estimates for the proposed numerical methods. In particular, we track explicitly the dependence of the error bounds on the parameter ε, for the error u^e-u^e_hu^{\varepsilon}-u^{\varepsilon}_{h}. Due to the strong nonlinearity of the underlying equation, the standard error estimate technique, which has been widely used for error analysis of finite element approximations of nonlinear problems, does not work here. To overcome the difficulty, we employ a fixed point technique which strongly makes use of the stability property of the linearized problem and its finite element approximations. Finally, using the Argyris finite element method as an example, we present a detailed numerical study of the rates of convergence in terms of powers of ε for the error u⁰-u_h^eu^{0}-u_{h}^{\varepsilon}, and numerically examine what is the “best” mesh size h in relation to ε in order to achieve these rates.     

Circuit Complexity of Regular Languages

We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC⁰ and ACC⁰ are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222–234, 1985). As a consequence we obtain that in order to separate ACC⁰ from NC¹ it suffices to prove for some ε>0 an Ω(n ^1+ε ) lower bound on the size of ACC⁰ circuits computing certain NC¹-complete functions. Partially supported by grant GA ČR 201/07/P276, project No. 1M0021620808 of MŠMT ČR and Institutional Research Plan No. AV0Z10190503.     

Efficiently Testing Sparse <Emphasis Type="Italic">GF</Emphasis>(2) Polynomials

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1} ⁿ →{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε.     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

Fast Dynamic Transitive Closure with Lookahead

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n ^{ω(1,1,ε)−ε} ) time given a lookahead of n ^ε operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n ^ε matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n ^2−ε ) time, whereas for ε=1 the time is O(n ^ω−1). This is essentially optimal as it implies an O(n ^ω ) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n^\fracw2)O(n^{\frac{\omega}{2}}) time to process n^\frac12n^{\frac{1}{2}} operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.     

Practical Methods for Shape Fitting and Kinetic Data Structures using Coresets

The notion of ε-kernel was introduced by Agarwal et al. (J. ACM 51:606–635, 2004) to set up a unified framework for computing various extent measures of a point set P approximately. Roughly speaking, a subset Q⊆P is an ε-kernel of P if for every slab W containing Q, the expanded slab (1+ε)W contains P. They illustrated the significance of ε-kernel by showing that it yields approximation algorithms for a wide range of geometric optimization problems. We present a simpler and more practical algorithm for computing the ε-kernel of a set P of points in ℝ ^d . We demonstrate the practicality of our algorithm by showing its empirical performance on various inputs. We then describe an incremental algorithm for fitting various shapes and use the ideas of our algorithm for computing ε-kernels to analyze the performance of this algorithm. We illustrate the versatility and practicality of this technique by implementing approximation algorithms for minimum enclosing cylinder, minimum-volume bounding box, and minimum-width annulus. Finally, we show that ε-kernels can be effectively used to expedite the algorithms for maintaining extents of moving points. A preliminary version of the paper appeared in Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 2004, pp. 263–272. Research by the first two authors is supported by NSF under grants CCR-00-86013, EIA-98-70724, EIA-01-31905, and CCR-02-04118, and by a grant from the US–Israel Binational Science Foundation. Research by the fourth author is supported by NSF CAREER award CCR-0237431.     

A family of non-conforming elements and the analysis of Nitsche’s method for a singularly perturbed fourth order problem

In this paper we address several issues arising from a singularly perturbed fourth order problem with small parameter ε. First, we introduce a new family of non-conforming elements. We then prove that the corresponding finite element method is robust with respect to the parameter ε and uniformly convergent to order h ^1/2. In addition, we analyze the effect of treating the Neumann boundary condition weakly by Nitsche’s method. We show that such treatment is superior when the parameter ε is smaller than the mesh size h and obtain sharper error estimates. Such error analysis is not restricted to the proposed elements and can easily be carried out to other elements as long as the Neumann boundary condition is imposed weakly. Finally, we discuss the local error estimates and the pollution effect of the boundary layers in the interior of the domain.     

The Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem

A modified fast approximation algorithm for the 0-1 knapsack problem with improved complexity is presented, based on the schemes of Ibarra, Kim and Babat. By using a new partition of items, the algorithm solves the n -item 0-1 knapsack problem to any relative error tolerance ε > 0 in the scaled profit space P ^* /K = O ( 1/ ε ^1+δ ) with time O(n log(1/ ε )+1/ ε^{2+2δ}) and space O(n +1/ ɛ^{2+δ}), where P^{*} and b are the maximal profit and the weight capacity of the knapsack problem, respectively, K is a problem-dependent scaling factor, δ={α}/(1+α) and α=O( log b ). This algorithm reduces the exponent of the complexity bound in [5].     

Approximations for optimal stopping of a piecewise-deterministic process

This paper deals with approximation techniques for the optimal stopping of a piecewise-deterministic Markov process (P.D.P.). Such processes consist of a mixture of deterministic motion and random jumps. In the first part of the paper (Section 3) we study the optimal stopping problem with lower semianalytic gain function; our main result is the construction of ε-optimal stopping times. In the second part (Section 4) we consider a P.D.P. satisfying some smoothness conditions, and forN integer we construct a discretized P.D.P. which retains the main characteristics of the original process. By iterations of the single jump operator from ℝ ^N to ℝ ^N , each iteration consisting ofN one-dimensional minimizations, we can calculate the payoff function of the discretized process. We demonstrate the convergence of the payoff functions, and for the case when the state space is compact we construct ε-optimal stopping times for the original problem using the payoff function of the discretized problem. A numerical example is presented.     

On truthfulness and approximation for scheduling selfish tasks

We consider the problem of designing truthful mechanisms for scheduling n tasks on a set of m parallel related machines in order to minimize the makespan. In what follows, we consider that each task is owned by a selfish agent. This is a variant of the KP-model introduced by Koutsoupias and Papadimitriou (Proc. of STACS 1999, pp. 404–413, 1999) (and of the CKN-model of Christodoulou et al. in Proc. of ICALP 2004, pp. 345–357, 2004) in which the agents cannot choose the machine on which their tasks will be executed. This is done by a centralized authority, the scheduler. However, the agents may manipulate the scheduler by providing false information regarding the length of their tasks. We introduce the notion of increasing algorithm and a simple reduction that transforms any increasing algorithm into a truthful one. Furthermore, we show that some of the classical scheduling algorithms are indeed increasing: the LPT algorithm, the PTAS of Graham (SIAM J. Appl. Math. 17(2):416–429, 1969) in the case of two machines, as well as a simple PTAS for the case of m machines, with m a fixed constant. Our results yield a randomized r(1+ε)-approximation algorithm where r is the ratio between the largest and the smallest speed of the related machines. Furthermore, by combining our approach with the classical result of Shmoys et al. (SIAM J. Comput. 24(6):1313–1331, 1995), we obtain a randomized 2r(1+ε)-competitive algorithm. It has to be noticed that these results are obtained without payments, unlike most of the existing works in the field of Mechanism Design. Finally, we show that if payments are allowed then our approach gives a (1+ε)-algorithm for the off-line case with related machines.     

Indexing Factors with Gaps

Indexing of factors or substrings is a widely used and useful technique in stringology and can be seen as a tool in solving diverse text algorithmic problems. A gapped-factor is a concatenation of a factor of length k, a gap of length d and another factor of length k′. Such a gapped factor is called a (k−d−k′)-gapped-factor. The problem of indexing the gapped-factors was considered recently by Peterlongo et al. (In: Stringology, pp. 182–196, 2006). In particular, Peterlongo et al. devised a data structure, namely a gapped factor tree (GFT) to index the gapped-factors. Given a text of length n over the alphabet Σ and the values of the parameters k, d and k′, the construction of GFT requires O(n|Σ|) time. Once GFT is constructed, a given (k−d−k′)-gapped-factor can be reported in O(k+k′+Occ) time, where Occ is the number of occurrences of that factor in  . In this paper, we present a new improved indexing scheme for the gapped-factors. The improvements we achieve come from two aspects. Firstly, we generalize the indexing data structure in the sense that, unlike GFT, it is independent of the parameters k and k′. Secondly, our data structure can be constructed in O(nlog ^1+ε n) time and space, where 0<ε<1. The only price we pay is a slight increase, i.e. an additional log log n term, in the query time. Preliminary version appeared in [29]. C.S. Iliopoulos is supported by EPSRC and Royal Society grants. M.S. Rahman is supported by the Commonwealth Scholarship Commission in the UK under the Commonwealth Scholarship and Fellowship Plan (CSFP). M.S. Rahman is on leave from Department of CSE, BUET, Dhaka 1000, Bangladesh.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Nodal Superconvergence of SDFEM for Singularly Perturbed Problems

In this paper, we analyze the streamline diffusion finite element method for one dimensional singularly perturbed convection-diffusion-reaction problems. Local error estimates on a subdomain where the solution is smooth are established. We prove that for a special group of exact solutions, the nodal error converges at a superconvergence rate of order (ln ε ⁻¹/N)^2k (or (ln N/N)^2k ) on a Shishkin mesh. Here ε is the singular perturbation parameter and 2N denotes the number of mesh elements. Numerical results illustrating the sharpness of our theoretical findings are displayed.     

Activatable tiles for compact robust programmable molecular assembly and other applications

Algorithmic DNA self-assembly is capable of forming complex patterns and shapes, that have been shown theoretically, and experimentally. Its experimental demonstrations, although improving over recent years, have been limited by significant assembly errors. Since 2003 there have been several designs of error-resilient tile sets but all of these existing error-resilient tile systems assumed directional growth of the tiling assembly. This is a very strong assumption because experiments show that tile self-assembly does not necessarily behave in such a fashion, since they may also grow in the reverse of the intended direction. The assumption of directional growth of the tiling assembly also underlies the growth model in theoretical assembly models such as the TAM. What is needed is a means for enforce this directionality constraint, which will allow us to reduce assembly errors. In this paper we describe a protection/deprotection strategy to strictly enforce the direction of tiling assembly growth so that the assembly process is robust against errors. Initially, we start with (1) a single “activated” tile with output pads that can bind with other tiles, along with (2) a set of “deactivated” tiles, meaning that the tile’s output pads are protected and cannot bind with other tiles. After other tiles bind to a “deactivated” tile’s input pads, the tile transitions to an active state and its output pads are exposed, allowing further growth. When these are activated in a desired order, we can enforce a directional assembly at the same scale as the original one. Such a system can be built with minimal modifications of existing DNA tile nanostructures. We propose a new type of tiles called activatable tiles and its role in compact proofreading. Activatable tiles can be thought of as a particular case of the more recent signal tile assembly model, where signals transmit binding/unbinding instructions across tiles on binding to one or more input sites. We describe abstract and kinetic models of activatable tile assembly and show that the error rate can be decreased significantly with respect to Winfree’s original kinetic tile assembly model without considerable decrease in assembly growth speed. We prove that an activatable tile set is an instance of a compact, error-resilient and self-healing tile-set. We describe a DNA design of activatable tiles and a mechanism of deprotection using DNA polymerization and strand displacement. We also perform detailed stepwise simulations using a DNA Tile simulator Xgrow, and show that the activatable tiles mechanism can reduce error rates in self assembly. We conclude with a brief discussion on some applications of activatable tiles beyond computational tiling, both as (1) a novel system for concentration of molecules, and (2) a catalyst in sequentially triggered chemical reactions.     

Viscous heating in nanoscale shear driven liquid flows

Three-dimensional Molecular Dynamics (MD) simulations of heat and momentum transport in liquid Argon filled shear-driven nano-channels are performed using 6–12 Lennard–Jones potential interactions. Work done by the viscous stresses heats the fluid, which is dissipated through the channel walls, maintained at isothermal conditions through a recently developed interactive thermal wall model. Shear driven nano-flows for weak wetting surfaces (ε _wf /ε ≤ 0.6) are investigated. Spatial variations in the fluid density, kinematic viscosity, shear- and energy dissipation rates are presented. Temperature profiles in the nano-channel are obtained as a function of the surface wettability, shear rate and the intermolecular stiffness of wall molecules. The energy dissipation rate is almost a constant for ε _wf /ε ≤ 0.6, which results in parabolic temperature profiles in the domain with temperature jumps due to the well known Kapitza resistance at the liquid/solid interfaces. Using the energy dissipation rates predicted by MD simulations and the continuum energy equation subjected to the temperature jump boundary conditions developed in [Kim et al. Journal of Chemical Physics, 129, 174701, 2008b], we obtain analytical solutions for the temperature profiles, which agree well with the MD results.     

On the correlation of symmetric functions

Thecorrelation between two Boolean functions ofn inputs is defined as the number of times the functions agree minus the number of times they disagree, all divided by 2 ⁿ . In this paper we compute, in closed form, the correlation between any twosymmetric Boolean functions. As a consequence of our main result, we get that every symmetric Boolean function having an odd period has anexponentially small correlation (inn) with the parity function. This improves a result of Smolensky [12] restricted to symmetric Boolean functions: the correlation between parity and any circuit consisting of a Mod _q gate over AND gates of small fan-in, whereq is odd and the function computed by the sum of the AND gates is symmetric, is bounded by 2^−Ω(n). In addition, we find that for a large class of symmetric functions the correlation with parity isidentically zero for infinitely manyn. We characterize exactly those symmetric Boolean functions having this property. This research was supported in part by NSF Grant CCR-9057486. Jin-Yi Cai was supported in part by an Alfred T. Sloan Fellowship in computer science. The work of F. Green was done in part while visiting Princeton University, while the work of T. Thierauf was done in part while visiting Princeton University and the University of Rochester. The third author was supported in part by DFG Postdoctoral Stipend Th 472/1-1 and by NSF Grant CCR-8957604.     

Lattice constants matricial equations for conversion matrices

In this paper we proof a theorem concerning lattice constants and hence three matricial equations for conversion matricesR: if H=Δ^RT we have: i)H ³ =I; ii) H^T Σ H= Σ; iii)(DH) ² =I; where Δ,D, and ε are known when we can enumerate all non-isomorphic graphs withn vertices, we know (for Δ and ε) their edge-number and (for ε) the order of their automorphism group.     

Grouping Techniques for Scheduling Problems: Simpler and Faster

In this paper we describe a general grouping technique to devise faster and simpler approximation schemes for several scheduling problems. We illustrate the technique on two different scheduling problems: scheduling on unrelated parallel machines with costs and the job shop scheduling problem. The time complexity of the resulting approximation schemes is always linear in the number n of jobs, and the multiplicative constant hidden in the O(n) running time is reasonably small and independent of the error ε. Supported by Swiss National Science Foundation project 200020-109854, “Approximation Algorithms for Machine scheduling Through Theory and Experiments II”. A preliminary version of this paper appeared in the Proceedings of ESA’01.     

On the isomorphism problem of concept algebras

Weakly dicomplemented lattices are bounded lattices equipped with two unary operations to encode a negation on concepts. They have been introduced to capture the equational theory of concept algebras (Wille 2000; Kwuida 2004). They generalize Boolean algebras. Concept algebras are concept lattices, thus complete lattices, with a weak negation and a weak opposition. A special case of the representation problem for weakly dicomplemented lattices, posed in Kwuida (2004), is whether complete weakly dicomplemented lattices are isomorphic to concept algebras. In this contribution we give a negative answer to this question (Theorem 4). We also provide a new proof of a well known result due to M.H. Stone (Trans Am Math Soc 40:37–111, 1936), saying that each Boolean algebra is a field of sets (Corollary 4). Before these, we prove that the boundedness condition on the initial definition of weakly dicomplemented lattices (Definition 1) is superfluous (Theorem 1, see also Kwuida (2009)).