Zobrazeno 1 - 10
of 15
pro vyhledávání: '"Karteek Sreenivasaiah"'
Publikováno v:
Information Processing Letters. :106418
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::05356f874fd1eac1a6cecc7746751faf
https://doi.org/10.1016/j.ipl.2023.106418
https://doi.org/10.1016/j.ipl.2023.106418
Publikováno v:
STOC
In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. W
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9cff192b2627e721c4985d3cba42c7e5
https://doi.org/10.1145/3313276.3316339
https://doi.org/10.1145/3313276.3316339
Publikováno v:
ACM Transactions on Computation Theory. 8:1-28
S ubset S um is a well-known NP-complete problem: given t ∈ Z + and a set S of m positive integers, output YES if and only if there is a subset S ′⊆ S such that the sum of all numbers in S ′ equals t . The problem and its search and optimizat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4d5aaa39c381f63dec402b5c7dd84f10
https://doi.org/10.1145/2894843
https://doi.org/10.1145/2894843
Autor:
Karteek Sreenivasaiah, Balagopal Komarath, Christian Ikenmeyer, Christoph Lenzen, Andrey Mokhov, Vladimir Lysikov
Publikováno v:
Journal of the ACM
BASE-Bielefeld Academic Search Engine
STOC'18
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
JOURNAL OF THE ACM
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing -STOC 2018
BASE-Bielefeld Academic Search Engine
STOC'18
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
STOC
JOURNAL OF THE ACM
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-STOC 2018
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing -STOC 2018
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:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2ed98631a56be359d1d43fa4ed3c5ba8
Publikováno v:
Algorithmica. 76:890-909
Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::244ffcbd33ba62ca14dd28a32ae63a8d
https://doi.org/10.1007/s00453-015-0101-z
https://doi.org/10.1007/s00453-015-0101-z
Publikováno v:
Fundamentals of Computation Theory ISBN: 9783662557501
FCT
FCT
We study polynomials computed by depth five \(\varSigma \wedge \varSigma \wedge \varSigma \) arithmetic circuits where ‘\(\varSigma \)’ and ‘\(\wedge \)’ represent gates that compute sum and power of their inputs respectively. Such circuits c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5669cd82bdda31ff7b2d0b433b8626cf
https://doi.org/10.1007/978-3-662-55751-8_19
https://doi.org/10.1007/978-3-662-55751-8_19
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783319155784
LATA
LATA
We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution [10]. This gives the first successful transf
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::443abb60354d523d4dbadc548d4d135b
https://doi.org/10.1007/978-3-319-15579-1_38
https://doi.org/10.1007/978-3-319-15579-1_38
Publikováno v:
IndraStra Global.
We study the problem of testing if the polynomial computed by an arithmetic circuit is identically zero. We give a deterministic polynomial time algorithm for this problem when the inputs are read-twice or read-thrice formulas. In the process, these
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a471fd04e3e70c98bfdf39c52caad0b5
https://igi.indrastra.com/items/show/82558
https://igi.indrastra.com/items/show/82558
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319087825
COCOON
COCOON
Polynomial Identity Testing (PIT) algorithms have focussed on polynomials computed either by small alternation-depth arithmetic circuits, or by read-restricted formulas. Read-once polynomials (ROPs) are computed by read-once formulas (ROFs) and are t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::91a9c5546443786bed2c567f86f992e8
https://doi.org/10.1007/978-3-319-08783-2_1
https://doi.org/10.1007/978-3-319-08783-2_1
A proof system for a language L is a function f such that Range(f) is exactly L. In this paper, we look at proofsystems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a7ccbdac46f59b3d0d69f38c9c957e55