Undergraduate teaching assistants (UTAs) office hours are an approachable way for students to get help, but little is known about why and for what do the students choose to attend office hours. We sought to understand what kind of help the students believe they need by analyzing the problem-solving step students self-reported when joining the office hours queue app. We used the UPIC framework to aggregate course specific problem-solving steps to enable comparing between seven data sets from a CS1 and a data science course across four semesters. We then compared the class-level and student-level phase distributions to understand the differences between the two courses and the two levels in the courses. We found most students have a "primary phase" where a majority of their interactions fall, and there are significant individual differences in their phase distributions. Moreover, we did not find either students' demographics or the context of their first visits to significantly impact their individual differences in the phase distributions, suggesting students may have fixed beliefs on how to approach office hours. Finally, a strong majority of interactions happen within 3 days of the deadline, such that the UPIC distribution for those days looks like the class-level phase distribution.

                
                @inproceedings{DBLP:conf/sigcse/KoS23,
                  author       = {Shao{-}Heng Ko and
                                  Kristin Stephens{-}Martinez},
                  title        = {What Drives Students to Office Hours: Individual Differences and Similarities},
                  booktitle    = {{SIGCSE} {(1)}},
                  pages        = {959--965},
                  publisher    = {{ACM}},
                  year         = {2023}
                }
                                
            

In this paper, we propose to use the concept of local fairness for auditing and ranking redistricting plans. Given a redistricting plan, a deviating group is a population-balanced contiguous region in which a majority of individuals are of the same interest and in the minority of their respective districts; such a set of individuals have a justified complaint with how the redistricting plan was drawn. A redistricting plan with no deviating groups is called locally fair. We show that the problem of auditing a given plan for local fairness is NP-complete. We present an MCMC approach for auditing as well as ranking redistricting plans. We also present a dynamic programming based algorithm for the auditing problem that we use to demonstrate the efficacy of our MCMC approach. Using these tools, we test local fairness on real-world election data, showing that it is indeed possible to find plans that are almost or exactly locally fair. Further, we show that such plans can be generated while sacrificing very little in terms of compactness and existing fairness measures such as competitiveness of the districts or seat shares of the plans.

                
                @inproceedings{DBLP:conf/nips/Ko0AM22,
                  author       = {Shao{-}Heng Ko and
                                  Erin Taylor and
                                  Pankaj K. Agarwal and
                                  Kamesh Munagala},
                  title        = {All Politics is Local: Redistricting via Local Fairness},
                  booktitle    = {NeurIPS},
                  year         = {2022}
                }
                                
            

We study the power of price discrimination via an intermediary in bilateral trade, when there is a revenue-maximizing seller selling an item to a buyer with a private value drawn from a prior. Between the seller and the buyer, there is an intermediary that can segment the market by releasing information about the true values to the seller. This is termed signaling, and enables the seller to price discriminate. In this setting, Bergemann et al. showed the existence of a signaling scheme that simultaneously raises the optimal consumer surplus, guarantees the item always sells, and ensures the seller's revenue does not increase. Our work extends the positive result of Bergemann et al. to settings where the type space is larger, and where optimal auction is randomized, possibly over a menu that can be exponentially large. In particular, we consider two settings motivated by budgets: The first is when there is a publicly known budget constraint on the price the seller can charge and the second is the FedEx problem where the buyer has a private deadline or service level (equivalently, a private budget that is guaranteed to never bind). For both settings, we present a novel signaling scheme and its analysis via a continuous construction process that recreates the optimal consumer surplus guarantee of Bergemann et al. The settings we consider are special cases of the more general problem where the buyer has a private budget constraint in addition to a private value. We finally show that our positive results do not extend to this more general setting. Here, we show that any efficient signaling scheme necessarily transfers almost all the surplus to the seller instead of the buyer.

                
                @inproceedings{DBLP:conf/sigecom/KoM22,
                  author       = {Shao{-}Heng Ko and
                                  Kamesh Munagala},
                  title        = {Optimal Price Discrimination for Randomized Mechanisms},
                  booktitle    = {{EC}},
                  pages        = {477--496},
                  publisher    = {{ACM}},
                  year         = {2022}
                }
                                
            

We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition Π of the plane into regions so that each region contains roughly σ=n/k points. Π should satisfy a notion of "local" fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in Π if it belongs to the minority party. A group D of roughly σ contiguous points is called a deviating group with respect to Π if majority of points in D are unhappy in Π. The partition Π is locally fair if there is no deviating group with respect to Π. This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and "beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of σ, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.

                
                @inproceedings{DBLP:conf/aaai/AgarwalKM022,
                  author       = {Pankaj K. Agarwal and
                                  Shao{-}Heng Ko and
                                  Kamesh Munagala and
                                  Erin Taylor},
                  title        = {Locally Fair Partitioning},
                  booktitle    = {{AAAI}},
                  pages        = {4752--4759},
                  publisher    = {{AAAI} Press},
                  year         = {2022}
                }
                                
            

