ST
Shang-Hua Teng
cs.DScs.CCcs.LGcs.GTcs.SIstat.MLcs.AIcs.DMmath.COcs.NA
On Valency
published · living versionsW_5w3c7mnb·v1 · currentpublished
Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors
with Qian Li
1 version
W_4gqfqjj6·v1published
Preprints & journals
61 papers in the corpus · 1998–2026Approximate Solomonoff Induction: On the Robustness of Learned Universal Predictors2610.29289v1 · Qian Li, Shang-Hua Teng2026 · 0 citationsarXivon Valency
Learning When to Abort in Transformer Planning: A Mechanistic Study2610.25300v1 · Shi Feng, Qimin Zhong, Siwei Wang et al.2026 · 0 citationsarXivon Valency
Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper Learning2608.26516v1 · Julian Asilis, Shaddin Dughmi, Vatsal Sharan et al.2026 · 0 citationsarXiv
Prediction Under Imperfect Compression: A Theory of Approximate MDL2606.04834v1 · Qian Li, Xinyu Mao, Shang-Hua Teng et al.2026 · 0 citationsarXiv
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete2606.01532v2 · Qian Li, Xinyu Mao, Shang-Hua Teng2026 · 0 citationsarXiv
A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse2605.11302v2 · Atul Ganju, Travis McVoy, Shaddin Dughmi et al.2026 · 0 citationsarXiv
Submodular Maximization under Supermodular Constraint: Greedy Guarantees2602.16240v3 · Ajitesh Srivastava, Shanghua Teng2026 · 0 citationsarXiv
Benefits and Pitfalls of Reinforcement Learning for Language Model Planning: A Theoretical Perspective2509.22613v2 · Siwei Wang, Yifei Shen, Haoran Sun et al.2025 · 1 citationarXiv
Semi-Random Graphs, Robust Asymmetry, and Reconstruction2509.21516v2 · Julian Asilis, Xi Chen, Dutch Hansen et al.2025 · 0 citationsarXiv
Proper Learnability and the Role of Unlabeled Data2502.10359v2 · Julian Asilis, Siddartha Devic, Shaddin Dughmi et al.2025 · 0 citationsarXiv
Overcoming Non-Submodularity: Towards Constant Approximation for Network Immunization2410.19205v5 · Ajitesh Srivastava, Shang-Hua Teng2024 · 0 citationsarXiv
ALPINE: Unveiling the Planning Capability of Autoregressive Learning in Language Models2405.09220v3 · Siwei Wang, Yifei Shen, Shi Feng et al.2024 · 1 citationarXiv
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers2403.04955v1 · Kyle Burke, Matthew Ferland, Svenja Huntemann et al.2024 · 0 citationsarXiv
Transductive Learning Is Compact2402.10360v3 · Julian Asilis, Siddartha Devic, Shaddin Dughmi et al.2024 · 0 citationsarXiv
Regularization and Optimal Multiclass Learning2309.13692v2 · Julian Asilis, Siddartha Devic, Shaddin Dughmi et al.2023 · 1 citationarXiv
Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings2109.05622v2 · Kyle Burke, Matthew Ferland, Shanghua Teng2021 · 1 citationarXiv
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography2106.02114v1 · Kyle Burke, Matthew Ferland, Shanghua Teng2021 · 2 citationsarXiv
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim2101.07237v2 · Kyle Burke, Matthew Ferland, Shanghua Teng2021 · 3 citationsarXiv
On the Equivalence Between High-Order Network-Influence Frameworks: General-Threshold, Hypergraph-Triggering, and Logic-Triggering Models2012.00355v1 · Wei Chen, Shang-Hua Teng, Hanrui Zhang2020 · 1 citationarXiv
Quantum Combinatorial Games: Structures and Computational Complexity2011.03704v1 · Kyle Burke, Matthew Ferland, Shang-Hua Teng2020 · 2 citationsarXiv
Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis1907.05087v3 · Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng et al.2019 · 45 citationsarXiv
A Systematic Framework and Characterization of Influence-Based Network Centrality1810.09981v1 · Wei Chen, Shang-Hua Teng, Hanrui Zhang2018 · 0 citationsarXiv
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity1805.04436v3 · Wei Chen, Shang-Hua Teng, Hanrui Zhang2018 · 6 citationsarXiv
Network Essence: PageRank Completion and Centrality-Conforming Markov Chains1708.07906v1 · Shang-Hua Teng2017 · 5 citationsarXiv
Network Composition from Multi-layer Data1609.01641v1 · Kristina Lerman, Shang-Hua Teng, Xiaoran Yan2016 · 2 citationsarXiv
Interplay between Social Influence and Network Centrality: A Comparative Study on Shapley Centrality and Single-Node-Influence Centrality1602.03780v6 · Wei Chen, Shang-Hua Teng2016 · 15 citationsarXiv
Mixture Selection, Mechanism Design, and Signaling1508.03679v1 · Yu Cheng, Ho Yee Cheung, Shaddin Dughmi et al.2015 · 42 citationsarXiv
Spectral Sparsification of Random-Walk Matrix Polynomials1502.03496v1 · Dehua Cheng, Yu Cheng, Yan Liu et al.2015 · 10 citationsarXiv
Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities1410.5152v1 · Christian Borgs, Jennifer Chayes, Adrian Marple et al.2014 · 1 citationarXiv
Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models1410.5392v1 · Dehua Cheng, Yu Cheng, Yan Liu et al.2014 · 5 citationsarXiv
Efficient Clustering with Limited Distance Information1408.2045v1 · Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin et al.2014 · 2 citationsarXiv
Finding Endogenously Formed Communities1201.4899v2 · Maria-Florina Balcan, Christian Borgs, Mark Braverman et al.2012 · 0 citationsarXiv
Non-Conservative Diffusion and its Application to Social Network Analysis1102.4639v3 · Rumi Ghosh, Kristina Lerman, Tawan Surachawala et al.2011 · 33 citationsarXiv
Clustering Protein Sequences Given the Approximation Stability of the Min-Sum Objective Function1101.3620v2 · Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin et al.2011 · 0 citationsarXiv
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs1010.2921v2 · Paul Christiano, Jonathan A. Kelner, Aleksander Madry et al.2010 · 282 citationsarXiv
Efficient Clustering with Limited Distance Information1009.5168v2 · Konstantin Voevodski, Maria-Florina Balcan, Heiko Roglin et al.2010 · 16 citationsarXiv
A Complexity View of Markets with Social Influence1009.0309v1 · Xi Chen, Shang-Hua Teng2010 · 7 citationsarXiv
Metric uniformization and spectral bounds for graphs1008.3594v3 · Jonathan A. Kelner, James R. Lee, Gregory N. Price et al.2010 · 24 citationsarXiv
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers0912.1623v1 · Alexandra Kolla, Yury Makarychev, Amin Saberi et al.2009 · 53 citationsarXiv
Spectral affinity in protein networks.19943959 · Voevodski, Konstantin, Teng, Shang-Hua, Xia, Yu2010 · 44 citationsBMC systems biology. 2009;3:112
Finding local communities in protein networks.19765306 · Voevodski, Konstantin, Teng, Shang-Hua, Xia, Yu2010 · 70 citationsBMC bioinformatics. 2009;10:297
Spending is not Easier than Trading: On the Computational Equivalence of Fisher and Arrow-Debreu Equilibria0907.4130v1 · Xi Chen, Shang-Hua Teng2009 · 64 citationsarXiv
Reducibility Among Fractional Stability Problems0904.1435v1 · Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman et al.2009 · 29 citationsarXiv
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities0904.0644v1 · Xi Chen, Decheng Dai, Ye Du et al.2009 · 132 citationsarXiv
Decision trees are PAC-learnable from most product distributions: a smoothed analysis0812.0933v1 · Adam Tauman Kalai, Shang-Hua Teng2008 · 7 citationsarXiv
Preference Games and Personalized Equilibria, with Applications to Fractional BGP0812.0598v2 · Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram et al.2008 · 2 citationsarXiv
A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning0809.3232v1 · Daniel A. Spielman, Shang-Hua Teng2008 · 316 citationsarXiv
Spectral Sparsification of Graphs0808.4134v3 · Daniel A. Spielman, Shang-Hua Teng2008 · 413 citationsarXiv
Bounded Budget Connection (BBC) Games or How to make friends and influence people, on a budget0806.1727v1 · Nikolaos Laoutaris, Laura J. Poplawski, Rajmohan Rajaraman et al.2008 · 53 citationsarXiv
Optimal Cache-Oblivious Mesh Layouts0705.1033v2 · Michael A. Bender, Bradley C. Kuszmaul, Shang-Hua Teng et al.2007 · 9 citationsarXiv
Career total: 346 works. 61 are in this corpus.Showing the 50 most recent.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.