Date & Time:
November 29, 2022 3:30 pm – 4:30 pm
Location:
Kent 107, 1020-24 East 58th St., Chicago, IL, 60637
11/29/2022 03:30 PM 11/29/2022 04:30 PM America/Chicago Vladimir Podolskii (NYU) – Constant-Depth Sorting Networks CS Theory Seminar Kent 107, 1020-24 East 58th St., Chicago, IL, 60637

We consider sorting networks that are constructed from comparators of arity k>2. That is, in our setting the arity of the comparators — or, in other words, the number of inputs that can be sorted at the unit cost — is a parameter. We study its relationship with two other parameters — n, the number of inputs, and d, the depth. This model received considerable attention. Partly, its motivation is to better understand the structure of sorting networks. In particular, sorting networks with large arity are related to recursive constructions of ordinary sorting networks. Additionally, studies of this model have natural correspondence with a recent line of work on constructing circuits for majority functions from majority gates of lower fan-in.

We obtain the first lower bounds on the arity of constant-depth sorting networks. More precisely, we consider sorting networks of depth d up to 4, and determine the minimal k for which there is such a network with comparators of arity k. For depths d=1, 2 we observe that k=n. For d=3 we show that k=n/2. For d=4 the minimal arity becomes sublinear: k=\Theta(n^{2/3}). This contrasts with the case of majority circuits, in which k=O(n^{2/3}) is achievable already for depth d=3.

The talk is based on joint work with Natalia Dobrokhotova-Maikova and Alexander Kozachinskiy.

Speakers

Vladimir Podolskii

Visiting Associate Professor, Courant Institute of Mathematical Sciences, NYU

Vladimir Podolskii defended his PhD thesis in 2009 in Moscow State University. His research areas are computational complexity, tropical algebra, applications of complexity theory to databases augmented with logical theories. He is on leave from Steklov Mathematical Institute (Moscow) and a visiting faculty at NYU.

Related News & Events

Students posing at competition

UChicago Undergrad Team Places Second Overall In Regionals For World’s Largest Programming Competition

Mar 17, 2023
Haifeng Xu

New CS and DSI Faculty Haifeng Xu Brings Strategic Intelligence to NeurIPS 2022

Nov 28, 2022

UChicago CS Research Finds New Angle on Database Query Processing with Geometry

Nov 08, 2022

Asst. Prof. Aloni Cohen Receives Award For Revealing Flaws in Deidentifying Data

Sep 09, 2022

UChicago Hosts NSF Workshop on Frontiers of Quantum Advantage

Aug 15, 2022

New 2022-23 Faculty Add Expertise in Linguistics, Visualization, Economics, and Data Science Education

Aug 11, 2022

UChicago Co-Leads $10 Million NSF Institute on Foundations of Data Science

Aug 09, 2022

Bill Fefferman Comments on New Standards for Quantum-Proof Cryptography

Jul 07, 2022

UChicago London Colloquium Features Data Science, Quantum Research

Jul 01, 2022

Faculty Bill Fefferman and Chenhao Tan Receive Google Research Scholar Awards

Jun 21, 2022

First-Year PhD Student Co-Authors Outstanding Paper Award Winner at TQC 2022

Apr 28, 2022

Quanta Magazine Features Prof. Bill Fefferman’s Work on Quantum Algorithms

Jan 20, 2022
arrow-down-largearrow-left-largearrow-right-large-greyarrow-right-large-yellowarrow-right-largearrow-right-smallbutton-arrowclosedocumentfacebookfacet-arrow-down-whitefacet-arrow-downPage 1CheckedCheckedicon-apple-t5backgroundLayer 1icon-google-t5icon-office365-t5icon-outlook-t5backgroundLayer 1icon-outlookcom-t5backgroundLayer 1icon-yahoo-t5backgroundLayer 1internal-yellowinternalintranetlinkedinlinkoutpauseplaypresentationsearch-bluesearchshareslider-arrow-nextslider-arrow-prevtwittervideoyoutube