4 Search Results for "Li, Fu"


Document
Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network

Authors: Fu Li and Xiong Zheng

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
In recent work, Gourv{è}s, Lesca, and Wilczynski (IJCAI 17) propose a variant of the classic housing markets model in which the matching between agents and objects evolves through Pareto-improving swaps between pairs of agents who are adjacent in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings, and investigate the computational complexity of these questions when the graph structure of the social network is a star, path, or tree, or is unrestricted. We are interested in how to direct the agents to swap objects with each other in order to arrive at a reachable matching that is both efficient and most agreeable. In particular, we study the computational complexity of reaching a Pareto-efficient matching that maximizes the number of agents who prefer their match to their initial endowments. We consider various graph structures of the social network: path, star, tree, or being unrestricted. Additionally, we consider two assumptions regarding preference relations of agents: strict (ties among objects not allowed) or weak (ties among objects allowed). By designing two polynomial-time algorithms and two NP-hardness reductions, we resolve the complexity of all cases not yet known. Our main contributions include a polynomial-time algorithm for path networks with strict preferences and an NP-hardness result in a star network with weak preferences.

Cite as

Fu Li and Xiong Zheng. Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.MFCS.2021.71,
  author =	{Li, Fu and Zheng, Xiong},
  title =	{{Maximum Votes Pareto-Efficient Allocations via Swaps on a Social Network}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{71:1--71:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.71},
  URN =		{urn:nbn:de:0030-drops-145112},
  doi =		{10.4230/LIPIcs.MFCS.2021.71},
  annote =	{Keywords: Housing markets, Distributed process, Algorithms, Complexity}
}
Document
RANDOM
Improved Extractors for Recognizable and Algebraic Sources

Authors: Fu Li and David Zuckerman

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)


Abstract
We study the task of seedless randomness extraction from recognizable sources, which are uniform distributions over sets of the form {x : f(x) = 1} for functions f in some specified class C. We give two simple methods for constructing seedless extractors for C-recognizable sources. Our first method shows that if C admits XOR amplification, then we can construct a seedless extractor for C-recognizable sources by using a mildly hard function for C as a black box. By exploiting this reduction, we give polynomial-time, seedless randomness extractors for three natural recognizable sources: (1) constant-degree algebraic sources over any prime field, where constant-degree algebraic sources are uniform distributions over the set of zeros of a system of constant degree polynomials; (2) sources recognizable by randomized multiparty communication protocols of cn bits, where c>0 is a small enough constant; (3) halfspace sources, or sources recognizable by linear threshold functions. In particular, the new extractor for each of these three sources has linear output length and exponentially small error for min-entropy k >= (1-alpha)n, where alpha>0 is a small enough constant. Our second method shows that a seed-extending pseudorandom generator with exponentially small error for C yields an extractor with exponentially small error for C-recognizable sources, improving a reduction by Kinne, Melkebeek, and Shaltiel [Kinne et al., 2012]. Using the hardness of the parity function against AC^0 [Håstad, 1987], we significantly improve Shaltiel’s extractor [Shaltiel, 2011] for AC^0-recognizable sources. Finally, assuming sufficiently strong one-way permutations, we construct seedless extractors for sources recognizable by BPP algorithms, and these extractors run in quasi-polynomial time.

Cite as

Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 72:1-72:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.72,
  author =	{Li, Fu and Zuckerman, David},
  title =	{{Improved Extractors for Recognizable and Algebraic Sources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{72:1--72:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.72},
  URN =		{urn:nbn:de:0030-drops-112873},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.72},
  annote =	{Keywords: Extractor, Pseudorandomness}
}
Document
A PTAS for a Class of Stochastic Dynamic Programs

