Shang-Hua Teng

ORCID

Publication Activity (10 Years)

Years Active: 1987-2024
Publications (10 Years): 43

Top Venues

Publications

Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Open Problem: Can Local Regularization Learn All Multiclass Problems? COLT (2024)
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Nimber-preserving reduction: Game secrets and homomorphic Sprague-Grundy theorem. Theor. Comput. Sci. 1005 (2024)
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Learnability is a Compact Property. CoRR (2024)
Siwei Wang, Yifei Shen, Shi Feng, Haoran Sun, Shang-Hua Teng, Wei Chen
ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models. CoRR (2024)
Kyle Burke, Matthew Ferland, Svenja Huntemann, Shang-Hua Teng
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers. FUN (2024)
Kyle Burke, Matthew Ferland, Svenja Huntemann, Shang-Hua Teng
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers. CoRR (2024)
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Regularization and Optimal Multiclass Learning. COLT (2024)
Shang-Hua Teng
Technical Perspective: Maximum Flow through a Network: A Storied Problem and a Groundbreaking Solution. Commun. ACM 66 (12) (2023)
Julian Asilis, Siddartha Devic, Shaddin Dughmi, Vatsal Sharan, Shang-Hua Teng
Regularization and Optimal Multiclass Learning. CoRR (2023)
Rumi Ghosh, Kristina Lerman, Tawan Surachawala, Konstantin Voevodski, Shang-Hua Teng
Non-conservative diffusion and its application to social network analysis. J. Complex Networks 12 (1) (2023)
Shang-Hua Teng
"Intelligent Heuristics Are the Future of Computing". ACM Trans. Intell. Syst. Technol. 14 (6) (2023)
Kyle W. Burke, Matthew Ferland, Shang-Hua Teng
Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. FUN (2022)
Kyle W. Burke, Matthew Ferland, Shang-Hua Teng
Quantum-Inspired Combinatorial Games: Algorithms and Complexity. FUN (2022)
Kyle W. Burke, Matthew T. Ferland, Shang-Hua Teng
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. FOCS (2022)
Shang-Hua Teng
Beyond Traditional Characterizations in the Age of Data: Big Models, Scalable Algorithms, and Meaningful Solutions. KDD (2022)
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings. CoRR (2021)
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim. CoRR (2021)
Sina Dehghani, Hamed Saleh, Saeed Seddighin, Shang-Hua Teng
Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable. AAAI (2021)
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. CoRR (2021)
Kyle W. Burke, Matthew T. Ferland, Shang-Hua Teng
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography. FOCS (2021)
Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis. SODA (2020)
Wei Chen, Shang-Hua Teng, Hanrui Zhang
A graph-theoretical basis of stochastic-cascading network influence: Characterizations of influence-based centrality. Theor. Comput. Sci. (2020)
Wei Chen, Shang-Hua Teng, Hanrui Zhang
On the Equivalence Between High-Order Network-Influence Frameworks: General-Threshold, Hypergraph-Triggering, and Logic-Triggering Models. CoRR (2020)
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Quantum Combinatorial Games: Structures and Computational Complexity. CoRR (2020)
Wei Chen, Shang-Hua Teng, Hanrui Zhang
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. ITCS (2019)
Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, Jialin Zhang
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis. CoRR (2019)
Wei Chen, Shang-Hua Teng, Hanrui Zhang
A Systematic Framework and Characterization of Influence-Based Network Centrality. CoRR (2018)
Shang-Hua Teng
Scalable Algorithms in the Age of Big Data and Network Sciences: Characterization, Primitives, and Techniques. WSDM (2018)
Shang-Hua Teng
Going Beyond Traditional Characterizations in the Age of Big Data and Network Sciences (Invited Talk). ISAAC (2018)
Wei Chen, Shang-Hua Teng, Hanrui Zhang
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. CoRR (2018)
Shang-Hua Teng
Network Essence: PageRank Completion and Centrality-Conforming Markov Chains. CoRR (2017)
Wei Chen, Shang-Hua Teng
Interplay between Social Influence and Network Centrality: A Comparative Study on Shapley Centrality and Single-Node-Influence Centrality. WWW (2017)
Xiaoran Yan, Shang-Hua Teng, Kristina Lerman
Multi-layer Network Composition Under a Unified Dynamical Process. SBP-BRiMS (2017)
Xingwu Liu, Shang-Hua Teng
Maximum bipartite matchings with low rank data: Locality and perturbation analysis. Theor. Comput. Sci. 621 (2016)
Xiaoran Yan, Shang-Hua Teng, Kristina Lerman, Rumi Ghosh
Capturing the interplay of dynamics and networks through parameterizations of Laplacian operators. PeerJ Comput. Sci. 2 (2016)
Wei Chen, Shang-Hua Teng
Interplay between Social Influence and Network Centrality: Shapley Values and Scalable Algorithms. CoRR (2016)
Shang-Hua Teng
Scalable Algorithms for Data and Network Analysis. Found. Trends Theor. Comput. Sci. 12 (1-2) (2016)
Christian Borgs, Jennifer T. Chayes, Adrian Marple, Shang-Hua Teng
An Axiomatic Approach to Community Detection. ITCS (2016)
Kristina Lerman, Shang-Hua Teng, Xiaoran Yan
Network Composition from Multi-layer Data. CoRR (2016)
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng
Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification. COLT (2015)
Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng
Mixture Selection, Mechanism Design, and Signaling. FOCS (2015)
Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng
Mixture Selection, Mechanism Design, and Signaling. CoRR (2015)
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng
Spectral Sparsification of Random-Walk Matrix Polynomials. CoRR (2015)
Rumi Ghosh, Shang-Hua Teng, Kristina Lerman, Xiaoran Yan
The interplay between dynamics and networks: centrality, communities, and cheeger inequality. KDD (2014)
Daniel A. Spielman, Shang-Hua Teng
Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM J. Matrix Anal. Appl. 35 (3) (2014)
Nikolaos Laoutaris, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng
Bounded Budget Connection (BBC) games or how to make friends and influence people, on a budget. J. Comput. Syst. Sci. 80 (7) (2014)
Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Shang-Hua Teng
Signaling in Quasipolynomial time. CoRR (2014)
Christian Borgs, Jennifer T. Chayes, Adrian Marple, Shang-Hua Teng
Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities. CoRR (2014)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Efficient Clustering with Limited Distance Information. CoRR (2014)
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Shang-Hua Teng
Multiscale Matrix Sampling and Sublinear-Time PageRank Computation. Internet Math. 10 (1-2) (2014)
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models. CoRR (2014)
Rumi Ghosh, Kristina Lerman, Shang-Hua Teng, Xiaoran Yan
The Interplay Between Dynamics and Networks: Centrality, Communities, and Cheeger Inequality. CoRR (2014)
Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng
Reducibility among Fractional Stability Problems. SIAM J. Comput. 42 (6) (2013)
Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, Shang-Hua Teng
Spectral sparsification of graphs: theory and algorithms. Commun. ACM 56 (8) (2013)
Daniel A. Spielman, Shang-Hua Teng
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM J. Comput. 42 (1) (2013)
László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, John Wilmes
Faster Canonical Forms for Strongly Regular Graphs. FOCS (2013)
Xi Chen, Xiaorui Sun, Shang-Hua Teng
Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems. STOC (2013)
Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng
Finding Endogenously Formed Communities. SODA (2013)
Xingwu Liu, Shang-Hua Teng
Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data. COCOON (2013)
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Shang-Hua Teng
A Sublinear Time Algorithm for PageRank Computations. WAW (2012)
Weiyu Zhang, Stella X. Yu, Shang-Hua Teng
Power SVM: Generalization with exemplar classification uncertainty. CVPR (2012)
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Shang-Hua Teng
Sublinear Time Algorithm for PageRank Computations and Related Applications CoRR (2012)
Maria-Florina Balcan, Christian Borgs, Mark Braverman, Jennifer T. Chayes, Shang-Hua Teng
I Like Her more than You: Self-determined Communities CoRR (2012)
Wei Chen, Christian Sommer, Shang-Hua Teng, Yajun Wang
A compact routing scheme and approximate distance oracle for power-law graphs. ACM Trans. Algorithms 9 (1) (2012)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Active Clustering of Biological Sequences. J. Mach. Learn. Res. 13 (2012)
Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. STOC (2011)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function CoRR (2011)
Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng
Competitive routing over time. Theor. Comput. Sci. 412 (39) (2011)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Min-sum Clustering of Protein Sequences with Limited Distance Information. SIMBAD (2011)
Daniel A. Spielman, Shang-Hua Teng
Spectral Sparsification of Graphs. SIAM J. Comput. 40 (4) (2011)
Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu
Bounded budget betweenness centrality game for strategic network formations. Theor. Comput. Sci. 412 (52) (2011)
Michael A. Bender, Bradley C. Kuszmaul, Shang-Hua Teng, Kebin Wang
Optimal Cache-Oblivious Mesh Layouts. Theory Comput. Syst. 48 (2) (2011)
John Dunagan, Daniel A. Spielman, Shang-Hua Teng
Smoothed analysis of condition numbers and complexity implications for linear programming. Math. Program. 126 (2) (2011)
Zornitsa Kozareva, Konstantin Voevodski, Shang-Hua Teng
Class Label Enhancement via Related Instances. EMNLP (2011)
Xi Chen, Shang-Hua Teng
A Complexity View of Markets with Social Influence. ICS (2011)
Rumi Ghosh, Kristina Lerman, Tawan Surachawala, Konstantin Voevodski, Shang-Hua Teng
Non-Conservative Diffusion and its Application to Social Network Analysis CoRR (2011)
Xi Chen, Xiaoming Sun, Shang-Hua Teng
Quantum Separation of Local Search and Fixed Point Computation. Algorithmica 56 (3) (2010)
Mohammad Taghi Hajiaghayi, Shang-Hua Teng
Foreword to special issue on SODA 2008. ACM Trans. Algorithms 6 (4) (2010)
Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng
Metric uniformization and spectral bounds for graphs CoRR (2010)
Shang-Hua Teng
Beyond convexity: local search and equilibrium computation. BQGT (2010)
Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs CoRR (2010)
Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng
Subgraph sparsification and nearly optimal ultrasparsifiers. STOC (2010)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Efficient Clustering with Limited Distance Information. UAI (2010)
Shang-Hua Teng
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs. TAMC (2010)
Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng
On the complexity of equilibria in markets with additively separable utilities. BQGT (2010)
Xi Chen, Shang-Hua Teng
A Complexity View of Markets with Social Influence CoRR (2010)
Konstantin Voevodski, Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng, Yu Xia
Efficient Clustering with Limited Distance Information CoRR (2010)
Daniel A. Spielman, Shang-Hua Teng
Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52 (10) (2009)
Xi Chen, Shang-Hua Teng
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria CoRR (2009)
Maria-Florina Balcan, Heiko Röglin, Shang-Hua Teng
Agnostic Clustering. ALT (2009)
Martin Hoefer, Vahab S. Mirrokni, Heiko Röglin, Shang-Hua Teng
Competitive Routing over Time. WINE (2009)
Yingchao Zhao, Shang-Hua Teng
Combinatorial and spectral aspects of nearest neighbor graphs in doubling dimensional and nearly-Euclidean spaces. Theor. Comput. Sci. 410 (11) (2009)
Heiko Röglin, Shang-Hua Teng
Smoothed Analysis of Multiobjective Optimization. FOCS (2009)
Yingchao Zhao, Wei Chen, Shang-Hua Teng
The isolation game: A game of distances. Theor. Comput. Sci. 410 (47-49) (2009)
Xi Chen, Li-Sha Huang, Shang-Hua Teng
Market equilibria with hybrid linear-Leontief utilities. Theor. Comput. Sci. 410 (17) (2009)
Xiaohui Bei, Wei Chen, Shang-Hua Teng, Jialin Zhang, Jiajie Zhu
Bounded Budget Betweenness Centrality Game for Strategic Network Formations. ESA (2009)
Xi Chen, Decheng Dai, Ye Du, Shang-Hua Teng
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities. FOCS (2009)
Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng
Learning and Smoothed Analysis. FOCS (2009)
Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng
Reducibility Among Fractional Stability Problems. Electron. Colloquium Comput. Complex. 16 (2009)
Wei Chen, Christian Sommer, Shang-Hua Teng, Yajun Wang
Compact Routing in Power-Law Graphs. DISC (2009)

Shang-Hua Teng.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shang-Hua Teng