With the rapid advent of Virtual Reality (VR) technology and virtual tour applications, there is a research need on spatial queries tailored for simultaneous movements in both the physical and virtual worlds. Traditional spatial queries, designed mainly for one world, do not consider the entangled dual worlds in VR. In this paper, we first investigate the fundamental shortest-path query in VR as the building block for spatial queries, aiming to avoid hitting boundaries and obstacles in the physical environment by leveraging Redirected Walking (RW) in Computer Graphics. Specifically, we first formulate Dual-world Redirected-walking Obstacle-free Path (DROP) to find the minimum-distance path in the virtual world, which is constrained by the RW cost in the physical world to ensure immersive experience in VR. We prove DROP is NP-hard and design a fully polynomial-time approximation scheme, Dual Entangled World Navigation (DEWN), by finding Minimum Immersion Loss Range (MIL Range). Afterward, we show that the existing spatial query algorithms and index structures can leverage DEWN as a building block to support kNN and range queries in the dual worlds of VR. Experimental results and a user study with implementation in HTC VIVE manifest that DEWN outperforms the baselines with smoother RW operations in various VR scenarios.

                
                @inproceedings{DBLP:conf/cikm/KoLLLY19,
                  author       = {Shao{-}Heng Ko and
                                  Ying{-}Chun Lin and
                                  Hsu{-}Chao Lai and
                                  Wang{-}Chien Lee and
                                  De{-}Nian Yang},
                  title        = {On {VR} Spatial Query for Dual Entangled Worlds},
                  booktitle    = {{CIKM}},
                  pages        = {9--18},
                  publisher    = {{ACM}},
                  year         = {2019}
                }
                                
            

Research on new queries for finding dense subgraphs and groups has been actively pursued due to their many applications, especially in social network analysis and graph mining. However, existing work faces two major weaknesses: i) incapability of supporting personalized neighborhood density, and ii) inability to find sparse groups. To tackle the above issues, we propose a new query, called Density-Customized Social Group Query (DCSGQ), that accommodates the need for personalized density by allowing individual users to flexibly configure their social tightness (and sparseness) for the target group. The proposed DCSGQ is general due to flexible in configuration of neighboring social density in queries. We prove the NP-hardness and inapproximability of DCSGQ, formulate an Integer Program (IP) as a baseline, and propose an efficient algorithm, FSGSel-RR, by relaxing the IP. We then propose a fixed-parameter tractable algorithm with a performance guarantee, named FSGSel-TD, and further combine it with FSGSel-RR into a hybrid approach, named FSGSel-Hybrid, in order to strike a good balance between solution quality and efficiency. Extensive experiments on multiple large real datasets demonstrate the superior solution quality and efficiency of our approaches over existing subgraph and group queries.

                
                @article{DBLP:journals/pvldb/ShenKLLY22,
                  author       = {Chih{-}Ya Shen and
                                  Shao{-}Heng Ko and
                                  Guang{-}Siang Lee and
                                  Wang{-}Chien Lee and
                                  De{-}Nian Yang},
                  title        = {Density Personalized Group Query},
                  journal      = {Proc. {VLDB} Endow.},
                  volume       = {16},
                  number       = {4},
                  pages        = {615--628},
                  year         = {2022}
                }
                                
            

Shopping in VR malls has been regarded as a paradigm shift for E-commerce, but most of the conventional VR shopping platforms are designed for a single user. In this paper, we envisage a scenario of VR group shopping, which brings major advantages over conventional group shopping in brick-and-mortar stores and Web shopping: 1) configure flexible display of items and partitioning of subgroups to address individual interests in the group, and 2) support social interactions in the subgroups to boost sales. Accordingly, we formulate the Social-aware VR Group-Item Configuration (SVGIC) problem to configure a set of displayed items for flexibly partitioned subgroups of users in VR group shopping. We prove SVGIC is NP-hard to approximate within (32/31)−ϵ. We design an approximation algorithm based on the idea of Co-display Subgroup Formation (CSF) to configure proper items for display to different subgroups of friends. Experimental results on real VR datasets and a user study with hTC VIVE manifest that our algorithms outperform baseline approaches by at least 30.1% of solution quality.

                
                @article{DBLP:journals/pvldb/KoLSLYY20,
                  author       = {Shao{-}Heng Ko and
                                  Hsu{-}Chao Lai and
                                  Hong{-}Han Shuai and
                                  Wang{-}Chien Lee and
                                  Philip S. Yu and
                                  De{-}Nian Yang},
                  title        = {Optimizing Item and Subgroup Configurations for Social-Aware {VR}
                                  Shopping},
                  journal      = {Proc. {VLDB} Endow.},
                  volume       = {13},
                  number       = {8},
                  pages        = {1275--1289},
                  year         = {2020}
                }
                                
            

TBA

                
                TBA
                                
            

Academic help-seeking is a vital part of students' self-regulated learning strategies. Computing students' help-seeking horizon has seen several transformations in the past 15 years such that past findings no longer capture current computing students' learning environment, motivating a dedicated study on computing students' help-seeking behavior. Building on extant works that on a single course or help source, my research investigates computing students' help-seeking behavior across different contexts. By analyzing students' help-seeking records, I found substantial individual differences in the kind of help sought in office hours. Other preliminary results include correlational analysis on students' help-seeking metrics and pattern analysis on students help-seeking event sequences.