Authors: Hao Fu, Jian Li, and Pan Xu

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We develop a framework for obtaining polynomial time approximation schemes (PTAS) for a class of stochastic dynamic programs. Using our framework, we obtain the first PTAS for the following stochastic combinatorial optimization problems: 1) Probemax [Munagala, 2016]: We are given a set of n items, each item i in [n] has a value X_i which is an independent random variable with a known (discrete) distribution pi_i. We can probe a subset P subseteq [n] of items sequentially. Each time after {probing} an item i, we observe its value realization, which follows the distribution pi_i. We can adaptively probe at most m items and each item can be probed at most once. The reward is the maximum among the m realized values. Our goal is to design an adaptive probing policy such that the expected value of the reward is maximized. To the best of our knowledge, the best known approximation ratio is 1-1/e, due to Asadpour et al. [Asadpour and Nazerzadeh, 2015]. We also obtain PTAS for some generalizations and variants of the problem. 2) Committed Pandora's Box [Weitzman, 1979; Singla, 2018]: We are given a set of n boxes. For each box i in [n], the cost c_i is deterministic and the value X_i is an independent random variable with a known (discrete) distribution pi_i. Opening a box i incurs a cost of c_i. We can adaptively choose to open the boxes (and observe their values) or stop. We want to maximize the expectation of the realized value of the last opened box minus the total opening cost. 3) Stochastic Target [{I}lhan et al., 2011]: Given a predetermined target T and n items, we can adaptively insert the items into a knapsack and insert at most m items. Each item i has a value X_i which is an independent random variable with a known (discrete) distribution. Our goal is to design an adaptive policy such that the probability of the total values of all items inserted being larger than or equal to T is maximized. We provide the first bi-criteria PTAS for the problem. 4) Stochastic Blackjack Knapsack [Levin and Vainer, 2014]: We are given a knapsack of capacity C and probability distributions of n independent random variables X_i. Each item i in [n] has a size X_i and a profit p_i. We can adaptively insert the items into a knapsack, as long as the capacity constraint is not violated. We want to maximize the expected total profit of all inserted items. If the capacity constraint is violated, we lose all the profit. We provide the first bi-criteria PTAS for the problem.

Cite as

Hao Fu, Jian Li, and Pan Xu. A PTAS for a Class of Stochastic Dynamic Programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2018.56,
  author =	{Fu, Hao and Li, Jian and Xu, Pan},
  title =	{{A PTAS for a Class of Stochastic Dynamic Programs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.56},
  URN =		{urn:nbn:de:0030-drops-90609},
  doi =		{10.4230/LIPIcs.ICALP.2018.56},
  annote =	{Keywords: stochastic optimization, dynamic program, markov decision process, block policy, approximation algorithm}
}
Document
Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs

Authors: Fu Li, Iddo Tzameret, and Zhengyu Wang

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)


Abstract
Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e. Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the size of the formula proved) is a major open problem in proof complexity, and among a handful of fundamental hardness questions in complexity theory by and large. Non-commutative arithmetic formulas, on the other hand, constitute a quite weak computational model, for which exponential-size lower bounds were shown already back in 1991 by Nisan [STOC 1991], using a particularly transparent argument. In this work we show that Frege lower bounds in fact follow from corresponding size lower bounds on non-commutative formulas computing certain polynomials (and that such lower bounds on non-commutative formulas must exist, unless NP=coNP). More precisely, we demonstrate a natural association between tautologies T to non-commutative polynomials p, such that: (*) if T has a polynomial-size Frege proof then p has a polynomial-size non-commutative arithmetic formula; and conversely, when T is a DNF, if p has a polynomial-size non-commutative arithmetic formula over GF(2) then T has a Frege proof of quasi-polynomial size. The argument is a characterization of Frege proofs as non-commutative formulas: we show that the Frege system is (quasi-)polynomially equivalent to a non-commutative Ideal Proof System (IPS), following the recent work of Grochow and Pitassi [FOCS 2014] that introduced a propositional proof system in which proofs are arithmetic circuits, and the work in [Tzameret 2011] that considered adding the commutator as an axiom in algebraic propositional proof systems. This gives a characterization of propositional Frege proofs in terms of (non-commutative) arithmetic formulas that is tighter than (the formula version of IPS) in Grochow and Pitassi [FOCS 2014], in the following sense: (i) The non-commutative IPS is polynomial-time checkable - whereas the original IPS was checkable in probabilistic polynomial-time; and (ii) Frege proofs unconditionally quasi-polynomially simulate the non-commutative IPS - whereas Frege was shown to efficiently simulate IPS only assuming that the decidability of PIT for (commutative) arithmetic formulas by polynomial-size circuits is efficiently provable in Frege.

Cite as

Fu Li, Iddo Tzameret, and Zhengyu Wang. Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 412-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.CCC.2015.412,
  author =	{Li, Fu and Tzameret, Iddo and Wang, Zhengyu},
  title =	{{Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{412--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.412},
  URN =		{urn:nbn:de:0030-drops-50585},
  doi =		{10.4230/LIPIcs.CCC.2015.412},
  annote =	{Keywords: Proof complexity, algebraic complexity, arithmetic circuits, Frege, non-commutative formulas}
}
  • Refine by Author
  • 3 Li, Fu
  • 1 Fu, Hao
  • 1 Li, Jian
  • 1 Tzameret, Iddo
  • 1 Wang, Zhengyu
  • Show More...

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Pseudorandomness and derandomization
  • 1 Theory of computation → Stochastic approximation

  • Refine by Keyword
  • 1 Algorithms
  • 1 Complexity
  • 1 Distributed process
  • 1 Extractor
  • 1 Frege
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2015
  • 1 2018
  • 1 2019
  • 1 2021

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