Complexity of Hard-Core Set Proofs

We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}ⁿ?{0,1}{f:\{0,1\}^n\to\{0,1\}} which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size s￠=O(s/(\frac1e²log(\frac1ed))){s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))} must disagree with f on at least (1-e)/2{(1-\epsilon)/2} fraction of inputs from H.     

Distributed discovery of large near-cliques

Given an undirected graph and 0 ￡ e ￡ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant probability of success, a linear size e{\epsilon}-near clique if there exists an e³{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n ^−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of size Ω(n/(log log n) ^α ) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting.     

Coalition formation for task allocation: theory and algorithms

This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of O(m^1-e){O(m^{1-\epsilon})} for all ${\epsilon > 0}${\epsilon > 0}. Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor, for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus’ algorithm (Artif Intell 101(1–2):165–200, 1998), which provides guarantee’s on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent domains is a modification of and has the same running time as Shehory and Kraus’ algorithm, while our approach for multi-robot domains runs in time O(n^\frac32m){O(n^{\frac{3}{2}}m)}, much faster than Vig and Adams (J Intell Robot Syst 50(1):85–118, 2007) modifications to Shehory and Kraus’ algorithm for multi-robot domains, which ran in time O(n ^k m), for n agents and m tasks.     

Approximate Pattern Matching with the <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>, <Emphasis Type="Italic">L</Emphasis><Subscript>2</Subscript> and <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> Metrics

Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ ⁿ and a pattern string P∈Σ ^m , for each i=1,2,…,n−m+1 define L _p (i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L _p distance is to compute L _p (i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L ₁ matching (pattern matching with an L ₁ distance) we show a reduction of the string matching with mismatches problem to the L ₁ matching problem and we present an algorithm that approximates the L ₁ matching up to a factor of 1+ε, which has an O(\frac1e²nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|) run time. Then, the L ₂ matching problem (pattern matching with an L ₂ distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L _∞ matching up to a factor of 1+ε with a run time of O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|) . We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog ⁴ m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric.     

When Does Eddy Viscosity Damp Subfilter Scales Sufficiently?

Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore, in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size smaller than Δ initially. From this we deduce that the eddy viscosity ν _e has to depend on the invariants q = \frac12tr(S²)q = \frac{1}{2}\mathrm{tr}(S^{2}) and r = -\frac13tr(S³)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by n_e = \frac32(D/p)² |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re  _τ =590).     

Nonclairvoyant Speed Scaling for Flow and Energy

We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s ^α , LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and \frac2a²lna\frac{2\alpha^{2}}{\ln\alpha} for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s ^α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive.     

The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions

We prove asymptotically optimal bounds on the Gaussian noise sensitivity and Gaussian surface area of degree-d polynomial threshold functions. In particular, we show that for f a degree-d polynomial threshold function that the Gaussian noise sensitivity of f with parameter e{\epsilon} is at most \fracdarcsin(?{2e-e²})p{\frac{d\arcsin\left(\sqrt{2\epsilon-\epsilon^2}\right)}{\pi}} . This bound translates into an optimal bound on the Gaussian surface area of such functions, namely that the Gaussian surface area is at most \fracd?{2p}{\frac{d}{\sqrt{2\pi}}} . Finally, we note that the later result implies bounds on the runtime of agnostic learning algorithms for polynomial threshold functions.     

Fast primal-dual distributed algorithms for scheduling and matching problems

In this paper we give efficient distributed algorithms computing approximate solutions to general scheduling and matching problems. All approximation guarantees are within a constant factor of the optimum. By “efficient”, we mean that the number of communication rounds is poly-logarithmic in the size of the input. In the scheduling problem, we have a bipartite graph with computing agents on one side and resources on the other. Agents that share a resource can communicate in one time step. Each agent has a list of jobs, each with its own length and profit, to be executed on a neighbouring resource within a given time-window. Each job is also associated with a rational number in the range between zero and one (width), specifying the amount of resource required by the job. Resources can execute non preemptively multiple jobs whose total width at any given time is at most one. The goal is to maximize the profit of the jobs that are scheduled. We then adapt our algorithm for scheduling, to solve the weighted b-matching problem, which is the generalization of the weighted matching problem where for each vertex v, at most b(v) edges incident to v, can be included in the matching. For this problem we obtain a randomized distributed algorithm with approximation guarantee of \frac16+e{\frac{1}{6+\epsilon}}, for any ${\epsilon >0 }${\epsilon >0 }. For weighted matching, we devise a deterministic distributed algorithm with the same approximation ratio. To our knowledge, we give the first distributed algorithm for the aforementioned scheduling problem as well as the first deterministic distributed algorithm for weighted matching with poly-logaritmic running time. A very interesting feature of our algorithms is that they are all derived in a systematic manner from primal-dual algorithms.     

Entanglement and Berry phase in a 9 × 9 Yang–Baxter system

A M-matrix which satisfies the Hecke algebraic relations is presented. Via the Yang–Baxterization approach, we obtain a unitary solution \breveR(q,j₁,j₂){\breve{R}(\theta,\varphi_{1},\varphi_{2})} of Yang–Baxter equation. It is shown that any pure two-qutrit entangled states can be generated via the universal \breveR{\breve{R}}-matrix assisted by local unitary transformations. A Hamiltonian is constructed from the \breveR{\breve{R}}-matrix, and Berry phase of the Yang–Baxter system is investigated. Specifically, for j₁ = j₂{\varphi_{1}\,{=}\,\varphi_{2}}, the Hamiltonian can be represented based on three sets of SU(2) operators, and three oscillator Hamiltonians can be obtained. Under this framework, the Berry phase can be interpreted.     

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of 3\frac1318 n² + O(n){3\frac{13}{18} n^2 + O(n)} for the complexity of this algorithm. We also show a lower bound of 1\frac56 n² - O(n){1\frac{5}{6} n^2 - O(n)} for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of \frac56 n² + O(n){\frac{5}{6} n^2 + O(n)} for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5\frac34n²+O(n){5\frac{3}{4}n^2+O(n)} and a lower bound of \frac18n²-O(n){\frac{1}{8}n^2-O(n)} for its stabilization time. For this algorithm we prove an upper bound of 1\frac12n² + O(n){1\frac{1}{2}n^2 + O(n)} and show a lower bound of n ²−O(n). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.     

Testing Periodicity

We study the string-property of being periodic and having periodicity smaller than a given bound. Let Σ be a fixed alphabet and let p,n be integers such that p ￡ \fracn2p\leq \frac{n}{2} . A length-n string over Σ, α=(α ₁,…,α _n ), has the property Period(p) if for every i,j∈{1,…,n}, α _i =α _j whenever i≡j (mod p). For an integer parameter g ￡ \fracn2,g\leq \frac{n}{2}, the property Period(≤g) is the property of all strings that are in Period(p) for some p≤g. The property Period( ￡ \fracn2)\mathit{Period}(\leq \frac{n}{2}) is also called Periodicity.     

Computing Diameter in the Streaming and Sliding-Window Models

We investigate the diameter problem in the streaming and sliding-window models. We show that, for a stream of nn points or a sliding window of size nn, any exact algorithm for diameter requires W(n)\Omega(n) bits of space. We present a simple e\epsilon-approximation algorithm for computing the diameter in the streaming model. Our main result is an e\epsilon-approximation algorithm that maintains the diameter in two dimensions in the sliding-window model using O((1/e^3/2) log³n(logR+loglogn + log(1/e)))O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n + \log ({1}/{\epsilon}))) bits of space, where RR is the maximum, over all windows, of the ratio of the diameter to the minimum non-zero distance between any two points in the window.     

