DNF sparsification and a faster deterministic counting algorithm

Given a DNF formula f on n variables, the two natural size measures are the number of terms or size s(f) and the maximum width of a term w(f). It is folklore that small DNF formulas can be made narrow: if a formula has m terms, it can be ${\epsilon}$ -approximated by a formula with width ${{\rm log}(m/{\epsilon})}$ . We prove a converse, showing that narrow formulas can be sparsified. More precisely, any width w DNF irrespective of its size can be ${\epsilon}$ -approximated by a width w DNF with at most ${(w\, {\rm log}(1/{\epsilon}))^{O(w)}}$ terms. We combine our sparsification result with the work of Luby & Velickovic (1991, Algorithmica 16(4/5):415–433, 1996) to give a faster deterministic algorithm for approximately counting the number of satisfying solutions to a DNF. Given a formula on n variables with poly(n) terms, we give a deterministic ${n^{\tilde{O}({\rm log}\, {\rm log} (n))}}$ time algorithm that computes an additive ${\epsilon}$ approximation to the fraction of satisfying assignments of f for ${\epsilon = 1/{\rm poly}({\rm log}\, n)}$ . The previous best result due to Luby and Velickovic from nearly two decades ago had a run time of ${n^{{\rm exp}(O(\sqrt{{\rm log}\, {\rm log} n}))}}$ (Luby & Velickovic 1991, in Algorithmica 16(4/5):415–433, 1996).     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.     

A new PAC bound for intersection-closed concept classes

For hyper-rectangles in $\mathbb{R}^{d}$ Auer (1997) proved a PAC bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ , where $\varepsilon$ and $\delta$ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension $d$ in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\varepsilon}(d\log d + \log \frac{1}{\delta}))$ for arbitrary intersection-closed concept classes, complementing the well-known bounds $O(\frac{1}{\varepsilon}(\log \frac{1}{\delta}+d\log \frac{1}{\varepsilon}))$ and $O(\frac{d}{\varepsilon}\log \frac{1}{\delta})$ of Blumer et al. and (1989) and Haussler, Littlestone and Warmuth (1994). Our bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples. On the other hand, we show that many intersection-closed concept classes including e.g. maximum intersection-closed classes satisfy an additional combinatorial property that allows a proof of the optimal bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ . For such improved bounds the choice of the learning algorithm is crucial, as there are consistent learning algorithms that need $\Omega(\frac{1}{\varepsilon}(d\log\frac{1}{\varepsilon} +\log\frac{1}{\delta}))$ examples to learn some particular maximum intersection-closed concept classes.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

Tight Bounds for Distributed Minimum-Weight Spanning Tree Verification

This paper introduces the notion of distributed verification without preprocessing. It focuses on the Minimum-weight Spanning Tree (MST) verification problem and establishes tight upper and lower bounds for the time and message complexities of this problem. Specifically, we provide an MST verification algorithm that achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time, where m is the number of edges in the given graph G, n is the number of nodes, and D is G’s diameter. On the other hand, we show that any MST verification algorithm must send $\tilde{\varOmega}(m)$ messages and incur $\tilde{\varOmega}(\sqrt{n} + D)$ time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of $\tilde{\varOmega}(m)$ messages and $\tilde{\varOmega}(\sqrt{n} + D)$ time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously $\tilde{O}(m)$ messages and $\tilde{O}(\sqrt{n} + D)$ time. Specifically, the best known time-optimal algorithm (using ${\tilde{O}}(\sqrt {n} + D)$ time) requires O(m+n ^3/2) messages, and the best known message-optimal algorithm (using ${\tilde{O}}(m)$ messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.     

An efficient simulation algorithm on Kripke structures

A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let $\varSigma $ denote the state space, ${\rightarrow }$ the transition relation and $P_{\mathrm {sim}}$ the partition of $\varSigma $ induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose dominating additive term is $|P_{\mathrm {sim}}|^2$ , other algorithms are devised to attain the best time complexity $O(|P_{\mathrm {sim}}||{\rightarrow }|)$ . We present a novel simulation algorithm which is both space and time efficient: it runs in $O(|P_ {\mathrm {sim}}|^2 \log |P_{\mathrm {sim}}| + |\varSigma |\log |\varSigma |)$ space and $O(|P_{\mathrm {sim}}||{\rightarrow }|\log |\varSigma |)$ time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives

We consider Markov decision processes (MDPs) with Büchi (liveness) objectives. We consider the problem of computing the set of almost-sure winning states from where the objective can be ensured with probability 1. Our contributions are as follows: First, we present the first subquadratic symbolic algorithm to compute the almost-sure winning set for MDPs with Büchi objectives; our algorithm takes $O(n \cdot\sqrt{m})$ symbolic steps as compared to the previous known algorithm that takes O(n ²) symbolic steps, where n is the number of states and m is the number of edges of the MDP. In practice MDPs have constant out-degree, and then our symbolic algorithm takes $O(n \cdot\sqrt{n})$ symbolic steps, as compared to the previous known O(n ²) symbolic steps algorithm. Second, we present a new algorithm, namely win-lose algorithm, with the following two properties: (a) the algorithm iteratively computes subsets of the almost-sure winning set and its complement, as compared to all previous algorithms that discover the almost-sure winning set upon termination; and (b) requires $O(n \cdot\sqrt{K})$ symbolic steps, where K is the maximal number of edges of strongly connected components (scc’s) of the MDP. The win-lose algorithm requires symbolic computation of scc’s. Third, we improve the algorithm for symbolic scc computation; the previous known algorithm takes linear symbolic steps, and our new algorithm improves the constants associated with the linear number of steps. In the worst case the previous known algorithm takes 5?n symbolic steps, whereas our new algorithm takes 4?n symbolic steps.     

Exact Algorithms for Finding Longest Cycles in Claw-Free Graphs

The Hamiltonian Cycle problem is the problem of deciding whether an n-vertex graph G has a cycle passing through all vertices of G. This problem is a classic NP-complete problem. Finding an exact algorithm that solves it in ${\mathcal {O}}^{*}(\alpha^{n})$ time for some constant α<2 was a notorious open problem until very recently, when Björklund presented a randomized algorithm that uses ${\mathcal {O}}^{*}(1.657^{n})$ time and polynomial space. The Longest Cycle problem, in which the task is to find a cycle of maximum length, is a natural generalization of the Hamiltonian Cycle problem. For a claw-free graph G, finding a longest cycle is equivalent to finding a closed trail (i.e., a connected even subgraph, possibly consisting of a single vertex) that dominates the largest number of edges of some associated graph H. Using this translation we obtain two deterministic algorithms that solve the Longest Cycle problem, and consequently the Hamiltonian Cycle problem, for claw-free graphs: one algorithm that uses ${\mathcal {O}}^{*}(1.6818^{n})$ time and exponential space, and one algorithm that uses ${\mathcal {O}}^{*}(1.8878^{n})$ time and polynomial space.     

Order optimal information spreading using algebraic gossip

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $k$ distinct messages to all $n$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $O((k+\log n + D)\varDelta )$ rounds with high probability, where $D$ and $\varDelta $ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $k$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is $\varTheta (k + D)$ . To eliminate the factor of $\varDelta $ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $\mathcal{S } $ . The stopping time of TAG is $O(k+\log n +d(\mathcal{S })+t(\mathcal{S }))$ , where $t(\mathcal{S })$ is the stopping time of the spanning tree protocol, and $d(\mathcal{S })$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $k=\varOmega (n)$ , where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $\varTheta (n)$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $k=\varOmega (\text{ polylog }(n))$ . The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.     

ATP and Presentation Service for Mizar Formalizations

This paper describes the Automated Reasoning for Mizar ( $\textsf{Miz}\mathbb{AR}$ ) service, which integrates several automated reasoning, artificial intelligence, and presentation tools with Mizar and its authoring environment. The service provides ATP assistance to Mizar authors in finding and explaining proofs, and offers generation of Mizar problems as challenges to ATP systems. The service is based on a sound translation from the Mizar language to that of first-order ATP systems, and relies on the recent progress in application of ATP systems in large theories containing tens of thousands of available facts. We present the main features of $\textsf{Miz}\mathbb{AR}$ services, followed by an account of initial experiments in finding proofs with the ATP assistance. Our initial experience indicates that the tool offers substantial help in exploring the Mizar library and in preparing new Mizar articles.     

CLOVER: a faster prior-free approach to rare-category detection

Rare-category detection helps discover new rare classes in an unlabeled data set by selecting their candidate data examples for labeling. Most of the existing approaches for rare-category detection require prior information about the data set without which they are otherwise not applicable. The prior-free algorithms try to address this problem without prior information about the data set; though, the compensation is high time complexity, which is not lower than $O(dN^2)$ where $N$ is the number of data examples in a data set and $d$ is the data set dimension. In this paper, we propose CLOVER a prior-free algorithm by introducing a novel rare-category criterion known as local variation degree (LVD), which utilizes the characteristics of rare classes for identifying rare-class data examples from other types of data examples and passes those data examples with maximum LVD values to CLOVER for labeling. A remarkable improvement is that CLOVER’s time complexity is $O(dN^{2-1/d})$ for $d > 1$ or $O(N\log N)$ for $d = 1$ . Extensive experimental results on real data sets demonstrate the effectiveness and efficiency of our method in terms of new rare classes discovery and lower time complexity.     

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.

     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

D-Separation and computation of probability distributions in Bayesian networks

Consider a family ${(X_i)_{i \in I}}$ of random variables endowed with the structure of a Bayesian network, and a subset S of I. This paper examines the problem of computing the probability distribution of the subfamily ${(X_{a})_{a \in S}}$ (respectively the probability distribution of ${ (X_{b})_{b \in {\bar{S}}}}$ , where ${{\bar{S}} = I - S}$ , conditional on ${(X_{a})_{a \in S}}$ ). This paper presents some theoretical results that makes it possible to compute joint and conditional probabilities over a subset of variables by computing over separate components. In other words, it is demonstrated that it is possible to decompose this task into several parallel computations, each related to a subset of S (respectively of ${{\bar{S}}}$ ); these partial results are then put together as a final product. In computing the probability distribution over ${(X_a)_{a \in S}}$ , this procedure results in the production of a structure of level two Bayesian network structure for S.     

Scheduling to minimize gaps and power consumption

This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost  $\alpha $ . There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of “gaps” in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a $(1+{2 \over 3} \alpha )$ -approximation, and show that dependence on $\alpha $ is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not $o(\lg n)$ -approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an $O(\sqrt{n})$ -approximation for maximizing throughput given a hard upper bound on the number of gaps.     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient $\upvarepsilon $ -approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is $O$ (( $n^{4}/\upvarepsilon $ )log( $n$ / $\upvarepsilon $ )), where $n$ is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in $O(n^{3}/\upvarepsilon )$ time.     

Efficient broadcasting in radio networks with long-range interference

We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network $G,$ we term the smallest integer $d$ , s.t., for any interference edge $e$ there exists a simple path formed of at most $d$ transmission edges connecting the endpoints of $e$ as its interference distance $d_I$ . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt $n$ as the number of nodes, $D_T$ is the diameter of the subnetwork induced by the transmission edges, and $\varDelta $ refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance $d_I\ge 2$ any broadcasting schedule requires at least $D_T+\varOmega (\varDelta \cdot \frac{\log {n}}{\log {\varDelta }})$ rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes $1$ -shot (each node transmits at most once) broadcasting schedules of length $O(\varDelta \cdot \log {n})$ . (3) The main result of the paper is an algorithm that computes a $1$ -shot broadcasting schedule of length at most $4 \cdot D_T + O(\varDelta \cdot d_I \cdot \log ^4{n})$ for networks with arbitrary topology. Note that in view of the lower bound from (1) if $d_I$ is poly-logarithmic in $n$ this broadcast schedule is a poly-logarithmic factor away from the optimal solution.     

Two-Grid hp-Version Discontinuous Galerkin Finite Element Methods for Second-Order Quasilinear Elliptic PDEs

In this article we propose a class of so-called two-grid hp-version discontinuous Galerkin finite element methods for the numerical solution of a second-order quasilinear elliptic boundary value problem of monotone type. The key idea in this setting is to first discretise the underlying nonlinear problem on a coarse finite element space $V({{\mathcal {T}_{H}}},\boldsymbol {P})$ . The resulting ‘coarse’ numerical solution is then exploited to provide the necessary data needed to linearise the underlying discretisation on the finer space $V({{\mathcal {T}_{h}}},\boldsymbol {p})$ ; thereby, only a linear system of equations is solved on the richer space $V({{\mathcal {T}_{h}}},\boldsymbol {p})$ . In this article both the a priori and a posteriori error analysis of the two-grid hp-version discontinuous Galerkin finite element method is developed. Moreover, we propose and implement an hp-adaptive two-grid algorithm, which is capable of designing both the coarse and fine finite element spaces $V({{\mathcal {T}_{H}}},\boldsymbol {P})$ and $V({{\mathcal {T}_{h}}},\boldsymbol {p})$ , respectively, in an automatic fashion. Numerical experiments are presented for both two- and three-dimensional problems; in each case, we demonstrate that the CPU time required to compute the numerical solution to a given accuracy is typically less when the two-grid approach is exploited, when compared to the standard discontinuous Galerkin method.