English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  The fourth moment in Luby`s distribution

Dubhashi, D. P., Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C.(1995). The fourth moment in Luby`s distribution (MPI-I-1995-1-019). Saarbrücken: Max-Planck-Institut für Informatik.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-A432-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-B63E-A
Genre: Report

Files

show Files
hide Files
:
MPI-I-95-1-019.pdf (Any fulltext), 161KB
View   Save
File Permalink:
https://hdl.handle.net/11858/00-001M-0000-0014-B63F-8
Name:
MPI-I-95-1-019.pdf
Description:
-
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
View
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Dubhashi, Devdatt P.1, Author
Pantziou, Grammati E.1, Author
Spirakis, P. G.2, Author           
Zaroliagis, Christos2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Luby (1988) proposed a way to derandomize randomized computations which is based on the construction of a small probability space whose elements are $3$-wise independent. In this paper we prove some new properties of Luby's space. More precisely, we analyze the fourth moment and prove an interesting technical property which helps to understand better Luby's distribution. As an application, we study the behavior of random edge cuts in a weighted graph.

Details

show
hide
Language(s): eng - English
 Dates: 1995
 Publication Status: Issued
 Pages: 10 p.
 Publishing info: Saarbrücken : Max-Planck-Institut für Informatik
 Table of Contents: -
 Rev. Type: -
 Identifiers: URI: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1995-1-019
Report Nr.: MPI-I-1995-1-019
BibTex Citekey: DubhashiPantziouSpirakisZaroliagis95
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Research Report / Max-Planck-Institut für Informatik
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: - Identifier: -