Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR17-019 | 27th October 2017 10:39

A Unified Method for Placing Problems in Polylogarithmic Depth

RSS-Feed




Revision #2
Authors: Andreas Krebs, Nutan Limaye, Michael Ludwig
Accepted on: 27th October 2017 10:39
Downloads: 150
Keywords: 


Abstract:

In this work we consider the term evaluation problem which is, given a term over some algebra
and a valid input to the term, computing the value of the term on that input. In contrast to previous
methods we allow the algebra to be completely general and consider the problem of obtaining an
efficient upper bound for this problem. Many variants of the problems where the algebra is well
behaved have been studied. For example, the problem over the Boolean semiring or over the semiring
$(N, +, ×)$. We extend this line of work.

Our efficient term evaluation algorithm then serves as a tool for obtaining polylogarithmic depth
upper bounds for various well-studied problems. To demonstrate the utility of our result we show new
bounds and reprove known results for a large spectrum of problems. In particular, the applications
of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word
problems for tree and visibly pushdown automata, and various problems related to bounded tree-width
and clique-width graphs.



Changes to previous version:

Updated the abstract, the introduction and added some details for the outline of the main algorithm. Also added some sectioning in order to improve readability.


Revision #1 to TR17-019 | 21st February 2017 12:06

A Unified Method for Placing Problems in Polylogarithmic Depth





Revision #1
Authors: Andreas Krebs, Nutan Limaye, Michael Ludwig
Accepted on: 21st February 2017 12:06
Downloads: 248
Keywords: 


Abstract:

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem etc.. Many variants of the problems where the algebra is well behaved have been studied. For example, the problem over the Boolean semiring or over the semiring (Z, +, ×). Here, we allow the algebra to be completely general and obtain a bound for the term evaluation problem. We consider the problem of deriving upper bounds in terms of polylogarithmically deep circuits. To that end we present a generic term evaluation algorithm that works in polylogarithmic depth.

This efficient term evaluation algorithm over a very general algebra then
serves as a tool for showing polylogarithmic time upper bounds for various well-studied problems. To underline the utility of our result we show new bounds and reprove known results using our approach and thereby present a unified proof approach for problems of this nature. The spectrum of problems for which we apply our term evaluation algorithm is wide: in particular, the application of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word problems for tree and visibly pushdown automata, and various problems related to bounded tree-width and clique-width graphs.



Changes to previous version:

Multiple typos fixed.


Paper:

TR17-019 | 8th February 2017 16:32

A Unified Method for Placing Problems in Polylogarithmic Depth





TR17-019
Authors: Andreas Krebs, Nutan Limaye, Michael Ludwig
Publication: 10th February 2017 01:37
Downloads: 441
Keywords: 


Abstract:

In this work we consider the term evaluation problem which involves, given a term over some algebra and a valid input to the term, computing the value of the term on that input. This is a classical problem studied under many names such as formula evaluation problem, formula value problem etc.. Many variants of the problems where the algebra is well behaved have been studied. For example, the problem over the Boolean semiring or over the semiring (Z, +, ×). Here, we allow the algebra to be completely general and obtain a bound for the term evaluation problem. We consider the problem of deriving upper bounds in terms of polylogarithmically deep circuits. To that end we present a generic term evaluation algorithm that works in polylogarithmic depth.

This efficient term evaluation algorithm over a very general algebra then
serves as a tool for showing polylogarithmic time upper bounds for various well-studied problems. To underline the utility of our result we show new bounds and reprove known results using our approach and thereby present a unified proof approach for problems of this nature. The spectrum of problems for which we apply our term evaluation algorithm is wide: in particular, the application of the algorithm we consider include (but are not restricted to) arithmetic formula evaluation, word problems for tree and visibly pushdown automata, and various problems related to bounded tree-width and clique-width graphs.



ISSN 1433-8092 | Imprint