7 Search Results for "Liu, Lin"

Document
Extended Abstract
DOI: 10.4230/OASIcs.Tokenomics.2021.10
Detecting and Quantifying Crypto Wash Trading (Extended Abstract)

Authors: Lin William Cong, Xi Li, Ke Tang, and Yang Yang

Published in: OASIcs, Volume 97, 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)

Abstract
We introduce systematic tests exploiting robust statistical and behavioral patterns in trading to detect fake transactions on 29 cryptocurrency exchanges. Regulated exchanges feature patterns consistently observed in financial markets and nature; abnormal first-significant-digit distributions, size rounding, and transaction tail distributions on unregulated exchanges reveal rampant manipulations unlikely driven by strategy or exchange heterogeneity. We quantify the wash trading on each unregulated exchange, which averaged over 70% of the reported volume. We further document how these fabricated volumes (trillions of dollars annually) improve exchange ranking, temporarily distort prices, and relate to exchange characteristics (e.g., age and userbase), market conditions, and regulation.
Cite as

Lin William Cong, Xi Li, Ke Tang, and Yang Yang. Detecting and Quantifying Crypto Wash Trading (Extended Abstract). In 3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021). Open Access Series in Informatics (OASIcs), Volume 97, pp. 10:1-10:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cong_et_al:OASIcs.Tokenomics.2021.10,
  author =	{Cong, Lin William and Li, Xi and Tang, Ke and Yang, Yang},
  title =	{{Detecting and Quantifying Crypto Wash Trading}},
  booktitle =	{3rd International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2021)},
  pages =	{10:1--10:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-220-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{97},
  editor =	{Gramoli, Vincent and Halaburda, Hanna and Pass, Rafael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.Tokenomics.2021.10},
  URN =		{urn:nbn:de:0030-drops-159072},
  doi =		{10.4230/OASIcs.Tokenomics.2021.10},
  annote =	{Keywords: Bitcoin, Cryptocurrency, FinTech, Forensic Finance, Fraud Detection, Regulation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.54
The Importance of the Spectral Gap in Estimating Ground-State Energies

Authors: Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the Local Hamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the Local Hamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the Local Hamiltonian problem is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision (promise gap), there is a surprising result that the complexity of Local Hamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space (but possibly exponential time). We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.
Cite as

Abhinav Deshpande, Alexey V. Gorshkov, and Bill Fefferman. The Importance of the Spectral Gap in Estimating Ground-State Energies. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 54:1-54:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{deshpande_et_al:LIPIcs.ITCS.2022.54,
  author =	{Deshpande, Abhinav and Gorshkov, Alexey V. and Fefferman, Bill},
  title =	{{The Importance of the Spectral Gap in Estimating Ground-State Energies}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{54:1--54:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.54},
  URN =		{urn:nbn:de:0030-drops-156501},
  doi =		{10.4230/LIPIcs.ITCS.2022.54},
  annote =	{Keywords: Local Hamiltonian problem, PSPACE, PP, QMA}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.66
A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Authors: Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The maximum duo-preservation string mapping (Max-Duo) problem is the complement of the well studied minimum common string partition (MCSP) problem, both of which have applications in many fields including text compression and bioinformatics. k-Max-Duo is the restricted version of Max-Duo, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree \Delta \le 6(k-1). In particular, 2-Max-Duo can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem. 2-Max-Duo was proved APX-hard and very recently a (1.6 + \epsilon)-approximation was claimed, for any \epsilon > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-Max-Duo can be approximated arbitrarily close to 1.4.
Cite as

Yao Xu, Yong Chen, Guohui Lin, Tian Liu, Taibo Luo, and Peng Zhang. A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 66:1-66:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.ISAAC.2017.66,
  author =	{Xu, Yao and Chen, Yong and Lin, Guohui and Liu, Tian and Luo, Taibo and Zhang, Peng},
  title =	{{A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{66:1--66:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.66},
  URN =		{urn:nbn:de:0030-drops-82120},
  doi =		{10.4230/LIPIcs.ISAAC.2017.66},
  annote =	{Keywords: Approximation algorithm, duo-preservation string mapping, string partition, independent set}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.45
Approximation via Correlation Decay When Strong Spatial Mixing Fails

Authors: Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of anti-ferromagnetic two-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortise against certain "bad" instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails. We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper-bound Delta and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k >= 2 and Delta <= 5 (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to Delta = 6). Our technique gives a tight result for Delta = 6, showing that there is an FPTAS for k >= 3 and Delta <= 6. The best previously-known approximation scheme for Delta = 6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k >= 8. Our technique also applies for larger values of k, giving an FPTAS for k >= 1.66 Delta. This bound is not as strong as existing randomised results, for technical reasons that are discussed in the paper. Nevertheless, it gives the first deterministic approximation schemes in this regime. We further demonstrate that in the hypergraph independent set model, approximating the partition function is NP-hard even within the uniqueness regime.
Cite as

Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic. Approximation via Correlation Decay When Strong Spatial Mixing Fails. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bezakova_et_al:LIPIcs.ICALP.2016.45,
  author =	{Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Stefankovic, Daniel},
  title =	{{Approximation via Correlation Decay When Strong Spatial Mixing Fails}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.45},
  URN =		{urn:nbn:de:0030-drops-63257},
  doi =		{10.4230/LIPIcs.ICALP.2016.45},
  annote =	{Keywords: approximate counting, independent sets in hypergraphs, correlation decay}
}
Document
DOI: 10.4230/DagRep.2.10.117
Requirements Management – Novel Perspectives and Challenges (Dagstuhl Seminar 12442)

Authors: Jane Cleland-Huang, Matthias Jarke, Lin Liu, and Kalle Lyytinen

Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 12442 "Requirements Management -- Novel Perspectives and Challenges". Changes in computational paradigms and capabilities that draw upon platform strategies, web services, and virtualization of both application services and development platforms have significant implications for views of modularity and requirements evolution, complexity of RE tasks, and the economics of system development and operations. The aim of the seminar was to bring together experts from multiple fields to discuss models and theories around these changes. Three key challenges and associated solution ideas were addressed, namely (1) to better deal with context changes and business goal management to reduce the "black swan" rate of badly failed large projects, (2) to exploit recent theories of technological and institutional evolution to understand better how to control complexity and leverage it for innovation at the same time, and (3) the demand for runtime re-organization of existing large-scale systems with respect to new operational goals such as energy efficiency. Future RE must see itself as the marketplace where responsibility for all these complexities and evolutionary steps is traded.
Cite as

Jane Cleland-Huang, Matthias Jarke, Lin Liu, and Kalle Lyytinen. Requirements Management – Novel Perspectives and Challenges (Dagstuhl Seminar 12442). In Dagstuhl Reports, Volume 2, Issue 10, pp. 117-152, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{clelandhuang_et_al:DagRep.2.10.117,
  author =	{Cleland-Huang, Jane and Jarke, Matthias and Liu, Lin and Lyytinen, Kalle},
  title =	{{Requirements Management – Novel Perspectives and Challenges (Dagstuhl Seminar 12442)}},
  pages =	{117--152},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{10},
  editor =	{Cleland-Huang, Jane and Jarke, Matthias and Liu, Lin and Lyytinen, Kalle},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.10.117},
  URN =		{urn:nbn:de:0030-drops-39082},
  doi =		{10.4230/DagRep.2.10.117},
  annote =	{Keywords: requirements engineering; system complexity; software evolution; socio-technical systems}
}
Document
DOI: 10.4230/DagSemProc.10081.12
On First-Order Definability and Computability of Progression for Local-Effect Actions and Beyond

Authors: Yongmei Liu and Gerhard Lakemeyer

Published in: Dagstuhl Seminar Proceedings, Volume 10081, Cognitive Robotics (2010)

Abstract
In a seminal paper, Lin and Reiter introduced the notion of progression for basic action theories in the situation calculus. Unfortunately, progression is not first-order definable in general. Recently, Vassos, Lakemeyer, and Levesque showed that in case actions have only local effects, progression is firstorder representable. However, they could show computability of the first-order representation only for a restricted class. Also, their proofs were quite involved. In this paper, we present a result stronger than theirs that for local-effect actions, progression is always first-order definable and computable. We give a very simple proof for this via the concept of forgetting. We also show first-order definability and computability results for a class of knowledge bases and actions with non-local effects. Moreover, for a certain class of local-effect actions and knowledge bases for representing disjunctive information, we show that progression is not only firstorder definable but also efficiently computable.
Cite as

Yongmei Liu and Gerhard Lakemeyer. On First-Order Definability and Computability of Progression for Local-Effect Actions and Beyond. In Cognitive Robotics. Dagstuhl Seminar Proceedings, Volume 10081, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:DagSemProc.10081.12,
  author =	{Liu, Yongmei and Lakemeyer, Gerhard},
  title =	{{On First-Order Definability and Computability of Progression for Local-Effect Actions and Beyond}},
  booktitle =	{Cognitive Robotics},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10081},
  editor =	{Gerhard Lakemeyer and Hector J. Levesque and Fiora Pirri},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10081.12},
  URN =		{urn:nbn:de:0030-drops-26380},
  doi =		{10.4230/DagSemProc.10081.12},
  annote =	{Keywords: Action and change, knowledge representation}
}
Document
DOI: 10.4230/DagSemProc.08412.19
Understanding Social and Environmental Requirements in China

Authors: Lin Liu

Published in: Dagstuhl Seminar Proceedings, Volume 8412, Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems (2009)

Abstract
Rapid changes in the social and technical environment bring about many new challenges to system requirements engineering, amongst which out-sourcing or off-shoring of certain design tasks to countries with more human resources and broader markets becomes promising business leverage. Here we report some of the result from an ongoing research project on the survey of requirements practices in China. It is interesting to understand the current status of industrial practices after years' research efforts, especially in a rapidly developing country such as the China. We perform a web-based survey of requirements engineering practices in China, focusing on the requirement elicitation techniques and requirement presentation techniques. Our study has collected data from 150+ participants from 50+ Chinese companies and education institutes. We also analyze the impact of Chinese culture on requirement engineering practices. In this report, we present the main survey results and point out their implications. We hope our results are useful for industrial practitioners and academic researchers wishing to improve current practices, and for foreign software companies wishing to better understand their Chinese customers.
Cite as

Lin Liu. Understanding Social and Environmental Requirements in China. In Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems. Dagstuhl Seminar Proceedings, Volume 8412, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{liu:DagSemProc.08412.19,
  author =	{Liu, Lin},
  title =	{{Understanding Social and Environmental Requirements in China}},
  booktitle =	{Perspectives Workshop: Science of Design: High-Impact Requirements for Software-Intensive Systems},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{8412},
  editor =	{Matthias Jarke and Kalle Lyytinen and John Mylopoulos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08412.19},
  URN =		{urn:nbn:de:0030-drops-19787},
  doi =		{10.4230/DagSemProc.08412.19},
  annote =	{Keywords: Requirements engineering, culture, environment, China}
}
  • Refine by Author
  • 2 Liu, Lin
  • 1 Bezáková, Ivona
  • 1 Chen, Yong
  • 1 Cleland-Huang, Jane
  • 1 Cong, Lin William
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Action and change
  • 1 Approximation algorithm
  • 1 Bitcoin
  • 1 China
  • 1 Cryptocurrency
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2022
  • 1 2009
  • 1 2010
  • 1 2013
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact