我正派
发表于 2025-3-23 13:29:47
Complex polynomials and circuit lower bounds for modular counting,It is easy to show that a depth 2 circuit of size . (where . is the number of inputs) containing . gates can determine whether the sum of the input bits is divisible by ., for any fixed .>1, whereas it is known that this requires exponentialsize circuits if we have no . gates. Our main result is tha
吹气
发表于 2025-3-23 15:23:23
http://reply.papertrans.cn/59/5801/580036/580036_12.png
迷住
发表于 2025-3-23 20:29:11
Edge insertion for optimal triangulations,d retriangulating the resulting two polygonal regions. After presenting an abstract view of the paradigm, this paper shows that it can be used to obtain polynomial time algorithms for several types of optimal triangulations.
harpsichord
发表于 2025-3-23 22:10:31
Simulating permutation networks on hypercubes,tation networks on hypercubes. Our embeddings exhibit a marked trade-off between dilation and expansion and for the .-dimensional star network have the following dilation and expansion bounds:.The embeddings are, in fact, optimum or nearly optimum in both dilation and expansion for small values of .
MURAL
发表于 2025-3-24 06:23:46
http://reply.papertrans.cn/59/5801/580036/580036_15.png
obsession
发表于 2025-3-24 09:57:28
Parallel complexity of heaps and min-max heaps,n (e.g., the heap, the minmax heap, and the deap) can be constructed in linear sequential time. In this paper, we design optimal Ω((log log .).) time parallel algorithms with ./(log log.). processors for the constructions on the parallel comparison tree model. For building heaps in parallel, our alg
肉身
发表于 2025-3-24 12:36:23
On the complexity of some problems for the Blum, Shub & Smale model,putation. We also introduce a class of languages . lying between . and . that uses probabilistic machines, and several problems from the same area are classified as “probably noncomplete” by showing their membership in ..
排名真古怪
发表于 2025-3-24 15:00:31
http://reply.papertrans.cn/59/5801/580036/580036_18.png
因无茶而冷淡
发表于 2025-3-24 19:44:53
How to write integers in non-integer base,ansion. We give examples which show that this is not the general case, even for θ being a Pisot number. In connection with symbolic dynamics two families of Pisot numbers such that every integer has a finite expansion are given: when θ is the dominant root of the polynomial X. − a.X.−1-... -a., wher
立即
发表于 2025-3-25 01:56:46
A simple randomized parallel algorithm for maximal ,-matchings,inclusion) .-matchings. Our algorithm works in .(log..) time on an arbitrary . with a linear number of processors. Also we slightly improve a constant coefficient in the analysis of the Israeli-Itai algorithm. Finally we present more efficient NC algorithms for maximal .-matchings for several non-tr