Interpolation of Shifted-Lacunary Polynomials

Given a “black box” function to evaluate an unknown rational polynomial f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 ￡ e₁ < e₂ < ? < e_t{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients c₁, ?, c_t ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that

Reoptimization of constraint satisfaction problems with approximation resistant predicates

If k = O(log n) and a predicate P is approximation resistant for the reoptimization of the Max-EkCSP-P problem, then, after inserting a truth-value into the predicate and imposing some constraint, there exists a polynomial algorithm with the approximation ratio q(P) = \frac12 - d(P) q(P) = \frac{1}{{2 - d(P)}} , where d(P) = 2 ^{- k}| P ^{- 1}(1) | d(P) = {2^{ - k}}\left| {{P^{ - 1}}(1)} \right| is a “random” threshold approximation ratio of the predicate P. The ratio q(P) is a threshold approximation ratio.     

Entanglement and Yangian in a {V^{\otimes 3}} Yang-Baxter system

In this paper, a 8 × 8 unitary Yang-Baxter matrix \breveR₁₂₃(q₁,q₂,f){\breve{R}_{123}(\theta_{1},\theta_{2},\phi)} acting on the triple tensor product space, which is a solution of the Yang-Baxter Equation for three qubits, is presented. Then quantum entanglement and the Berry phase of the Yang-Baxter system are studied. The Yangian generators, which can be viewed as the shift operators, are investigated in detail. And it is worth mentioning that the Yangian operators we constructed are independent of choice of basis.     

Tighter Approximation Bounds for Minimum CDS in Unit Disk Graphs

Connected dominating set (CDS) in unit disk graphs has a wide range of applications in wireless ad hoc networks. A number of approximation algorithms for constructing a small CDS in unit disk graphs have been proposed in the literature. The majority of these algorithms follow a general two-phased approach. The first phase constructs a dominating set, and the second phase selects additional nodes to interconnect the nodes in the dominating set. In the performance analyses of these two-phased algorithms, the relation between the independence number α and the connected domination number γ _c of a unit-disk graph plays the key role. The best-known relation between them is a ￡ 3\frac23g_c+1\alpha\leq3\frac{2}{3}\gamma_{c}+1. In this paper, we prove that α≤3.4306γ _c +4.8185. This relation leads to tighter upper bounds on the approximation ratios of two approximation algorithms proposed in the literature.     

Spreading of Messages in Random Graphs

Consider the following model on the spreading of messages. A message initially convinces a set of vertices, called the seeds, of the Erdős-Rényi random graph G(n,p). Whenever more than a ρ∈(0,1) fraction of a vertex v’s neighbors are convinced of the message, v will be convinced. The spreading proceeds asynchronously until no more vertices can be convinced. This paper derives lower bounds on the minimum number of initial seeds, min-seed(n,p,d,r)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho), needed to convince a δ∈{1/n,…,n/n} fraction of vertices at the end. In particular, we show that (1) there is a constant β>0 such that min-seed(n,p,d,r)=W(min{d,r}n)\mathrm{min\hbox{-}seed}(n,p,\delta,\rho)=\Omega(\min\{\delta,\rho\}n) with probability 1−n ^−Ω(1) for p≥β (ln (e/min {δ,ρ}))/(ρ n) and (2) min-seed(n,p,d,1/2)=W(dn/ln(e/d))\mathrm{min\hbox{-}seed}(n,p,\delta,1/2)=\Omega(\delta n/\ln(e/\delta)) with probability 1−exp (−Ω(δ n))−n ^−Ω(1) for all p∈[ 0,1 ]. The hidden constants in the Ω notations are independent of p.     

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time [(O)\tilde](n²s^w/2-1)\widetilde{O}(n^{2}s^{\omega/2-1}), where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and [(O)\tilde](f(n))\widetilde{O}(f(n)) denotes O(f(n)log  ^d n) for some constant d. By the currently best bound on ω, its running time can be also expressed as [(O)\tilde](n²s^0.188)\widetilde{O}(n^{2}s^{0.188}). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n ^1.232 and it is never slower than the fast [(O)\tilde](n^w)\widetilde{O}(n^{\omega})-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form [(O)\tilde](n^{w(\frac12log_ns,1,1)})\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)}), where ω(p,q,t) is the exponent of the fast multiplication of an n ^p ×n ^q matrix by an n ^q ×n ^t matrix.     

