Skip to MenuSkip to Content
  • Toggle High Contrast
  • Toggle Font Size
Technion Logo
Department of Mathematics
Technion - Israel Institute of Technology
  • Home
    • Error 404
    • Academics Faculty
    • Instructions
  • People
    • Administrative Staff
    • Faculty
    • "Kamea" Program
    • Visitors
    • Post-Docs
    • Graduate Students
    • Adjuncts
    • Alumni
    • In Memoriam
      • Leonid Lerer
      • David Chillag
      • Arie Leizarowitz
      • Zvi Har'el
      • Robert W. Brooks
      • Paul Erdös
      • Binyamin Schwarz
      • Elisha Netanyahu
    • Staff Card
  • Research
    • Research Groups
    • Research Areas
    • Center for Math Sciences
      • CMS - Information
      • CMS - Activities Archive
        • Year 2014-2015
        • Year 2013-2014
        • Year 2012-2013
        • Year 2011-2012
        • Year 2010-2011
        • Year 2009-2010
        • Year 2008-2009
        • Year 2007-2008
        • Year 2006-2007
        • Year 2005-2006
        • Year 2004-2005
        • Year 2003-2004
        • Year 2002-2003
        • Year 2001-2002
        • Year 2000-2001
        • Year 1999-2000
        • Year 1998-1999
      • CMS - Guidelines Forms for Submitting Proposals
        • CMS - Download Guidelines Forms
  • Studies
    • Undergraduate Studies
    • Graduate Studies
    • Postdoctoral Studies
    • Classrooms
    • Courses
      • Service Courses   
      • Math Dep Courses   
    • Mathematics for Youth   
    • Exams for the Technion   
  • Library
    • Collections
    • Library Services
    • Library Staff
    • Exams
    • Exams Store
      • List of Courses
        • List of Courses
        • List of Exams
    • Databases
    • Journals
    • External Math Resources
    • New Books
  • Events
    • Faculty Activities
    • Event
    • Google Calendar of Seminars, Colloquia and Activities
    • Regular Seminars and Colloquia
      • Regular Seminars and Colloquia
      • Regular Seminars and Colloquia
      • Test (vadder)
      • Test (vadder)
      • Colloquium
      • Colloquium
      • PDE and Applied Mathematics Seminar
      • PDE and Applied Mathematics Seminar
      • Nonlinear Analysis and Optimization Seminar
        • Archive
          • Year 2014-2015
          • Year 2013-2014
          • Year 2012-2013
          • Year 2011-2012
          • Year 2010-2011
          • Year 2009-2010
          • Year 2008-2009
          • Year 2007-2008
      • Nonlinear Analysis and Optimization Seminar
      • Geometry and Topology Seminar
      • Geometry and Topology Seminar
      • Groups, Dynamics and Related Topics
      • Groups, Dynamics and Related Topics
      • Combinatorics Seminar
      • Combinatorics Seminar
      • Algebra Seminar
      • Algebra Seminar
      • Let's do research in Mathematics
      • Let's do research in Mathematics
      • Free Analysis Seminar
      • Free Analysis Seminar
      • Operator Algebras/Operator Theory
      • Operator Algebras/Operator Theory
    • Techmath
      • Techmath - Submission Form
      • Techmath - Troubleshooting
    • CMS Activities
      • CMS Activities
      • CMS Activities
    • Special Lectures
      • Netanyahu Lectures
    • Math Club Lectures
      • Math Club Lectures
      • Math Club Lectures
    • News
  • Resources
    • Department Committees
    • Positions
      • Positions
      • Tenure Track Positions
      • PostDoc Research Fellowships
        • Registration for Candidates
      • Visiting Positions
    • Administrative Offices
      • Administrative Offices
      • Test (vadder)
      • Dean of the faculty
      • Head of administration
      • Department secretary
      • Teaching
      • Graduate students
      • Undergraduate students
      • Research secretary
      • Library
      • Network and computer manager
      • CMS
      • Application
    • Computer Farm
      • Staff
      • Magnetic Card Policy
      • Printing Policy
      • Print Help
      • Secure Services
        • Secure Services
        • Get Web Password
        • Change Web Password
        • Check Printing Quota
        • Check/Cancel Printing Jobs
        • Upload Photo
        • Change Home Page
    • Search Services
      • MathSite Map
      • MathSite Search
      • Technion Phone Directory
    • Admin Menu
      • Faculty Activities
      • Faculty Activities
      • News
      • News
  • Gallery
  • About
    • About The Department
    • Contact Information
    • Legend
Decorative Banner

Event № 1934

Event № 1934
TE Combinatorics Seminar - Amnon Ta-Shma 24/05/2017, Wednesday, 13:30
Type: Seminar
Name: Combinatorics Seminar
Title: Explicit, almost optimal, epsilon-balanced codes
Speaker: Amnon Ta-Shma
Place: Amado 814, Technion
Abstract:
The question of finding an epsilon-biased set with close to optimal
support size, or, equivalently, finding an explicit binary code with
distance $\frac{1-\eps}{2}$ and rate close to the Gilbert-Varshamov
bound, attracted a lot of attention in recent decades. In this paper
we solve the problem almost optimally and show an explicit
$\eps$-biased set over $k$ bits with support size
$O(\frac{k}{\eps^{2+o(1)}})$. This improves upon all previous
explicit constructions which were in the order of
$\frac{k^2}{\eps^2}$, $\frac{k}{\eps^3}$ or
$\frac{k^{5/4}}{\eps^{5/2}}$. The result is close to the
Gilbert-Varshamov bound which is $O(\frac{k}{\eps^2})$ and the lower
bound which is $\Omega(\frac{k}{\eps^2 \logeps})$.

The main technical tool we use is bias amplification with the
$s$-wide replacement product. The sum of two independent samples
from an $\eps$-biased set is $\eps^2$ biased. Rozenman and Wigderson
showed how to amplify the bias more economically by choosing two
samples with an expander. Based on that they suggested a recursive
construction that achieves sample size $O(\frac{k}{\eps^4})$. We
show that amplification with a long random walk over the $s$-wide
replacement product reduces the bias almost optimally.
SubmittedBy: Amir Yehudayoff , amir.yehudayoff@gmail.com
EventLink: Event № 1934
Print event № 1934 …
Mathematics for Youth    
  • מרכז נועם לנוער
  • מחנה קיץ בתורת המספרים
  • מחנה קיץ בתורת הגרפים
  • תחרות גרוסמן במתמטיקה
  • חוג ההכנה ללימודי מתמטיקה בטכניון
  • נטגר - כתב עת מתמטי לנוער
  • מתיכון לטכניון - מסלול לימודים לתלמידי תיכון
Mathematics for Youth …
Positions
  • Tenure Track Positions
  • PostDoc Research Fellowships
  • Visiting Positions
  • PostDoc Teaching (In Hebrew) (Downloads/Opens pdf file in a new window)
Positions …
Decorative image for Undergraduate Studies Undergraduate Studies
Decorative image for Graduate Studies Graduate Studies
Decorative image for PostDoc Studies PostDoc Studies
Useful Links
  • Secure Services (MathDep)
  • Exams Store (MathDep)
  • MathNet
  • Moodle
  • Webmail
  • Technion Cloud Services
  • Technion Computer Accounts
  • Technion Help Desk
  • Technion Calendar
  • Technion Phone Directory
  • Home
  • Site Map
  • Legend
  • Search
  • Accessibility Statement (Downloads/Opens pdf file in a new window)