Xiaorui sun uic. Apr 25, 2024 · Xiaorui Sun 1.
Xiaorui sun uic 7 percent higher than the average pay for university and college employees and 88. 41269 LCC C001 TR 2:00 - Lecturer: Xiaorui Sun Scribe: Ian P. One of the most recent records in 2021 lists a job of Assistant Professor and a pay of $122,996. D. 15412v1 [cs. 6 Zoran Amy Brenda Claire Yuri Brenda Amy Claire Xavier Amy Brenda Claire 1 st2 nd3rd Men’s Preference Profile Xiaorui Sun worked as an Assistant Professor for the University of Illinois At Chicago (UIC) and in 2023 had a reported pay of $135,086. In many cases we would prefer a deterministic algorithm over randomized algorithms(e. 5, 13, 1 find the closest pair Fact: Closest pair is adjacent in ordered list So, first sort, then scan adjacent pairs. Xiaorui Sun at UIC. 2. 8, 7, 8. 3 Recap and Outline •Greedy algorithm: • Apr 25, 2024 · Xiaorui Sun 1. Algorithm: randomly and independently choose r May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Parth Deshpande 1 Today and next Lecture Today: Trees for distance (Low Stretch Spanning Tree) Next Lecture: Extenders 2 Low Stretch Spanning Tree 2. 1 Introduction The group isomorphism problem is to determine whether two groups, given by their Cayley (mul-tiplication) tables, are isomorphic. For example, an O(1)round algorithm for MST and con- UIC Computer Science Assistant Professor Xiaorui Sun received a National Science Foundation (NSF) CAREER award, the agency's most prestigious award in support of early-career faculty, for his The 65th Annual Symposium on Foundations of Computer Science (FOCS 2024), sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, will be held in Chicago, IL, USA October 27— October 30, 2024. 25in \setlength{\oddsidemargin}{0pt} \setlength{\textwidth}{440pt} \setlength{\topmargin}{0in} \usepackage{amssymb . In particular, we introduced the concept of ”Stretch”. databases). edu: Valerie Taylor DEPT AFFL vtaylor6@uic. Be the first to comment Nobody's responded to this post yet. 6 percent higher than the average pay for co-workers and 77. Skip to navigation. 2 Stuff Homework 1 due tomorrow 11:59pm Homework 2 will be released tomorrow, due Feb 23 11:59pm. 41269 LCC C001 TR 2:00 - Sun, Xiaorui | Assistant Professor Department of Computer Science 312. today's schedule; 3:15 Xiaorui Sun. Madhur Tulsiani . Cut the graph such that one side is smaller than Assistant Professor Xiaorui Sun received a National Science Foundation (NSF) CAREER award, the most prestigious award in support of early-career faculty, to develop faster graph algorithms crucial to machine learning, data mining, Sun, who came to UIC in 2018, became interested in algorithm design during his PhD studies, noting that he likes to be at the intersection of theory, Xiaorui Sun, PhD Digital Learning Strategic Partner| Intercultural Communicator| Scholar-Practitioner| Researcher| Teacher Educator United States Support for the Webhost service ended August 31, 2023; as a result, this service can no longer be requested. 3-SAT is NP-complete. Desired Output: k~xk 2 = qP i2[n] x 2 or k~xk2 2 = P i2[n] x 2 i. Conquer: Recursively solve each subproblem. nnsoni@uic. Stuff Homework 4 due tomorrow Homework 5 will be released later today (due May 6) • Helpful for final exam preparation 2. 41269 LCC C001 TR 2:00 - MCS courses -- Spring 2024. Minimum Spanning Tree (MST) Given a connected undirected graph ! = (%,’) with real-valued edge weights )!≥0. edu Abstract We provide universally-optimal distributed graph algorithms for (1+ε)-approximate shortest path problems including shortest-path-tree and transshipment. 1 Problem Definition and Naive Solution Input: Matrix A and B where the dimensions of A Schedule of MSCS Classes - MSCS@UIC. Oftentimes if there exists a randomized algorithm we can find a Lecturer: Xiaorui Sun Scribe: Pranavi Alle 1 Last Lecture’s Review •In the last lecture, we reviewed about Graph Representation and its properties that include Generalization, Decomposition and Sparsification. Despitetheextensive Schedule of MSCS Classes - MSCS@UIC. My research interests lie in theoretical computer science, especially in graph algorithms, combinatorial optimization, and spectral graph theory. Assistant Professor Xiaorui Sun received a National Science Foundation (NSF) CAREER award this year, the most prestigious award in support of early-career faculty, to develop faster graph algorithms crucial to machine learning, data mining, and computational biology, through a process known as graph sparsification. 996. Q: Is Yuri-Brenda an unstable pair? A: No, Yuri and Brenda get matched. The funding supports research by UIC’s diverse array of 3,000 faculty members, 7,315 graduate students and 22,107 Apr 25, 2024 · Xiaorui Sun 1. Given n time-stamps x 1, , x n on which Oct 11, 2022 · “There is a lot of data science expertise at UIC and the other participating institutions and bringing them together can turn Chicago into a major data science hub. Case 1: Job * is not in OPT. Suggest URL; Education & Career History. University of Illinois At Chicago (UIC) records show Xiaorui Sun held one job between 2019 and 2021. UIC, CS. Graph is a very powerful representation by itself, however, we want to simplify a graph to make it have better properties so that more information can be computed from the abstract graph. edu Theys, Mitchell Schedule of MSCS Classes - MSCS@UIC. 41269 LCC C001 TR 2:00 - Xiaorui Sun 1. Let us use induction: IH: Suppose we can compute the optimum job scheduling for a set of jobs of size <*. . UIC, ECE. IDEAL Phase 1 (supported by the NSF award CCF 1934931) and UIC TRIPODS Institute (supported by the NSF award CCF 1934915). Lecturer: Xiaorui Sun Scribe: Rishi Advani 1 Last time and today Today, we will be continuing to study matrix multiplication algorithms with time complexity less than O(n3). Xiaorui Sun xiaorui@uic. 1 Goal To produce a graph H such that Laplacian L G = L H. weic,yajunw@microsoft. Lecturer: Xiaorui Sun Scribe: Tanmay Kelkar 1 Last time and today Previously: Solutions for special cases of graph representations can be generalized by approx-imation, decomposition and sparsification. Ega 1 Last Lecture’s Review In the last lecture, we reviewed the algorithm for edge sparsification of the graph, Matrix Concentration and solved the Laplacian system. I received my Ph. 20 according to public records. 6 percent higher than the average pay for university and college employees and 52. While we analysed Bartal’s Algo-rithm we were able to come up with the following conclusion as shown below. Typically, each sub-problem is at most a constant c < 1 fraction of the size of the original problem Conquer: Recursively solve each subproblem Combine: Merge the solutions Examples: Xiaorui Sun. arXiv:2303. Closest Pair of Points Given ! points, find the closest pair. Jul 19, 2023. Last Lecture (summary) Stable matching problem: Given n men and n women, and their preferences, find a stable matching. 43262 LCC C001 TR 3:30 - 4:45 Ajay Kshemkalyani. edu: Mitch Theys Clinical Associate Professor 941 SEO MC 152: 312-413 Xiaorui Sun (Principal Investigator) xiaorui@uic. Open comment sort options. DS] 27 Mar 2023. Please note, the university offers several alternative web hosting solutions with modern features and capabilities that are available to meet your needs. Lecturer: Xiaorui Sun Scribe: Sriman Cherukuru 1 Last Lecture’s Review Last Lecture: Graph decomposition • Utilization of nice properties on good edges (intra-component) • Upper bound on the number of bad edges (inter-component) This Graph problems have been widely researched and possess a broad class of applications. The department engaged in an intensive faculty recruiting effort not only keep pace with that growth—bringing the total number of computer science faculty to 48—but also CS 401: Computer AlgorithmI Representative Problems / Running Time Analysis Xiaorui Sun 1 Pinyan Lu Xiaorui Suny Yajun Wangz Zeyuan Allen Zhux Abstract We consider the problem of locating facilities in a metric space to serve a set of selfish agents. Brute force: Check all ! " pairwise distances 1-dim case: 11, 2, 4, 19, 4. Sort by citations Sort by year In 2022, we won phase II NSF funding and became a part of the Chicago-wide IDEAL institute. University of Chicago, Statistics. Divide and Conquer Divide: Divide problem in to subproblems. • We know the preference of all people. 2 Divide and Conquer. Add This subreddit is not officially endorsed by UIC or any affiliated group. edu: Xiaorui Sun Assistant Professor 1241 SEO MC 152: xiaorui@uic. ” More than 60 researchers will be working on key aspects of the foundations of data science across computer science, electrical engineering, mathematics, statistics, and fields such as May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Kumar Chandrasekhar 1 Recap of Last Lecture Figure 1: Graph Diagram • The standard way to compute distance between two vertices in a graph is Djk-stra’s algorithm. 43263 LCC C001 TR 3:30 - Xiaorui Sun worked as an Assistant Professor for the University of Illinois At Chicago (UIC) and in 2019 had a reported pay of $109,579. candidate advised by Prof. 1 percent higher than the national average for government employees. 355. Despitetheextensive Xiaorui Sun ∗ Abstract The group isomorphism problem determines whether two groups, given by their Cayley ∗xiaorui@uic. 3476 | xiaorui@uic. com 2 Harvard School of Engineering and Applied Sciences. Xiaorui Sun at the University of Illinois at Chicago (UIC) in Chicago, Illinois teaches CS 301 - Languagesand Automata, CS 398 - Undergrad Design/ Research, CS 401 - Computer AlgorithmsI, CS 594 - Machine Learn. Xiaorui Sun Assistant Professor, University of Illinois, Chicago. General Information | Topics | Grading | Scribe Notes | Homework | Final Project. Information about previous conferences can be found at the FOCS Conference Archive. •Breadth First Search (BFS): Order nodes in successive layers based on distance from ! •Depth First Search (DFS): More natural approach for exploring a maze; Applications of BFS: Apr 25, 2024 · Xiaorui Sun 1. Combine: Merge solutions of subproblems to the solution of the original problem Examples: CS 594: Algorithm Methods for Big Data Spring 2020 Lecture 2: Jan 16, 2020 Lecturer: Xiaorui Sun Recall the problem of testing sortedness from the previous lecture. Swift 1 Last time and today Last lecture, we were introduced to the concept that a tree T can represent a graph G(V,E), such that certain desirable properties about the graph are reflected within the representation. 3 percent higher than the national average for government employees. Shortest Paths with Neg Edge Weights Given a weighted directed graph !=#,% and a source vertex &, where the weight of edge (u,v) is Apr 25, 2024 · Xiaorui Sun 1. The Phase II operations of the IDEAL is supported by the National Science Foundation through the TRIPODS HDR program (under the awards EECS 2216970, 2217023, 2216926, 2216912, 2216899). University of Illinois, Chicago (uic. Largest empty interval. undergraduate catalog: courses descriptions up to the 400 level graduate catalog: 400 and 500 level course descriptions \documentclass[12pt]{article} \parindent=. The cost of an agent is the distance between her own location and the nearest facility. Sloan 2018 to 2021: Barbara Di Eugenio 2017 to 2020: Danilo Erricolo, James Patton, Venkat Venkatakrishnan 2015 to 2018: Daniela Tuninetti 2014 to 2017: Philip Yu 2013 to 2016: Sudip Jul 14, 2022 · is cs 401 hard with xiaorui sun? can anyone share their experience as das gupta's class full! Share Add a Comment. 4 percent higher than the average pay for university and college employees and 64. University of Illinois at Chicago Verified email at uic. 3 Greedy Algorithm •Greedy algorithm: • Divide solution construction into small steps • Decision in each step: ‘best’ current partial solution at each step The 2023 total reflects an 11% increase in funding over fiscal year 2022 and a 49% increase since 2018. Suffices to show that CIRCUIT-SAT £ P 3-SAT since 3-SAT is in NP. Articles Cited by Public access. faculty Faculty listings: directory; by research area; by position; emeritus faculty; visiting scholars; teaching assistants; graduate students; associates; staff; 39067 LCF F003 TR 2:00 - How are Yu Cheng, Xiaorui Sun or Sidiriropoulous for (M)CS 401? Which is the better of the three? Share Sort by: Best. This site is therefore no longer being maintained. May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Venkata Likith Ayyagari 1 Last Lecture’s Review In the last lecture, we reviewed the algorithm for edge sparsification of the graph and matrix concentration. 41269 LCC C001 TR 2:00 - Xiaorui Sun xiaorui@uic. edu; Recipient Sponsored Research Office: University of Illinois at Chicago 809 S MARSHFIELD AVE M/C 551 Xiaorui Sun at the University of Illinois at Chicago (UIC) in Chicago, Illinois teaches CS 301 - Languagesand Automata, CS 398 - Undergrad Design/ Research, CS 401 - Computer Mingquan Ye (CS), advisor: Xiaorui Sun, secondary advisor: Yu Cheng Kevin Zhou (MSCS), advisor: James Freitag, secondary advisory: Lev Reyzin Fall 2021 Heading link Copy link Email: mye9 at uic. edu: Wei Tang Assistant Professor 1141 SEO MC 152: 312-355-9088 tangw@uic. Xiaorui Sun is a professor in the Computer Science department at University of Illinois Chicago - see what their students are saying about them or leave a rating yourself. faculty Faculty listings: directory; by research area; by position; emeritus faculty; visiting scholars; teaching assistants; graduate students; associates; staff; seminars. Vishesh Jain receives NSF CAREER award for 2023-28. Assistant Professor. The department engaged in an intensive faculty recruiting effort not only keep pace with that growth—bringing the total number of computer science faculty to 48—but also Lecturer: Xiaorui Sun Scribe: Gnanamanickam Arumugaperumal 1 Last Lecture: • Courant-Fischer and Cheeger’s Inequality • Expanders • Introduced to Expander Decomposition 2 Expanders: Given a graph G that is a Φ expander, when G has a small cut size c then one of the sides of the cut will be smaller than the other. Shortest Paths with Neg Edge Weights Given a weighted directed graph !=#,% and a source vertex &, where the weight of edge (u,v) is ’ Lecturer: Xiaorui Sun Scribe: Xing Gao 1 Last time and today Previously: Graph decomposition (low-diameter, expander decomposition) • Utilize nice properties on good edges (intra-component) • Upper bound number of bad edges (inter-component) Starting today: Graph sparsification (edge, vertex sparsification) Weighted Interval Scheduling • Job ! starts at "(!) and finishes at %! and has weight &! •Two jobs compatible if they don’t overlap. 41269 LCC C001 TR 2:00 - vio ( U ÿW,U ÿW) ⩽ n Consider VÞ U if deg(V) < n, then number of violation ⩽ n → this is ok for us Æ Æ hence we check for cases Lecturer: Xiaorui Sun Scribe: Shahrukh Haider 1 Geometric Data Geometric data is a set of points where each points can be represented by a vector of dimension d P = {x : x Rd} Example: Google maps can be represented by geometric data for d = 2 Figure 1: Google map representation Problem: We have to calculate the distance between two points A and B. edu University of Illinois Chicago, IL, USA Omri Weinstein omri@cs. As of this fall, more than 1,200 undergraduate, master’s, and PhD students are studying computer science at UIC, more than triple the number enrolled in the department just seven years ago. DBLP. This means for any Lecturer: Xiaorui Sun Scribe: Rishi Advani 1 Last time and today Today, we will be continuing to study matrix multiplication algorithms with time complexity less than O(n3). Homework 2 Programming homework on Leetcode • Register a Leetcode account (free), and programming on Leetcode • You can use any programming language • Submit your code to gradescope Lecturer: Xiaorui Sun Scribe: Jake Maranzatto 1 Last time and today • Dynamic Connectivity, Expanders, Expander Pruning 2 Dynamic Connectivity in no(1) time deterministi-cally. Title. May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Sai Anish Garapati 1 Last Lecture’s Review In the last lecture Matrix multiplication was discussed and following algorithms were introduced to solve Matrix multiplication: •Naive Algorithm •Strassen Algorithm •Tensor 2 Today’s Lecture •Matrix multiplication algorithm represented as Bilinear and Apr 25, 2024 · Weighted Job Scheduling by Induction Suppose 1,,* are all jobs. We also had some early discussions about Graph Representations which entailed Well- Lecturer: Xiaorui Sun Scribe: Shashwath Jawaharlal Sathyanarayan 1 Last Lecture’s Review: In the previous few lectures, we were introduced to the concept that a tree T can represent a graph G(V,E), such that certain desirable properties about the graph are reflected within the representation. MCS courses -- Fall 2023. 2, 16, 11. edu (Confirmed) Suggest Email; Personal Links. The problem is de ned below: Input: Sequence a= (a 1;:::;a Apr 25, 2024 · Xiaorui Sun 1. ORCID provides an identifier for individuals to use with their name as they engage in research, scholarship, and innovation activities. 2 Today’s, Lecture: •Approximate of Edit Distance the way it is solved in Dynamic Program. General Information Xiaorui Sun worked as an Assistant Professor for the University of Illinois At Chicago (UIC) and in 2020 had a reported pay of $117,700 according to public records. IDEAL scholar Xiaorui Sun's groundbreaking algorithm for the group isomorphism problem was featured in an article in Quanta Magazine. Pf. Xiaorui Sun 1. Sort. faculty Faculty listings: directory; by research area; by position; emeritus faculty; visiting scholars; 3:15 Xiaorui Sun. Xiaorui Sun, Goran Zuzic SODA 2022. 2 Edge Sparsification of graph (G) 2. • Create a 3-SAT variable x i for each circuit element i. Apr 25, 2024 · O(n log n) Time O(n log n) time. Homepage. Time "(! log !) to sort, if needed, Plus "(!) to scan adjacent Stable Matching Problem Given n men and n women, find a “stable matching”. Given and edge from the original CS 594: Representations in Algorithm Design Spring 2022 Lecture 21: 03/29/2022 Lecturer: Xiaorui Sun Scribe: Arvind Gupta 1 Last time and today • Tensor Rank and Matrix multiplication Three UIC researchers received the prestigious NSF CAREER grant for early career development: Alessandra Eustaquio, who explores drug discovery and development from natural sources such as microorganisms; Vishesh Jain, who conducts research in probability, combinatorics and theoretical computer science; and Xiaorui Sun, who studies the design Lecturer: Xiaorui Sun Scribe: Sai Goutham Reddy Inturi 1 Matrix Multiplication To understand how different algorithms work, we put matrix multiplication through a tensor. 7 October 2024; TLDR. 41269 LCC C001 TR 2:00 - Lecturer: Xiaorui Sun Scribe: Kushal Reddy Palvai 1 Last Lecture’s Review In the last lecture, we discussed how the edge sparsification of the graph works. , CS 597 - Project Research. 3 Minimum Spanning Tree. The increasing large-scale graphs in various applications have necessitated the development of distributed algorithms. Supplemental Public Utilities; Skip navigation. edu Tang, Wei | Assistant Professor Department of Computer Science 312. Typically, each sub-problem is at most a constant c < 1 fraction of the size of the original problem Conquer: Recursively solve each subproblem Combine: Merge the solutions Examples: •Mergesort, Counting Inversions, Binary Search . edu. In order to do signi cantly better, we have to introduce tensors. Undirected Graphs G=(V,E) Notation. 2 Greedy Algorithm •Greedy algorithm: • Divide solution construction into small steps • Decision in each step: ‘best’ current partial solution at each step •Recipe: • Order the input in some way (the most ‘important’ element will be considered first) • Go through the input according to the order University of Illinois At Chicago (UIC) records show Xiaorui Sun held one job between 2019 and 2021. UIC, Math. arXiv. 2 DFS(A),1,2,10,9,8,3,7,6,4,5 1,12,13 Edge code: Tree edge Back edge No Cross Edges! Properties of (undirected) DFS Like BFS(!): •DFS(!) visits " iff there is a path in G from ! to "So, we can use DFS to find connected components •Edges into then-undiscovered vertices define a tree – Apr 25, 2024 · Xiaorui Sun 1. An MST , is a spanning tree whose sum of edge weights is May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Shivali Singh 1 Last time and today Previously: • Introduction to the problem of large matrix multiplication • Approximation algorithm using tensor rank • Schonhage’s Theorem • Analyzed the use of algebraic structure for fast matrix multiplication Today’s lecture: • Geometric data May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Smrithi Balki 1 Last Lecture’s Review In the last lecture, we discussed about the different ways to perform Expander Decom-position 2 Dynamic Connectivity in nO(1) time Definition: Alot of systems want Apr 25, 2024 · 3-SAT is NP-Complete Theorem. Top. Schedule of MSCS Classes - MSCS@UIC. University of Illinois at Chicago. faculty Faculty listings: directory; by research area; by position; emeritus faculty; visiting scholars; teaching assistants; graduate students; associates; staff; 39067 LCF F003 TR 2:00 - Xiaorui Sun xiaorui@uic. TTIC, cs. Three UIC researchers received the prestigious NSF CAREER grant for early career development: Alessandra Eustaquio, who explores drug discovery and development from natural sources such as microorganisms; Vishesh Jain, who conducts research in probability, combinatorics and theoretical computer science; and Xiaorui Sun, who studies the design Xiaorui Sun 1. Gyorgy Turan. • Property: All the distribution of tree should satisfy the following property, Lecturer: Xiaorui Sun Scribe: Siddarth Madanan Menon 1 Last Lecture’s Review In the last lecture, we discussed Bartal’s algorithm. This is 57. why rep-resentations can be useful. 2 Stuff •Homework 2 submission deadline extends to February 27 •In class midterm exam: February 29 Thursday 12:30pm – 1:45pm •Midterm review and details of the exam: February 27. 2 Representations Purpose of studying Representations: We make use of representations to increase the efficiency of the algorithms and view Apr 25, 2024 · Xiaorui Sun 1. The problem is among a few classes of problems in NP that Apr 25, 2024 · Xiaorui Sun 1. Daniela Tuninetti. G = (V, E) •V = nodes (or vertices) •E = edges between pairs of nodes Nov 30, 2023 · Xiaorui Sun 1. Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis FOCS 2015 Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width I am an assistant professor in the Computer Science Department of University of Illinois at Chicago. Theoretical Computer Science. Goal: Handle updates and answer queries as fast as possible. I am a final-year Ph. Inspired by the successful applications of continuous optimization methods in improving some combinatorial optimization problems, we adapt the Schedule of MSCS Classes - MSCS@UIC. org. We are interested in designing strategy-proof mechanisms without payment that Xiaorui Sun§ University of Illinois at Chicago xiaorui@uic. columbia. Mergesort and heapsort are sorting algorithms that perform O(n log n) comparisons. 2 Representations a. A unified and extensive evaluation of a variety of SAM variants across various hardware, assessing their efficiency and accuracy on representative benchmarks, and providing a clear comparison of their overall performance. Polynomial Time Reduction Def A May 10, 2022 · CS 594: Representations in Algorithm Design Spring 2022 Lecture 12: 2/17/2022 Lecturer: Xiaorui Sun Scribe: Jake Maranzatto 1 Last time and today • Dynamic Connectivity, Expanders, Expander Pruning 2 Dynamic Connectivity in no(1) time deterministi- cally. In particular, the concept of ”Stretch” is Schedule of MSCS Classes - MSCS@UIC. 1 Introduction The group isomorphism problem is to determine whether two groups, given by their Cayley (mul-tiplication) tables, are If you take Xiarou Sun his lectures are hard to understand but the class and homework are really easy, Bellos 151 class was harder Reply reply More replies More replies. edu 3 Department of Computer Science, Shanghai Jiao Tong University. Graph Traversal Walk (via edges) from a fixed starting vertex ! to all vertices reachable from !. 41269 LCC C001 TR 2:00 - 3:15 Xiaorui Sun. •Subproblem is at most a constant fraction of the original problem. edu - Homepage. This is 80. Reminder Homework 2 due 11:59pm today Midterm exam: Thursday 12:30pm-1:15pm this classroom Midterm review later this lecture 2. We have already seen Strassen’s algorithm, which has time complexity O(n2:81). IS: Goal: For any * jobs we can compute OPT. Computer Science. 41269 LCC C001 TR 2:00 - CS594:RepresentationsinAlgorithmDesign Spring2022 Lecture on 03/15/2022 Lecturer: Xiaorui Sun Scribe: Muhammed Adeem Shaik 1 LastLecture’sReview Schedule of MSCS Classes - MSCS@UIC. 7 percent higher than the national average for government employees. May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Tianyu Zhu Relevant Reading: Henzinger-King 1999 Problem: Dynamic Connectivity Input changes: maintain a data structure for some problem; Graph updates: edge insertions / deletions, query (x;y). harvard. Dynamic Programming Principle: • Optimal substructure: Remove certain part of the optimal solution (for the entire problem) is an optimal solution of a subproblem • Typically, only a polynomial number of subproblems Technique: • Parameterization: Describe subproblems by parameters so that the Schedule of MSCS Classes - MSCS@UIC. Equivalently, !"=$("%) Apr 25, 2024 · Xiaorui Sun 1. for Graphs/ Net. Members Online. Prior to joining UIC, I was at UC Berkeley Simons Institute and Microsoft Research. undergraduate catalog: courses descriptions up to the 400 level graduate catalog: 400 and 500 level course descriptions Xiaorui Sun, UIC Ewin Tang, Berkeley Kavitha Telikepalli, TIFR Mumbai Vera Traub, Bonn Chris Umans, Caltech Vinod Vaikuntanathan, MIT Santosh Vempala, Georgia Tech (chair) Adrian Vetta, McGill Yusu Wang, UCSD Andre Wibisono, Yale Mihalis Yannakakis, Columbia Huacheng Yu, Princeton Schedule of MSCS Classes - MSCS@UIC. • Make circuit compute correct values at each node: •x 2 = ¬ x 3 Þ add 2 clauses: •x 1 = x 4 Ú x 5 Þ add 3 clauses: •x 0 = x 1 Ù x 2 Þ add 3 clauses: May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Jahnavi R. Starting today: Computing edit distance for strings using exact algorithms (eg: DP) and approx-imation algorithms. Last Lecture Asymptotic notations: O, W, Q Common running times: linear time, O(n log n) time, quadratic time, polynomial time, and exponential time 2. Sorting. 41269 LCC C001 TR 2:00 - MATH courses -- Spring 2025. Minor Sparsifiers and the Distributed Laplacian Paradigm with Sebastian Forster, Gramoz Xiaorui Sun (Preferred) Suggest Name; Emails ****@uic. Joined ; December 2018 Xiaorui Sun's 22 research works with 134 citations and 543 reads, including: Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time Xiaorui Sun (Principal Investigator) xiaorui@uic. Yi Sun. 41269 LCC C001 TR 2:00 - Schedule of MSCS Classes - MSCS@UIC. undergraduate catalog: courses descriptions up to the 400 level graduate catalog: 400 and 500 level course descriptions Lecturer: Xiaorui Sun Scribe: Wenyu Jin 1 Last time: vertex sparsifier andc-edge connec-tivity • Vertex sparsification: Given a graphGand a set of vertices T called the terminals, we aim to find a graphH that also contains vertex set T such that c-connectivity between any pair of terminals are the same on G and on H. Apr 25, 2024 · Xiaorui Sun 1. University of Illinois at Chicago - 2. Finding the Closest Pair of Points. Lecturer: Xiaorui Sun Scribe: Ragavee Poosappagounder Kandavel 1 Last Lecture’s Review In the last lecture, we discussed algorithm to construct Low Stretch Tree for given weighted graph and the output will be distributions of all the trees (not a single tree). 1 Graph Distance(d(x, y)) A graph can have weighted or Apr 25, 2024 · Xiaorui Sun 1. IDEAL faculty Vishesh Jain(UIC) has received an NSF CAREER (Faculty Early Career Development Program) award Lecturer: Xiaorui Sun Scribe: Robert Finedore 1 Last time and today • Matrix multiplication – Naive Algorithm – Strassen Algorithm – Tensor 2 Matrix Multiplication Overview 2. edu; Recipient Sponsored Research Office: University of Illinois at Chicago 809 S MARSHFIELD AVE M/C 551 CHICAGO IL US 60612-4305 (312)996-2862 Jin, Wenyu and Sun, Xiaorui and Thorup, Mikkel "Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time", 2024 Citation Details. Computational Complexity Goal: Classify problems according to the amount of computational resources used by the best algorithms that solve them Here we focus on time complexity 2. 9088 | tangw@uic. 2 Edge Sparsification of graph Given a G = (V,E) -> H = (V,E’) We need to show that graph Schedule of MSCS Classes - MSCS@UIC. Arises in divide-and-conquer algorithms. algorithm for read more. Divide and Conquer Divide: We reduce a problem to several subproblems. Today: Representations can be related to distribution, algebraic structure. undergraduate catalog: courses descriptions up to the 400 level graduate catalog: 400 and 500 level course descriptions Lecturer: Xiaorui Sun Scribe: Bohan Fan 1 Last time and today Last lecture: Testing by learning is not good Today: Testing Uniformity of distribution Input: Given independent samples from a distribution D Output: Yes, if D= U [n] with probability 2 3 No, if L 1(D;U [n]) with probability 2 3 2 Testing Uniformity of distribution Algorithm 1 An Schedule of MSCS Classes - MSCS@UIC. • The time complexity of the algorithm is O(m) where m is the number of edges in a graph. g. edu: Sara-Jo Swiatek ADJ LECTURER 811 SEO MC 152: sswiatek@uic. Best. • Let K be any circuit. edu Columbia University New York, NY, USA 2019, Toronto, ON, Canada Sepehr Assadi, Xiaorui Sun, and Omri Weinstein The next set of improvements reduced the memory per machine to Oe(n). This is 46. This means that for vertex Apr 25, 2024 · CS 401: Computer Algorithm I Single Source Shortest Path / Minimum Spanning Tree Xiaorui Sun 1 Apr 23, 2020 · CS 594: Algorithm Methods for Big Data Spring 2020 Lecture 2: Jan 16, 2020 Lecturer: Xiaorui Sun Recall the problem of testing sortedness from the previous lecture. This subreddit is not officially endorsed by UIC or any affiliated group. 1 Matrix Multiplication Lecturer: Xiaorui Sun Scribe: Nima Shahbazi 1 Last Lecture’s Review In the last lecture, we reviewed several representations of the graph. 3 For a perfect matching M, a pair m-w is unstable if they prefer each other to their match in M. 41268 LCC C001 TR 2:00 - 3:15 Xiaorui Sun. Dynamic Programming Principle: • Optimal substructure: Remove certain part of the optimal solution (for the entire problem) is an optimal solution of a subproblem • Typically, only a polynomial number of subproblems Technique: • Parameterization: Describe subproblems by parameters so that the Apr 25, 2024 · Xiaorui Sun 1. Efficiency 3 An algorithm runs in polynomial time if !"="!(#). Zoran Amy Brenda Claire Instructor: Xiaorui Sun Office hours: Thursday 11am-1pm at SEO 1241 or Blackboard Instructional assistants: Dong Cao (office hour: 10am-12pm Monday), Chunyu Miao (office hour: 3pm-5pm Friday) ORCID record for xiaorui sun. 4 percent higher than the national average for government employees. May 10, 2022 · Lecturer: Xiaorui Sun Scribe: Chinmay Tarwate 1 Last time and today Previously: Graph representations and ideas and connections between different graph representations. zliu@fas. The social cost is the total cost of the agents. New. For groups with order ,analgorithmwith (log + (1))runningtime,attributedtoTarjan, wasproposedinthe1970s(Miller,STOC1978). people. Homework 2 Programming homework on Leetcode • Register a Leetcode account (free), and programming on Leetcode • You can use any programming language • Submit your code to gradescope Skip to main content. G = (V, E) •V = nodes (or vertices) •E = Xiaorui Sun 1. 50. May 10, 2022 · CS 594: Representations in Algorithm Design Spring 2022 Lecture 13: Feb 22, 2022 Lecturer: Xiaorui Sun Scribe: Xing Gao 1 Last time and today Previously: Graph decomposition (low-diameter, expander decomposition) • Utilize nice properties on good edges (intra-component) Mar 28, 2023 · Xiaorui Sun ∗ Abstract The group ∗xiaorui@uic. The universal optimality of our algorithms guarantees that, on any n-node network G, our algorithm completes in T·no(1) rounds whenever a T-round Xiaorui Sun's 3 research works with 62 citations and 107 reads, including: Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs Xiaorui Sun 1. Combine: Merge solutions of subproblems to the solution of the original problem Examples: •Mergesort, Counting inversions, Binary Search Apr 25, 2024 · Xiaorui Sun 1. CS 594: Representations in Algorithm Design Spring 2022. CS Theory Group Lecturer: Xiaorui Sun Scribe: Sai Anish Garapati 1 Last Lecture’s Review In the last lecture Matrix multiplication was discussed and following algorithms were introduced to solve Matrix multiplication: •Naive Algorithm •Strassen Algorithm •Tensor 2 Today’s Lecture •Matrix multiplication algorithm represented as Bilinear and Xiaorui Sun 1. Qiao, Youming A Game-Theoretic Framework to Identify Overlapping Communities in Social Networks Wei Chen1, Zhenming Liu2, Xiaorui Sun3, and Yajun Wang1 1 Microsoft Research Asia, Beijing, China. in 2016 from Columbia University, Xiaorui Sun. Homework 1 Homework 1 was out • Deadline: February 9 11:59pm • Submit your solution to gradescope • More details can be found in the slides of the lecture on January 25 . edu University of Illinois at Chicago United States ABSTRACT The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. Polynomial Time Reduction Def A 2021 to 2024: Eben Alsberg, Abolfazl (Kouros) Mohammadian, Reza Shahbazian-Yassar, Pai-Yen Chen, Kenneth Brezinsky 2020 to 2023: Rashid Ansari 2019 to 2022: Robert H. •Goal: find maximum weight subset of mutually compatible jobs. Stuff Homework 2 is out (due at 11:59pm February 23 Friday) Submit your source code for each problem to gradescope via blackboard. 250 lần trích dẫn - Theoretical Computer Science Schedule of MSCS Classes - MSCS@UIC. Let us consider a 3-tensor : x i y j z k The matrix multiplication tensor would be : t Lecturer: Xiaorui Sun Scribe: Manoj Kumar Alluri 1 Last time and today • Last time : Approximate Edit Distance • Today : Algebraic Representation(Matrix Multiplication), Strassen algorithm, Algebraic Definitions 2 Algebraic Representation In this we are going to introduce some algebraic structures. Papers presenting new Xiaorui Sun Jun Liu Hengtao Shen Xiaofeng Zhu Ping Hu. Apr 23, 2020 · CS 594: Algorithm Methods for Big Data Spring 2020 Lecture 14: Feb 27, 2020 Lecturer: Xiaorui Sun 1 Sketching for L 2 Norms Data Stream: updates of a vector ~x, (x i; = 1) : x i x i+ . Shortest Paths with Negative Edge Weights. 19 according to public records. This is 29. edu) Science and Engineering Offices (SEO), 851 South Morgan Street, University of Illinois at Chicago, Chicago, IL 60607 Xiaorui Sun's 22 research works with 134 citations and 543 reads, including: Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time As of this fall, more than 1,200 undergraduate, master’s, and PhD students are studying computer science at UIC, more than triple the number enrolled in the department just seven years ago. kqo gcld pdxfd hmgu fkar flshhbxb jesfyw urcxr lkzr ukx