Approximating Minimum-Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, 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 several fundamental undirected network design problems under the power minimization criteria. Given a graph G=(V,E)\mathcal{G}=(V,\mathcal{E}) with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover} (MPEMC\textsf{MPEMC} ) problem is to find a minimum-power subgraph G of G\mathcal{G} so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC\textsf{MPEMC} , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $\textsf{Minimum-Power ($\textsf{MP$\textsf{MP ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, _boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k}) which is O(log k) unless k=n−o(n), and is O(log ² k)=O(log ² n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$\textsf{ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.     

On the efficiency of quantum algorithms for Hamiltonian simulation

We study algorithms simulating a system evolving with Hamiltonian H = ?_j=1^m H_j{H = \sum_{j=1}^m H_j} , where each of the H _j , j = 1, . . . ,m, can be simulated efficiently. We are interested in the cost for approximating e^-iHt, t ? \mathbbR{e^{-iHt}, t \in \mathbb{R}} , with error e{\varepsilon} . We consider algorithms based on high order splitting formulas that play an important role in quantum Hamiltonian simulation. These formulas approximate e ^−iHt by a product of exponentials involving the H _j , j = 1, . . . ,m. We obtain an upper bound for the number of required exponentials. Moreover, we derive the order of the optimal splitting method that minimizes our upper bound. We show significant speedups relative to previously known results.