Xiaoming Sun

Shuo Zhang

CoRR, 2023

Moser-Tardos Algorithm: Beyond Shearer's Bound.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Bandit Multi-linear DR-Submodular Maximization and Its Applications on Adversarial Submodular Bandits.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Simple Deterministic Approximation for Submodular Multiple Knapsack Problem.

[BibT_eX]

[DOI]

Zhijie Zhang

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Optimal Synthesis of Multi-Controlled Qudit Gates.

[BibT_eX]

[DOI]

Wei Zi

Proceedings of the 60th ACM/IEEE Design Automation Conference, 2023

Quantum Multi-Armed Bandits and Stochastic Linear Bandits Enjoy Logarithmic Regrets.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

On the relationship between energy complexity and other boolean function measures.

[BibT_eX]

[DOI]

J. Comb. Optim., 2022

Discouraging pool block withholding attacks in Bitcoin.

[BibT_eX]

[DOI]

J. Comb. Optim., 2022

Higher order monotonicity and submodularity of influence in social networks: From local to global.

[BibT_eX]

[DOI]

Inf. Comput., 2022

Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation.

[BibT_eX]

[DOI]

CoRR, 2022

New Distinguishers for Negation-Limited Weak Pseudorandom Functions.

[BibT_eX]

[DOI]

CoRR, 2022

Bounded Memory Adversarial Bandits with Composite Anonymous Delayed Feedback.

[BibT_eX]

[DOI]

Zongqi Wan

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, 2022

Improved Deterministic Algorithms for Non-monotone Submodular Maximization.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 28th International Conference, 2022

Online Influence Maximization with Node-Level Feedback Using Standard Offline Oracles.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

