Zobrazeno 1 - 10
of 51
pro vyhledávání: '"KOMARATH, BALAGOPAL"'
We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We
Externí odkaz:
http://arxiv.org/abs/2301.02569
We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as
Externí odkaz:
http://arxiv.org/abs/2107.05128
We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph $H$ to $n$-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for
Externí odkaz:
http://arxiv.org/abs/2011.04778
Autor:
Komarath, Balagopal, Saurabh, Nitin
Detecting and eliminating logic hazards in Boolean circuits is a fundamental problem in logic circuit design. We show that there is no $O(3^{(1-\epsilon)n} \text{poly}(s))$ time algorithm, for any $\epsilon > 0$, that detects logic hazards in Boolean
Externí odkaz:
http://arxiv.org/abs/2006.10592
We study the time complexity of induced subgraph isomorphism problems where the pattern graph is fixed. The earliest known example of an improvement over trivial algorithms is by Itai and Rodeh (1978) who sped up triangle detection in graphs using fa
Externí odkaz:
http://arxiv.org/abs/1809.08858
Autor:
Ikenmeyer, Christian, Komarath, Balagopal, Lenzen, Christoph, Lysikov, Vladimir, Mokhov, Andrey, Sreenivasaiah, Karteek
Publikováno v:
J. ACM 66(4), Article 25 (2019)
The problem of constructing hazard-free Boolean circuits dates back to the 1940s and is an important problem in circuit design. Our main lower-bound result unconditionally shows the existence of functions whose circuit complexity is polynomially boun
Externí odkaz:
http://arxiv.org/abs/1711.01904
Publikováno v:
Fundam. Inform., volume 145, number 4, pages 471-483 (2016)
We initiate a complexity theoretic study of the language based graph reachability problem (L-REACH) : Fix a language L. Given a graph whose edges are labeled with alphabet symbols of the language L and two special vertices s and t, test if there is p
Externí odkaz:
http://arxiv.org/abs/1701.03255
The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble
Externí odkaz:
http://arxiv.org/abs/1604.05510
Comparator circuit model was originally introduced by Mayr and Subramanian (1992) (and further studied by Cook, Filmus and Le (2012)) to capture problems which are not known to be P-complete but still not known to admit efficient parallel algorithms.
Externí odkaz:
http://arxiv.org/abs/1503.00275
Autor:
IKENMEYER, CHRISTIAN1 (AUTHOR) cikenmey@mpi-sws.org, KOMARATH, BALAGOPAL2 (AUTHOR) bkomarath@cs.uni-saarland.de, LENZEN, CHRISTOPH3 (AUTHOR) clenzen@mpi-inf.mpg.de, LYSIKOV, VLADIMIR2 (AUTHOR) vlysikov@cs.uni-saarland.de, MOKHOV, ANDREY4 (AUTHOR) andrey.mokhov@ncl.ac.uk, SREENIVASAIAH, KARTEEK5 (AUTHOR) karteek@iith.ac.in
Publikováno v:
Journal of the ACM. Aug2019, Vol. 66 Issue 4, p1-20. 20p.