標(biāo)題: Titlebook: Computer Science – Theory and Applications; 16th International C Rahul Santhanam,Daniil Musatov Conference proceedings 2021 Springer Nature [打印本頁(yè)] 作者: Inveigle 時(shí)間: 2025-3-21 16:58
書(shū)目名稱Computer Science – Theory and Applications影響因子(影響力)
書(shū)目名稱Computer Science – Theory and Applications影響因子(影響力)學(xué)科排名
書(shū)目名稱Computer Science – Theory and Applications網(wǎng)絡(luò)公開(kāi)度
書(shū)目名稱Computer Science – Theory and Applications網(wǎng)絡(luò)公開(kāi)度學(xué)科排名
書(shū)目名稱Computer Science – Theory and Applications被引頻次
書(shū)目名稱Computer Science – Theory and Applications被引頻次學(xué)科排名
書(shū)目名稱Computer Science – Theory and Applications年度引用
書(shū)目名稱Computer Science – Theory and Applications年度引用學(xué)科排名
書(shū)目名稱Computer Science – Theory and Applications讀者反饋
書(shū)目名稱Computer Science – Theory and Applications讀者反饋學(xué)科排名
作者: STALL 時(shí)間: 2025-3-22 00:07 作者: 混雜人 時(shí)間: 2025-3-22 04:20
Variants of the Determinant Polynomial and the ,-Completeness,olynomial which we call . and . and show that they are . and . complete respectively under .-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their wor作者: Conscientious 時(shí)間: 2025-3-22 04:56
Dynamic Complexity of Expansion,.,.,., ., ., ., .] for some representative examples. Use of linear algebra has been a notable feature of some of these papers. We extend this theme to show that the gap version of spectral expansion in bounded degree graphs can be maintained in the class . (also known as ., for domain independent qu作者: neutralize 時(shí)間: 2025-3-22 11:04
Real ,-Conjecture for Sum-of-Squares: A Unified Approach to Lower Bound and Derandomization,n the number of distinct real roots of . is polynomially bounded in .. Assuming the conjecture with parameter ., one can show that . (i.e.?symbolic permanent requires superpolynomial-size circuit). In this paper, we propose a .-conjecture for sum-of-squares (SOS) model (equivalently, .)..For a univa作者: 放牧 時(shí)間: 2025-3-22 14:44 作者: 放牧 時(shí)間: 2025-3-22 17:34
Approximation Schemes for Multiperiod Binary Knapsack Problems,otes the cumulative size for periods ., and a list of . items. Each item is a triple (.,?.,?.) where . denotes the reward or value of the item, . its size, and . denotes its time index (or, deadline). The goal is to choose, for each deadline ., which items to include to maximize the total reward, su作者: aerial 時(shí)間: 2025-3-22 21:18
Limitations of Sums of Bounded Read Formulas and ABPs,ng task in algebraic complexity theory. We study representation of polynomials as sums of weaker models such as read once formulas (ROFs) and read once oblivious algebraic branching programs (ROABPs). We prove: .Our results are based on analysis of the partial derivative matrix under different distr作者: 可轉(zhuǎn)變 時(shí)間: 2025-3-23 05:21 作者: 名義上 時(shí)間: 2025-3-23 07:52 作者: 全面 時(shí)間: 2025-3-23 11:37
Bit-Complexity of Solving Systems of Linear Evolutionary Partial Differential Equations,-value problem for a linear evolutionary system of PDEs is approximated up?to absolute error . by repeatedly (exponentially often in .) multiplying a matrix . to the vector from the previous time step, starting with the initial condition ., approximated by the spatial grid vector .. The dimension of作者: VEN 時(shí)間: 2025-3-23 15:16
,A Secure Three-Input AND Protocol with?a?Standard Deck of Minimal Cards,xisting protocols use a two-colored deck consisting of red cards and black cards, Niemi and Renvall in 1999 constructed protocols for securely computing two-input Boolean functions (such as secure logical AND and XOR computations) using a commonly available standard deck of playing cards. Since this作者: 削減 時(shí)間: 2025-3-23 20:48 作者: 外來(lái) 時(shí)間: 2025-3-24 00:19
,Predictions and Algorithmic Statistics for?Infinite Sequences,“explanation” for the observed data (in the sense of algorithmic statistics) for prediction. In this way we keep the expected sum of squares of prediction errors bounded (as it was for the Solomonoff’s predictor) and, moreover, guarantee that the sum of squares of prediction errors is bounded along 作者: HEAVY 時(shí)間: 2025-3-24 02:36 作者: 我還要背著他 時(shí)間: 2025-3-24 07:03
Approximation Algorithms for Connectivity Augmentation Problems,he . problem we need to increase the edge-connectivity by?1. In the . problem . is connected and . should be 2-connected. In . problems every edge in . connects minimal deficient sets. For this version we give a simple combinatorial approximation algorithm with ratio 5/3, improving the 1.91 approxim作者: Irrigate 時(shí)間: 2025-3-24 13:02 作者: Pageant 時(shí)間: 2025-3-24 17:37
0302-9743 une/July 2021...The 28 full papers were carefully reviewed and selected from 68 submissions. The papers cover a broad range of topics, such as formal languages and automata theory, geometry and discrete structures; theory and algorithms for application domains and much more. .978-3-030-79415-6978-3-作者: 愚笨 時(shí)間: 2025-3-24 20:14 作者: 連系 時(shí)間: 2025-3-25 02:43
https://doi.org/10.1007/b113856red by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely ., by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).作者: 男生如果明白 時(shí)間: 2025-3-25 05:57
Injective Colouring for ,-Free Graphs,m is denoted .. A graph is .-free if it does not contain . as an induced subgraph. We prove a dichotomy for . for graphs with bounded independence number. Then, by combining known with further new results, we determine the complexity of . on .-free graphs for every . except for one missing case.作者: PLAYS 時(shí)間: 2025-3-25 11:02
Variants of the Determinant Polynomial and the ,-Completeness,red by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their work, namely ., by introducing additional edge labels on the edges of the underlying graph. The idea of using edge labels is inspired by the work of Mengel (MFCS 2013).作者: Communal 時(shí)間: 2025-3-25 13:37
0302-9743 languages and automata theory, geometry and discrete structures; theory and algorithms for application domains and much more. .978-3-030-79415-6978-3-030-79416-3Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: verdict 時(shí)間: 2025-3-25 16:36 作者: 厭煩 時(shí)間: 2025-3-25 21:58
The Chemistry of Metal Alkoxideseries) under batch changes (insertions and deletions) of . many edges..The spectral graph theoretic material of this work is based on the paper by Kale-Seshadhri [.]. Our primary technical contribution is to maintain up?to logarithmic powers of the transition matrix of a bounded degree undirected graph in ..作者: Volatile-Oils 時(shí)間: 2025-3-26 00:12
The Chemistry of Metal Alkoxidesnstant factors, and the dependence on discrepancy in our randomized upper bound is tight up?to taking square-roots. Our results can be used to obtain lower bounds on approximate rank. We also obtain a strengthening of Newman’s theorem with respect to approximate rank.作者: moratorium 時(shí)間: 2025-3-26 07:41 作者: Chivalrous 時(shí)間: 2025-3-26 09:53
Computational Complexity of Multi-player Evolutionarily Stable Strategies,lexity class we denote as . and is a member of ., where the former class restrict the latter by having the existentially quantified variables be Boolean rather then real-valued. As a special case of our results it follows that deciding whether a given strategy is an ESS is complete for ..作者: hermetic 時(shí)間: 2025-3-26 13:08 作者: mechanical 時(shí)間: 2025-3-26 17:03 作者: aneurysm 時(shí)間: 2025-3-26 23:21
On the Computational Complexity of Reaction Systems, Revisited,/or inhibitor sets, and (iii) threshold properties. The complexities vary from deterministic polynomial time solvability to .- and .-completeness. Finally, as a side result on the complexity of threshold problems we improve the previously known threshold values for the no-concurrency, the comparability, and the redundancy property studied in?[.].作者: goodwill 時(shí)間: 2025-3-27 03:53 作者: acolyte 時(shí)間: 2025-3-27 08:42
The Neurobiology of Mood and Psychosesll, and that can be computed efficiently. For example, for two letters the limit expected size is .77.8. Our theoretical constants are backed-up by the experimental evidence. This confirms the phenomena reported in [.], and further it completely discards the usefulness of the uniform distribution on regular expressions.作者: Incorruptible 時(shí)間: 2025-3-27 12:36
The Chemistry of Natural Productss to both the values of . and the additional proof certificate via oracle calls. It uses . random bits and reads .(1) many components of both . and the additional proof string, which is of length . The paper is a contribution to the not yet much developed area of designing PCPs of proximity in real number complexity theory.作者: critique 時(shí)間: 2025-3-27 17:30
Limitations of Sums of Bounded Read Formulas and ABPs,ilinear ROABPs known as strict-interval ABPs defined in [Ramya-Rao, MFCS2019]. We show that strict-interval ABPs are equivalent to ROABPs up?to a polynomial blow up in size. In contrast, we show that interval formulas are different from ROFs and also admit depth reduction which is not known in the case of strict-interval ABPs.作者: 黃油沒(méi)有 時(shí)間: 2025-3-27 21:32 作者: BATE 時(shí)間: 2025-3-27 22:06 作者: 出處 時(shí)間: 2025-3-28 05:23
Stefan Br?se,Franziska Gl?ser,Sabilla ZhongAND protocol requires fewer cards and shuffles compared to that required when applying any existing two-input AND protocol twice to perform the three-input AND computation. Our protocol is unique in the sense that it is card minimal if we use two cards to encode a single bit.作者: 散步 時(shí)間: 2025-3-28 10:13
Nucleosides, nucleotides and nucleic acids,y a streaming algorithm of similar complexity, and we identify two different aspects in which SCAs are more restricted than streaming algorithms. We also show there is a language which cannot be accepted by any SCA in . time, even though it admits an .-space streaming algorithm with . update time.作者: 競(jìng)選運(yùn)動(dòng) 時(shí)間: 2025-3-28 12:05
,A Secure Three-Input AND Protocol with?a?Standard Deck of Minimal Cards,AND protocol requires fewer cards and shuffles compared to that required when applying any existing two-input AND protocol twice to perform the three-input AND computation. Our protocol is unique in the sense that it is card minimal if we use two cards to encode a single bit.作者: 天空 時(shí)間: 2025-3-28 18:03
Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata,y a streaming algorithm of similar complexity, and we identify two different aspects in which SCAs are more restricted than streaming algorithms. We also show there is a language which cannot be accepted by any SCA in . time, even though it admits an .-space streaming algorithm with . update time.作者: 愚笨 時(shí)間: 2025-3-28 21:17 作者: 并置 時(shí)間: 2025-3-29 01:53 作者: MODE 時(shí)間: 2025-3-29 03:30
Lecture Notes in Computer Sciencehttp://image.papertrans.cn/c/image/233821.jpg作者: 性滿足 時(shí)間: 2025-3-29 09:07
The Chemistry of Metal AlkoxidesWe prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function ., we prove that the bipartite Holant problem . is . computable in polynomial time . #P-hard. The dichotomy criterion on . is explicit.作者: concert 時(shí)間: 2025-3-29 14:51
https://doi.org/10.1007/b113856It is shown that there exists . in E. such that for every . matrix . of rank . we have ., whenever . for a sufficiently small ., and . is large enough. This generalizes recent results which bound below the probability by . or apply to constant-depth circuits.作者: Electrolysis 時(shí)間: 2025-3-29 17:15 作者: 粗鄙的人 時(shí)間: 2025-3-29 20:46 作者: pericardium 時(shí)間: 2025-3-30 00:12 作者: 無(wú)法取消 時(shí)間: 2025-3-30 07:05
Upper Bound for Torus Polynomials,We prove that all functions that have low degree torus polynomials approximating them with small error also have . circuits computing them. This serves as a partial converse to the result that all . functions have low degree torus polynomials approximating them with small error, by Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).作者: 小步走路 時(shí)間: 2025-3-30 10:49
https://doi.org/10.1007/978-3-030-79416-3approximation theory; artificial intelligence; communication; computer hardware; computer networks; compu作者: LITHE 時(shí)間: 2025-3-30 13:59 作者: Tinea-Capitis 時(shí)間: 2025-3-30 19:22
Hybrid Organic-Inorganic Materials, games, deciding existence of an ESS is complete for ., the second level of the polynomial time hierarchy. We show that deciding existence of an ESS of a multi-player game is closely connected to the second level of the . polynomial time hierarchy. Namely, we show that the problem is hard for a comp作者: GROSS 時(shí)間: 2025-3-30 22:19 作者: jeopardize 時(shí)間: 2025-3-31 03:24
https://doi.org/10.1007/b113856olynomial which we call . and . and show that they are . and . complete respectively under .-projections. The definitions of the polynomials are inspired by a combinatorial characterisation of the determinant developed by Mahajan and Vinay (SODA 1997). We extend the combinatorial object in their wor作者: 描繪 時(shí)間: 2025-3-31 06:36 作者: 長(zhǎng)矛 時(shí)間: 2025-3-31 10:10
Hybrid Organic-Inorganic Materials,n the number of distinct real roots of . is polynomially bounded in .. Assuming the conjecture with parameter ., one can show that . (i.e.?symbolic permanent requires superpolynomial-size circuit). In this paper, we propose a .-conjecture for sum-of-squares (SOS) model (equivalently, .)..For a univa作者: Diuretic 時(shí)間: 2025-3-31 16:00
The Chemistry of Metal Alkoxides.. In addition, we show that any Boolean function with approximate rank . and discrepancy . can be computed by deterministic protocols of complexity .(.), and private coin bounded error randomized protocols of complexity .. Our deterministic upper bound in terms of approximate rank is tight up?to co作者: Infiltrate 時(shí)間: 2025-3-31 17:33 作者: 肉體 時(shí)間: 2025-4-1 01:29 作者: 不感興趣 時(shí)間: 2025-4-1 05:48
The Chemistry of Metal Alkoxidesnd Rozenberg in?[.], that were overseen in the literature. To this end we focus on the complexity of (i) equivalence and multi-step simulation properties, (ii) special structural and behavioural RS properties such as, e.g., isotonicity, antitonicity, etc., and minimality with respect to reactant and作者: 斥責(zé) 時(shí)間: 2025-4-1 08:28