On the Sensitivity Complexity of k-Uniform Hypergraph Properties.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Special Issue on the International Conference on Algorithmic Aspects in Information and Management 2019 (AAIM'19).

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Querying a Matrix through Matrix-Vector Products.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

Follow the perturbed approximate leader for solving semi-bandit combinatorial optimization.

[BibT_eX]

[DOI]

Frontiers Comput. Sci., 2021

Perfect Sampling for (Atomic) Lovász Local Lemma.

[BibT_eX]

[DOI]

Kewen Wu

CoRR, 2021

Dynamic Inference in Probabilistic Graphical Models.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Network Inference and Influence Maximization from Samples.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

Quantum Supremacy Circuit Simulation on Sunway TaihuLight.

[BibT_eX]

[DOI]

IEEE Trans. Parallel Distributed Syst., 2020

The one-round multi-player discrete Voronoi game on grids and trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

On the modulo degree complexity of Boolean functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Coreness of cooperative games with truncated submodular profit functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2020

Structured Decomposition for Reversible Boolean Functions.

[BibT_eX]

[DOI]

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2020

Local Equivalence of Multipartite Entanglement.

[BibT_eX]

[DOI]

Nengkun Yu

IEEE J. Sel. Areas Commun., 2020

Quantum Search with Prior Knowledge.

[BibT_eX]

[DOI]

Xiaoyu He

CoRR, 2020

Discouraging Pool Block Withholding Attacks in Bitcoins.

[BibT_eX]

[DOI]

CoRR, 2020

Tight Algorithms for the Submodular Multiple Knapsack Problem.

[BibT_eX]

[DOI]

Zhijie Zhang

CoRR, 2020

On the Optimality of Tape Merge of Two Lists with Similar Size.

[BibT_eX]

[DOI]

Algorithmica, 2020

Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Optimization from Structured Samples for Coverage Functions.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Decentralized Mining Pool Games in Blockchain.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Conference on Knowledge Graph, 2020

Approximate Single-Peakedness in Large Elections.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Conference on Knowledge Graph, 2020

On the Degree of Boolean Functions as Polynomials over ℤm.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Better Upper Bounds for Searching on a Line with Byzantine Robots.

[BibT_eX]

[DOI]

Yuan Sun

Proceedings of the Complexity and Approximation - In Memory of Ker-I Ko, 2020

Revisiting Online Quantum State Learning.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

A tighter relation between sensitivity complexity and certificate complexity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2019

Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful.

[BibT_eX]

[DOI]

Yufan Zheng

CoRR, 2019

Dynamic MCMC Sampling.

[BibT_eX]

[DOI]

CoRR, 2019

From independent sets and vertex colorings to isotropic spaces and isotropic decompositions.

[BibT_eX]

[DOI]

CoRR, 2019

Cumulative activation in social networks.

[BibT_eX]

[DOI]

Sci. China Inf. Sci., 2019

The Complexity of Optimization on Grids.

[BibT_eX]

[DOI]

Algorithmica, 2019

A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix Factorization.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019

2018

Path cooperative games.

[BibT_eX]

[DOI]

J. Comb. Optim., 2018

Quantum Lovász Local Lemma: Shearer's Bound is Tight.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Exact quantum query complexity of weight decision problems.

[BibT_eX]

[DOI]

CoRR, 2018

On the Decision Tree Complexity of String Matching.

[BibT_eX]

[DOI]

Xiaoyu He

Neng Huang

Proceedings of the 26th Annual European Symposium on Algorithms, 2018

Boosting Dynamic Programming with Neural Networks for Solving NP-hard Problems.

[BibT_eX]

[DOI]

Proceedings of The 10th Asian Conference on Machine Learning, 2018

2017

Near optimal algorithms for online weighted bipartite matching in adversary model.

[BibT_eX]

[DOI]

Jia Zhang

J. Comb. Optim., 2017

A Linear Algorithm for Finding the Sink of Unique Sink Orientations on Grids.

[BibT_eX]

[DOI]

Zhijie Zhang

CoRR, 2017

Partial Sorting Problem on Evolving Data.

[BibT_eX]

[DOI]

Algorithmica, 2017

On the Sensitivity Complexity of k-Uniform Hypergraph Properties.

[BibT_eX]

[DOI]

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Influence Maximization with ε-Almost Submodular Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Efficient Delivery Policy to Minimize User Traffic Consumption in Guaranteed Advertising.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

Randomized Mechanisms for Selling Reserved Instances in Cloud Computing.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

Computing the least-core and nucleolus for threshold cardinality matching games.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Randomized Mechanisms for Selling Reserved Instances in Cloud.

[BibT_eX]

[DOI]

CoRR, 2016

Community Detection: a Refined Axiomization and Beyond.

[BibT_eX]

[DOI]

CoRR, 2016

A Tighter Relation between Sensitivity and Certificate Complexity.

[BibT_eX]

[DOI]

CoRR, 2016

Communities in Preference Networks: Refined Axioms and Beyond.

[BibT_eX]

[DOI]

Proceedings of the IEEE 16th International Conference on Data Mining, 2016

Shortest Paths on Evolving Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computational Social Networks - 5th International Conference, 2016

The Routing of Complex Contagion in Kleinberg's Small-World Networks.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

Learning Market Parameters Using Aggregate Demand Queries.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016

2015

Any monotone property of 3-uniform hypergraphs is weakly evasive.

[BibT_eX]

[DOI]

Raghav Kulkarni

Theor. Comput. Sci., 2015

On the Power of Parity Queries in Boolean Decision Trees.

[BibT_eX]

[DOI]

Raghav Kulkarni

Proceedings of the Theory and Applications of Models of Computation, 2015

How to Select the Top k Elements from Evolving Data?

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

Multi-Classes Feature Engineering with Sliding Window for Purchase Prediction in Mobile Commerce.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Conference on Data Mining Workshop, 2015

The Least-Core and Nucleolus of Path Cooperative Games.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 21st International Conference, 2015

Tight Bounds for Graph Problems in Insertion Streams.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Approximation, 2015

2014

Tighter Relations Between Sensitivity and Other Complexity Measures.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Deterministic Protocol for Shared $Q$-queue $J$-choice $K$-best Secretary Problem.

[BibT_eX]

[DOI]

Jia Zhang

CoRR, 2014

How to select the largest k elements from evolving data?

[BibT_eX]

[DOI]

CoRR, 2014

On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Minimizing seed set selection with probabilistic coverage guarantee in a social network.

[BibT_eX]

[DOI]

Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014

Solving Multi-choice Secretary Problem in Parallel: An Optimal Observation-Selection Protocol.

[BibT_eX]

[DOI]

Jia Zhang

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

On the sensitivity complexity of bipartite graph properties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity.

[BibT_eX]

[DOI]

Marcos Villagra

Electron. Colloquium Comput. Complex., 2013

On a conjecture of Butler and Graham.

[BibT_eX]

[DOI]

Tengyu Ma

Huacheng Yu

Des. Codes Cryptogr., 2013

New upper bound on block sensitivity and certificate complexity in terms of sensitivity.

[BibT_eX]

[DOI]

CoRR, 2013

Determinantal Complexities and Field Extensions.

[BibT_eX]

[DOI]

Periklis A. Papakonstantinou

Nengkun Yu

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Space-bounded communication complexity.

[BibT_eX]

[DOI]

Joshua Brody

Shiteng Chen

Hao Song

Proceedings of the Innovations in Theoretical Computer Science, 2013

Influence Maximization in Dynamic Social Networks.

[BibT_eX]

[DOI]

Proceedings of the 2013 IEEE 13th International Conference on Data Mining, 2013

2012

Graph Coloring Applied to Secure Computation in Non-Abelian Groups.

[BibT_eX]

[DOI]

J. Cryptol., 2012

Preface.

[BibT_eX]

[DOI]

Xiao-Ming Sun

J. Comput. Sci. Technol., 2012

Stam's Conjecture and Threshold Phenomena in Collision Resistance.

[BibT_eX]

[DOI]

John P. Steinberger

Zhe Yang

IACR Cryptol. ePrint Arch., 2012

Conquering the rating bound problem in neighborhood-based collaborative filtering: a function recovery approach

[BibT_eX]

[DOI]

CoRR, 2012

Randomized Communication Complexity for Linear Algebra Problems over Finite Fields.

[BibT_eX]

[DOI]

Chengu Wang

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

The Relationship between Inner Product and Counting Cycles.

[BibT_eX]

[DOI]

Chengu Wang

Wei Yu

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Space-Efficient Approximation Scheme for Circular Earth Mover Distance.

[BibT_eX]

[DOI]

Joshua Brody

Hongyu Liang

Proceedings of the LATIN 2012: Theoretical Informatics, 2012

Streaming and Communication Complexity of Clique Approximation.

[BibT_eX]

[DOI]

Magnús M. Halldórsson

Mario Szegedy

Chengu Wang

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

An improved lower bound on the sensitivity complexity of graph properties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Bounds and trade-offs for Double-Base Number Systems.

[BibT_eX]

[DOI]

Tiancheng Lou

Christophe Tartary

Inf. Process. Lett., 2011

New separation between s(f) and bs(f).

[BibT_eX]

[DOI]

Andris Ambainis

Electron. Colloquium Comput. Complex., 2011

New separation between $s(f)$ and $bs(f)$

[BibT_eX]

[DOI]

Andris Ambainis

CoRR, 2011

A Better Upper Bound on Weights of Exact Threshold Functions.

[BibT_eX]

[DOI]

Xue Chen

Guangda Hu

Proceedings of the Theory and Applications of Models of Computation, 2011

A New Variation of Hat Guessing Games.

[BibT_eX]

[DOI]

Tengyu Ma

Huacheng Yu

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

2010

The Complexity of Word Circuits.

[BibT_eX]

[DOI]

Xue Chen

Guangda Hu

Discret. Math. Algorithms Appl., 2010

Quantum Separation of Local Search and Fixed Point Computation.

[BibT_eX]

[DOI]

Xi Chen

Kristoffer Arnsfelt Hansen

Shang-Hua Teng

Algorithmica, 2010

Weights of Exact Threshold Functions.

[BibT_eX]

[DOI]

László Babai

Vladimir V. Podolskii

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

The antimagicness of the Cartesian product of graphs.

[BibT_eX]

[DOI]

Yuchen Zhang

Theor. Comput. Sci., 2009

More Efficient Algorithms for Closest String and Substring Problems.

[BibT_eX]

[DOI]

Bin Ma

SIAM J. Comput., 2009

On the Quantum Query Complexity of Local Search in Two and Three Dimensions.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Algorithmica, 2009

2008

Searching monotone multi-dimensional arrays.

[BibT_eX]

[DOI]

Yongxi Cheng

Yiqun Lisa Yin

Discret. Math., 2008

Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

Graph Design for Secure Multiparty Computation over Non-Abelian Groups.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Christophe Tartary

Proceedings of the Advances in Cryptology, 2008

2007

Block sensitivity of weakly symmetric functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

The communication and streaming complexity of computing the longest common and increasing subsequences.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

2005

The existence of quantum entanglement catalysts.

[BibT_eX]

[DOI]

Runyao Duan

Mingsheng Ying

IEEE Trans. Inf. Theory, 2005

Rapid Algorithms for MPEG-2 to H.264 Transcoding.

[BibT_eX]

[DOI]

Pin Tao

Proceedings of the Advances in Multimedia Information Processing, 2005

2004

Performance evaluation for energy efficient topologic control in ad hoc wireless networks.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

On complexity of single-minded auction.

[BibT_eX]

[DOI]

Ning Chen

Xiaotie Deng

J. Comput. Syst. Sci., 2004

Dynamic Price Sequence and Incentive Compatibility (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Fisher Equilibrium Price with a Class of Concave Utility Functions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go?

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Shengyu Zhang

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

A 3-Party Simultaneous Protocol for SUM-INDEX.

[BibT_eX]

[DOI]