標題: Titlebook: Computer Science – Theory and Applications; 6th International Co Alexander Kulikov,Nikolay Vereshchagin Conference proceedings 2011 Springe [打印本頁] 作者: Lensometer 時間: 2025-3-21 19:42
書目名稱Computer Science – Theory and Applications影響因子(影響力)
書目名稱Computer Science – Theory and Applications影響因子(影響力)學科排名
書目名稱Computer Science – Theory and Applications網(wǎng)絡公開度
書目名稱Computer Science – Theory and Applications網(wǎng)絡公開度學科排名
書目名稱Computer Science – Theory and Applications被引頻次
書目名稱Computer Science – Theory and Applications被引頻次學科排名
書目名稱Computer Science – Theory and Applications年度引用
書目名稱Computer Science – Theory and Applications年度引用學科排名
書目名稱Computer Science – Theory and Applications讀者反饋
書目名稱Computer Science – Theory and Applications讀者反饋學科排名
作者: Truculent 時間: 2025-3-21 20:37 作者: Communicate 時間: 2025-3-22 02:44
Sediment and the phosphate cycle,implicit problem. First we present optimal and near-optimal structures for paths and trees. Then, based on these results, we provide efficient structures for planar graphs and general directed graphs.作者: 符合規(guī)定 時間: 2025-3-22 05:58
Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error,e main storage of .(.log..) bits and a short word of log.. bits that is pre-computed once for the stored set . and “cached”. To answer a query “.?∈?.?” we allow to read the whole cached word and only one bit from the main storage. For some reasonable values of parameters (e.g., for poly(log.)???.???作者: ONYM 時間: 2025-3-22 11:59
,The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms,with nonlinear . and random .. All above lower bounds are randomized..The main contribution of this paper is the simpler proof of the exponential lower bound of the Goldreich’s function inversion by myopic DPLL algorithms. A dependency graph in our construction may be based on an arbitrary expander,作者: Cacophonous 時間: 2025-3-22 13:03 作者: Cacophonous 時間: 2025-3-22 18:48
Sediment and the phosphate cycle,n give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation.作者: dandruff 時間: 2025-3-23 00:15 作者: JOT 時間: 2025-3-23 03:00
On Maltsev Digraphs,n give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation.作者: 確定無疑 時間: 2025-3-23 05:52
Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Cliqueidth of large path powers in polynomial time, which has been an open problem for a decade. The presented new characterisation is used to achieve this latter result. With our result, large .-path powers constitute the first non-trivial infinite class of graphs of unbounded clique-width whose clique-width can be computed exactly in polynomial time.作者: Vital-Signs 時間: 2025-3-23 13:44
0302-9743 Computer Science Symposium in Russia, CSR 2011, held in St. Petersburg, Russia, in June 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical compu作者: 確保 時間: 2025-3-23 16:30
Conference proceedings 2011 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.作者: SPER 時間: 2025-3-23 20:10 作者: 貞潔 時間: 2025-3-24 00:31
Christa Fest,Karl-Julius Schmidtnalogue of Muchnik’s conditional complexity theorem. I.e., for all . and . there exists a program . of least possible length that transforms . to . and is simple conditional on .. Here all programs work in polynomial space and all complexities are measured with logarithmic accuracy instead of polylogarithmic one in the previous work.作者: 一再遛 時間: 2025-3-24 05:17 作者: FOR 時間: 2025-3-24 07:12 作者: Etching 時間: 2025-3-24 12:14 作者: 刪減 時間: 2025-3-24 17:28
A. Patchornik,M. Fridkin,E. Katchalskimples where the latter parameter is bounded whereas the former is not. As main result we show that permanents of matrices of bounded triangular tree-width are efficiently computable. This result holds as well for the Hamiltonian Cycle problem.作者: fluffy 時間: 2025-3-24 22:13
The Equivalence of Sampling and Searching, version. What makes this nontrivial is that the same .. works for every ...As an application, we prove the surprising result that .?=?...?=?.. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.作者: HEED 時間: 2025-3-25 00:02 作者: CIS 時間: 2025-3-25 07:24 作者: nurture 時間: 2025-3-25 10:28 作者: 油膏 時間: 2025-3-25 12:57
,Graphs of Bounded Treewidth Can Be Canonized in?,,ree canonization algorithm?[22]. We define recursively what we call a . which gives with respect to some parameters in a logarithmic number of levels a canonical invariant together with an arrangement of all vertices. From this we compute a canonical labeling.作者: Embolic-Stroke 時間: 2025-3-25 19:12
An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents,mples where the latter parameter is bounded whereas the former is not. As main result we show that permanents of matrices of bounded triangular tree-width are efficiently computable. This result holds as well for the Hamiltonian Cycle problem.作者: 混合,攙雜 時間: 2025-3-25 23:27
0302-9743 cted from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.978-3-642-20711-2978-3-642-20712-9Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 全能 時間: 2025-3-26 03:38 作者: 宴會 時間: 2025-3-26 04:17
https://doi.org/10.1007/BFb0051473 polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.作者: 和藹 時間: 2025-3-26 09:39 作者: 血友病 時間: 2025-3-26 16:41 作者: verdict 時間: 2025-3-26 17:33
The Equivalence of Sampling and Searching, ., and asked to find a member of a nonempty set .. with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem ., there exis作者: murmur 時間: 2025-3-26 21:55 作者: 使苦惱 時間: 2025-3-27 02:05
Learning Read-Constant Polynomials of Constant Degree Modulo Composites,ass .. They are also precisely the functions computable efficiently by . over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by作者: Harness 時間: 2025-3-27 05:40
On the Arithmetic Complexity of Euler Function,e derandomization of the Identity Testing problem. Specifically, it is shown that (1) if computing the Euler function over a finite field is hard then computing permanent over the integers is also hard, and (2) if computing any factor of the Euler function over a field is hard then the Identity Test作者: 姑姑在炫耀 時間: 2025-3-27 13:20
Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error,a structure that queries of type “.?∈?.?” can be answered very quickly..H.?Buhrman, P.B.?Miltersen, J.?Radhakrishnan, and S.?Venkatesh proposed a bit-probe scheme based on expanders. Their scheme needs space of .(.log.) bits, and requires to read only one randomly chosen bit from the memory to answe作者: Ligament 時間: 2025-3-27 15:33
,Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandosuch objects with better parameters than explicit constructions do. But the probabilistic method does not give “effective” variants of such theorems, i.e. variants for resource-bounded Kolmogorov complexity. We show that a “naive derandomization” approach of replacing these objects by the output of 作者: 沒花的是打擾 時間: 2025-3-27 20:36 作者: Trochlea 時間: 2025-3-27 22:10
Faster Polynomial Multiplication via Discrete Fourier Transforms,stest algorithms for this problem and obtain faster algorithms for polynomial multiplication over certain fields which do not support DFTs of large smooth orders. We prove that the famous Sch?nhage-Strassen’s upper bound cannot be improved over the field of rational numbers if we consider only algor作者: overrule 時間: 2025-3-28 03:04 作者: 想象 時間: 2025-3-28 10:11
Almost ,-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs,e fundamental problem of derandomizing space bounded computations. Such constructions have been known only in the case of width?2 and in very restricted cases of bounded width. In our previous work, we have introduced a so-called richness condition which is, in a certain sense, sufficient for a set 作者: 粗野 時間: 2025-3-28 11:29 作者: 興奮過度 時間: 2025-3-28 15:57 作者: muscle-fibers 時間: 2025-3-28 21:13
On Maltsev Digraphs,nt union of directed cycles, showing that the constraint satisfaction problem for Maltsev digraphs is in logspace, .. (This was observed in [19] using an indirect argument.) We then generalize results in [19] to show that a Maltsev digraph is preserved not only by a majority operation, but by a clas作者: seroma 時間: 2025-3-28 23:31 作者: biopsy 時間: 2025-3-29 04:36 作者: 螢火蟲 時間: 2025-3-29 09:19 作者: 情愛 時間: 2025-3-29 14:34 作者: GROG 時間: 2025-3-29 18:34
An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents,ntries from a field . is the tree-width of the underlying graph .. having an edge (.,.) if and only if the entry ..?≠?0. Though .. is directed this does not influence the tree-width definition. Thus, it does not reflect the lacking symmetry when ..?≠?0 but ..?=?0. The latter however might have impac作者: 桶去微染 時間: 2025-3-29 21:36 作者: Ambulatory 時間: 2025-3-30 00:26
Christa Fest,Karl-Julius Schmidte derandomization of the Identity Testing problem. Specifically, it is shown that (1) if computing the Euler function over a finite field is hard then computing permanent over the integers is also hard, and (2) if computing any factor of the Euler function over a field is hard then the Identity Testing problem over the field can be derandomized.作者: Germinate 時間: 2025-3-30 05:30
on the worst case number of iterations needed for both of these algorithms to provide non-trivial approximations to the value of a game with . non-terminal positions and . actions for each player in each position.作者: nitroglycerin 時間: 2025-3-30 10:55
Chemical Signalling in Beetles, to reformulate some notions and therefore provide new intuition. In this survey we provide (with minimal comments) many different examples where notions and statements that involve Kolmogorov complexity are compared with their counterparts not involving complexity.作者: GLIDE 時間: 2025-3-30 14:34 作者: 浸軟 時間: 2025-3-30 18:16 作者: 符合你規(guī)定 時間: 2025-3-30 21:21
Alexander Kulikov,Nikolay VereshchaginUnique visibility.State-of-the-art research.Fast-track conference proceedings作者: 極肥胖 時間: 2025-3-31 02:43 作者: 表主動 時間: 2025-3-31 05:37 作者: Galactogogue 時間: 2025-3-31 10:13 作者: 蛙鳴聲 時間: 2025-3-31 13:37 作者: Infelicity 時間: 2025-3-31 21:18 作者: acclimate 時間: 2025-3-31 23:36
Snakes and Cellular Automata: Reductions and Inseparability Results,nseparable properties. Analogously, Wang tile sets that admit tilings of arbitrarily long loops (and hence also infinite snakes) are recursively inseparable from the tile sets that admit no loops and no infinite snakes. The latter inseparability result actually implies the first one in a trivial way.作者: 恭維 時間: 2025-4-1 03:48
Conference proceedings 2011 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.作者: 收養(yǎng) 時間: 2025-4-1 06:17 作者: 引起痛苦 時間: 2025-4-1 11:09 作者: Arboreal 時間: 2025-4-1 14:56
https://doi.org/10.1007/BFb0051473ass .. They are also precisely the functions computable efficiently by . over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by作者: 壕溝 時間: 2025-4-1 20:31
