
	Where results make sense

Topic: Polylogarithmic

In the News (Tue 18 Jun 13)

EXECUTIVE POWER

Iran

ANALYSIS

Pakistan

Family compact

	Polylogarithmic Extensions on Mixed Shimura varieties, by Joerg Wildeshaus
		This paper is a slightly revised version of the author's thesis (November 1993) and is identical to the Heft 12 of the Schriftenreihe des Mathematischen Instituts Muenster.
		Chapter I (chapter1.dvi) gives partial results on what we call the "generic relatively unipotent sheaf", which is defined for any sufficiently nice morphism with a section of schemes over C (in the Hodge theoretic context) or a number field (in the context of l-adic sheaves, or systems of smooth sheaves).
		We then give the general formalism of the construction of polylogarithmic extensions (indeed, in the higher dimensional case, these extensions won't be one-extensions, hence can't be thought of as framed sheaves).
	www.math.uiuc.edu /K-theory/0026 (495 words)

	NC
		In complexity theory, the class NC ("Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.
		The definition of NC is not affected by the choice of how the PRAM handles simultaneous access to a single bit by more than one processor.
		Equivalently, NC can be defined as those decision problems decidable by uniform Boolean circuits[?] with polylogarithmic depth and a polynomial number of gates.
	www.ebroadcast.com.au /lookup/encyclopedia/nc/NC.html (284 words)

	CSAIL Research Abstract
		Finally, in [4], we gave a tight (modulo polylogarithmic factors) upper bound for the space complexity of this problem.
		Our algorithms use only polylogarithmic space, which is exponentially smaller than than the space needed to store the whole input.
		The algorithms are obtained by representing the set of input points as a high-dimensional vector (using embeddings), and applying streaming algorithms designed for such vectors.
	publications.csail.mit.edu /abstracts/abstracts05/stream/stream.html (780 words)

	8 Conclusion
		Universal networks are capable of simulating any PRAM program with at most polylogarithmic degradation in time (see, for example, the simulation [12] of an EREW-PRAM on a butterfly network).
		Thus, when a universal network is physically constructed, the number of pins on a packaging unit must be nearly as large as the number of processors in the unit.
		A natural question to ask is whether a list can be sorted in a polylogarithmic number of steps where at each step, the load factor is bounded by the load factor induced by the linear list together with the permutation determined by the sorted output.
	www.cs.cmu.edu /afs/cs.cmu.edu/project/phrensy/pub/papers/LeisersonM88/node18.html (1335 words)

	[No title] (Site not responding. Last check: 2007-10-10)
		Polylogarithmic Inapproximability Robi Krauthgamer Several natural combinatorial optimization problems (such as Bandwidth, Pathwidth, Group-Steiner-Tree, Job-Shop-Scheduling and Min-Bisection) are known to have algorithms achieving an approximation ratio that is polylogarithmic in the input size.
		However, none of these problems was known to have a hardness of approximation result that excludes the possibility of a logarithmic approximation.
		This yields the first polylogarithmic integrality ratio for a (natural) relaxation of a problem.
	www.cs.huji.ac.il /~theorys/2003/Robi_Kraughthamer (159 words)

	Polylogarithmic - Wikipedia, the free encyclopedia
		A polylogarithmic function in n is a polynomial in the logarithm of n,
		In computer science, polylogarithmic functions occur as the order of some algorithms (e.g., "it has polylogarithmic order").
		for every exponent ε > 0 (for the meaning of this symbol, see big O notation), that is, a polylogarithmic function grows slower than any positive exponent.
	en.wikipedia.org /wiki/Polylogarithmic (126 words)

	Estimating Entropy of Data Streams
		That is, any processing must require only sublinear (ideally polylogarithmic) space and be performed in a single pass.
		In particular, most functions on the data will therefore be impossible to compute exactly, and must be approximated to some degree of accuracy using randomization.
		In other words, up to polylogarithmic factors, our algorithm is optimal.
	dimax.rutgers.edu /~khanhdob (553 words)

	[No title]
		As a consequence of our connectivity algorithm, we are able to solve several other dynamic graph problems with polylogarithmic update time and polylogarithmic query time, including bipartiteness, approximate minimum spanning tree, and the k-edge witness problem.
		Using similar techniques we have developed polylogarithmic algorithms for biconnectivity with bounded degree (FOCS '95) and 2-edge connectivity ``Fully Dynamic 2-Edge Connectivity in Polylogarithmic Time per Operation''.
		No previous polylogarithmic time algorithms were known for these problems.
	www.cs.uvic.ca /~val/researchsum.html (1765 words)

	2005-19: Workload-Optimal Histograms on Streams (Site not responding. Last check: 2007-10-10)
		Consider the case when the workload is explicitly stored and the input data is streamed in the time series model---the input is a vector of N components, and we are presented with the components, one at a time, in order.
		We present an algorithm that uses polylogarithmic space, processes each new item in constant time, and, in polylogarithmic post-processing time, determines a (1+epsilon)-approximation to the optimal histogram.
		This matches the space complexity, up to polylogarithmic factors, of the histogram construction on the stream when workload is uniform [Guha, Indyk, Muthukrishnan, and Strauss].
	dimacs.rutgers.edu /TechnicalReports/abstracts/2005/2005-19.html (291 words)

	Mohamed Aly \| Department of Computer Science \| University of Pittsburgh
		The concept of Oblivious Routing for general undirected networks was introduced by Racke when he showed that there exists an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t.
		In a following result, Racke and Rosen presented admission control algorithms achieving a polylogarithmic fraction (in the size of the network) of the optimal number of accepted messages.
		Admission control and routing algorithms for sensor networks under energy constraints, however, need to account for the energy spent in checking for feasible routes prior to the acceptance of a message and hence, it is unclear if these algorithms achieve polylogarithmic bounds under this condition.
	www.cs.pitt.edu /events/talks/07-1/mohamed-aly.14nov2006.php (405 words)

	Leonid Levin: research: (Site not responding. Last check: 2007-10-10)
		For that, one needs random access to the proof, to the proven statement (or input/output of computation) in error-correcting code, and to a source of coin-flips.
		The problem is that to decode any part of the library (say one paper) requires decoding everything.
		It is interesting that the powerful technique of error correcting codes was not used in general theory of computation for a long time: I know no such applications prior to [Levin 87] and few before
	www.cs.bu.edu /fac/lnd/research/er-r.htm (470 words)

	Transcendental Functions
		More on the Dilog and Polylog functions can be found in Lewin (Leonard Lewin, Polylogarithms and associated functions, New York: North Holland, 1981).
		For given integer m >= 2 and complex s of fixed precision or free real or complex s, this returns the value of the principal branch of the polylogarithm Li_m(s), defined for m >= 3 by Li_m(s)= the integral from 0 to s given by (Li_(m - 1)(s)/s)ds (and for m=2 as the dilogarithm Li_2).
		For their definition and main properties, see Zagier (D. Zagier, Polylogarithms, Dedekind Zeta Functions, and the Algebraic K-Theory of Fields, pp.
	www.math.wayne.edu /answers/magma/htmlhelp/text443.html (3562 words)

	L.Levin:Holo-Proofs
		Verifying holographic proofs takes a polylogarithmic, i.e., a constant power of the logarithm of n, number of bit operations.
		This is a tiny fraction: the binary logarithm of the number of atoms in the known Universe is under 300.
		There is a proofreader procedure, also running in polylogarithmic Monte-Carlo time, that confirms or corrects any given bit in any proof accepted by the verifier.
	www.cs.bu.edu /fac/lnd/expo/holo.htm (1472 words)

	Polylogarithmic Extensions on Mixed Shimura varieties. Part I Construction and basic properties, by Joerg Wildeshaus (Site not responding. Last check: 2007-10-10)
		Its subject is the generalization of the construction of polylogarithmic extensions to the context of mixed Shimura varieties.
		We also generalize Beilinson's and Levin's definition of the small polylogarithm pol.
		Our results depend on those contained in "The canonical construction of mixed sheaves on mixed Shimura varieties", which will soon be added to the archive.
	www.math.uiuc.edu /K-theory/0044 (116 words)

	Transcendental Functions
		For an integer m >= 2 and power series f defined over the free real or complex field, return the m-th polylogarithm of the series f.
		Then Li_m is the analytic continuation of the sum from n=1 to infinity of (s^n/n^m), (which is convergent for
		Given integer m >= 2 and complex s of fixed precision or free real or complex s, this returns the value of the principal branch of the modified versions tilde D_m, D_m and P_m of the polylogarithm Li_m(s); all of these satisfy functional equations of the form f_m(1/s)=(- 1)^mf_m(s).
	www.umich.edu /~gpcc/scs/magma/text569.htm (2561 words)

	Institute for Infrastructure Surety
		Our protocol is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n.
		To the best of our knowledge, we present the first leader election protocol which ensures that each good processor sends and processes a sublinear number of bits.
		Having reduced the problem of leader election to one of informing all good processors of a bit held by 1-o(1) fraction of good processors, we conjecture that the solution to this problem is not possible within polylogarithmic message bounds.
	www.eece.unm.edu /ifis/docs/abstract_kingvee.htm (165 words)

	Secure Games with Polynomial Expressions (Site not responding. Last check: 2007-10-10)
		We present the first private information retrieval (PIR) scheme which is both, deterministically correct and has polylogarithmic communication complexity.
		Our PIR protocol is symmetrically secure, and improves by a few orders of magnitude the known probabilistically correct polylogarithmic scheme.
		This result is achieved as an application of our methodology which introduces a broad family of games, called Secure Games with Polynomial Expressions (SGPEs), that involve two interacting players: Alice and Bob.
	www.sci.brooklyn.cuny.edu /~akiayias/pubs/sgpe.html (216 words)

	Computationally Private Information Retrieval with Polylogarithmic Communication - Cachin, Micali, Stadler ... (Site not responding. Last check: 2007-10-10)
		Computationally Private Information Retrieval with Polylogarithmic Communication (1999)
		Abstract: We present a single-database computationally private information retrieval scheme with polylogarithmic communication complexity.
		Our construction is based on a new, but reasonable intractability assumption, which we call the \Phi-Hiding Assumption (\PhiHA): essentially the difficulty of deciding whether a small prime divides OE(m), where m is a composite integer of unknown factorization.
	citeseer.ist.psu.edu /cachin99computationally.html (499 words)

	22C:196 Advanced Distributed Algorithms
		The course is on distributed algorithms with a focus on locality.
		We will be mainly interested in (i) distributed algorithms that solve problems exactly or approximately in at most polylogarithmic number of rounds and (ii) why certain problems cannot be solved in polylogarithmic number of rounds.
		We will also study lower bound results showing that certain problems, including the minimum spanning tree problem (MST), are impossible to solve in a certain number of rounds.
	www.cs.uiowa.edu /~sriram/196/fall06/syllabus.html (625 words)

	Polylogarithmic (Site not responding. Last check: 2007-10-10)
		Please look for Polylogarithmic, Minkowski and Minkowski Space to find more Polylogarithmic information.
		This paper is a slightly extended verion of Polylogarithmic Extensions on Mixed Shimura varieties, Part III: The elliptic polylogarithm, which...
		Definition of polylogarithmic, possibly with links to more information and implementations.
	www.polylogarithmic.info (383 words)

	[math/0208123] Growth and Percolation on the Uniform Infinite Planar Triangulation (Site not responding. Last check: 2007-10-10)
		the UIPT has growth rate r^4 up to polylogarithmic factors, confirming heuristic results from the physics literature.
		Additionally, the boundary component of the ball of radius r separating it from infinity a.s.
		It is also shown that the properly scaled size of a variant of the free triangulation of an m-gon converges in distribution to an asymmetric stable random variable of type 1/2.
	www.arxiv.org /math.PR/0208123 (197 words)

	Mathematics of Computation
		These are essentially polylogarithmic ladders in an integer base.
		A number of these identities that we derive in this work appear to be new, for example the critical identity for
		L. Lewin, Polylogarithms and Associated Functions, North Holland, New York, 1981.
	www.ams.org /mcom/1997-66-218/S0025-5718-97-00856-9/home.html (534 words)

	A polylogarithmic approximation of the minimum bisection (Site not responding. Last check: 2007-10-10)
		The previously known approximation ratio for bisection was roughly /spl radic/n.
		Index Terms- computational complexity; graph theory; computational geometry; polylogarithmic approximation; minimum bisection; graph; vertices; vertex partitioning; bisection cost; edges; complexity; approximation ratio
		Citation: U. Feige, R. Krauthgamer, "A polylogarithmic approximation of the minimum bisection," focs, p.
	csdl.computer.org /comp/proceedings/focs/2000/0850/00/08500105abs.htm (176 words)

	Explicit OR-Dispersers with Polylogarithmic Degree - Saks, Srinivasan, Zhou (ResearchIndex) (Site not responding. Last check: 2007-10-10)
		Explicit OR-Dispersers with Polylogarithmic Degree - Saks, Srinivasan, Zhou (ResearchIndex)
		This document uses CoBlitz to cache paper downloads.
		0, any sufficiently large N, and for any T 2 (log N) ¸, M 2 (log N), we give an explicit elementary construction of an (N; M;T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in N.
	citeseer.ist.psu.edu /80655.html (646 words)

	polylogarithmic (Site not responding. Last check: 2007-10-10)
		Definition: (1) Any function which is the sum of constants times powers of a logarithm of the argument: f(x)=Σ
		(2) In complexity theory, the measure of computation, m(n) (usually execution time or memory space), is bounded by a polylogarithmic function of the problem size, n.
		Paul E. Black, "polylogarithmic", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology.
	www.nist.gov /dads/HTML/polylogarith.html (102 words)

	Citebase - Integrals of polylogarithmic functions, recurrence relations, and associated Euler sums
		Citebase - Integrals of polylogarithmic functions, recurrence relations, and associated Euler sums
		Integrals of polylogarithmic functions, recurrence relations, and associated Euler sums
		Authors: Freitas, P. We show that integrals of the form [ dint
	citebase.eprints.org /cgi-bin/citations?id=oai:arXiv.org:math/0406401 (219 words)

	CIS Seminars and Talks
		A private approximation of a function f is defined to be another function F that approximates f in the usual sense, but does not reveal any information about x other than what can be deduced from f(x).
		We give the first secure two-party private approximation of the L_2 distance with polylogarithmic communication in the semi-honest model.
		In particular, we obtain a polylogarithmic private approximation of the Hamming distance, resolving the main open question of Feigenbaum et al [FIMNSW00].
	theory.lcs.mit.edu /~cis/cis-talks.html (16966 words)

	Citebase - Explicit regulator maps on polylogarithmic motivic complexes
		Citebase - Explicit regulator maps on polylogarithmic motivic complexes
		Authors: Goncharov, A. We define a regulator map from the weight n polylogarithmic motivic complex to the weight n Deligne complex of an algebraic variety X. The regulator map is constructed explicitly via the classical polylogarithms with some funny combinations of Bernoulli numbers as coefficients.
		Users are cautioned not to use it for academic evaluation yet.
	citebase.eprints.org /cgi-bin/citations?id=oai:arXiv.org:math/0003086 (107 words)

Try your search on: Qwika (all wikis)