Found 3 Possible Name Variants:

Document

RANDOM

**Published in:** LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Structural balance theory studies stability in networks. Given a n-vertex complete graph G = (V,E) whose edges are labeled positive or negative, the graph is considered balanced if every triangle either consists of three positive edges (three mutual "friends"), or one positive edge and two negative edges (two "friends" with a common "enemy"). From a computational perspective, structural balance turns out to be a special case of correlation clustering with the number of clusters at most two. The two main algorithmic problems of interest are: (i) detecting whether a given graph is balanced, or (ii) finding a partition that approximates the frustration index, i.e., the minimum number of edge flips that turn the graph balanced.
We study these problems in the streaming model where edges are given one by one and focus on memory efficiency. We provide randomized single-pass algorithms for: (i) determining whether an input graph is balanced with O(log n) memory, and (ii) finding a partition that induces a (1 + ε)-approximation to the frustration index with O(n ⋅ polylog(n)) memory. We further provide several new lower bounds, complementing different aspects of our algorithms such as the need for randomization or approximation.
To obtain our main results, we develop a method using pseudorandom generators (PRGs) to sample edges between independently-chosen vertices in graph streaming. Furthermore, our algorithm that approximates the frustration index improves the running time of the state-of-the-art correlation clustering with two clusters (Giotis-Guruswami algorithm [SODA 2006]) from n^O(1/ε²) to O(n²log³n/ε² + n log n ⋅ (1/ε)^O(1/ε⁴)) time for (1+ε)-approximation. These results may be of independent interest.

Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng, Jie Gao, and Chen Wang. Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.APPROX/RANDOM.2023.58, author = {Ashvinkumar, Vikrant and Assadi, Sepehr and Deng, Chengyuan and Gao, Jie and Wang, Chen}, title = {{Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {58:1--58:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.58}, URN = {urn:nbn:de:0030-drops-188830}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.58}, annote = {Keywords: Streaming algorithms, structural balance, pseudo-randomness generator} }

Document

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

We present a new approach for solving (minimum disagreement) correlation clustering that results in sublinear algorithms with highly efficient time and space complexity for this problem. In particular, we obtain the following algorithms for n-vertex (+/-)-labeled graphs G:
- A sublinear-time algorithm that with high probability returns a constant approximation clustering of G in O(nlog²n) time assuming access to the adjacency list of the (+)-labeled edges of G (this is almost quadratically faster than even reading the input once). Previously, no sublinear-time algorithm was known for this problem with any multiplicative approximation guarantee.
- A semi-streaming algorithm that with high probability returns a constant approximation clustering of G in O(n log n) space and a single pass over the edges of the graph G (this memory is almost quadratically smaller than input size). Previously, no single-pass algorithm with o(n²) space was known for this problem with any approximation guarantee. The main ingredient of our approach is a novel connection to sparse-dense graph decompositions that are used extensively in the graph coloring literature. To our knowledge, this connection is the first application of these decompositions beyond graph coloring, and in particular for the correlation clustering problem, and can be of independent interest.

Sepehr Assadi and Chen Wang. Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ITCS.2022.10, author = {Assadi, Sepehr and Wang, Chen}, title = {{Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {10:1--10:20}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.10}, URN = {urn:nbn:de:0030-drops-156067}, doi = {10.4230/LIPIcs.ITCS.2022.10}, annote = {Keywords: Correlation Clustering, Sublinear Algorithms, Semi-streaming Algorithms, Sublinear time Algorithms} }

Document

**Published in:** LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over the finite field F_p. Then, Clarkson and Woodruff [CW09] introduced the singularity problem to the streaming model. They proposed a randomized one pass streaming algorithm that uses O(k^2 log n) space to decide if the rank of a matrix is k, and proved an Omega(k^2) lower bound for randomized one-way protocols in the communication complexity model.
We prove that the randomized/quantum communication complexity of the singularity problem over F_p is Omega(n^2 log p), which implies the same space lower bound for randomized streaming algorithms, even for a constant number of passes. The proof uses the framework by Lee and Shraibman [LS09], but we choose Fourier coefficients as the witness for the dual approximate norm of the communication matrix. Moreover, we use Fourier analysis to show the same randomized/quantum lower bound when deciding if the determinant of a non-singular matrix is a or b for non-zero a and b.

Xiaoming Sun and Chengu Wang. Randomized Communication Complexity for Linear Algebra Problems over Finite Fields. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{sun_et_al:LIPIcs.STACS.2012.477, author = {Sun, Xiaoming and Wang, Chengu}, title = {{Randomized Communication Complexity for Linear Algebra Problems over Finite Fields}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {477--488}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.477}, URN = {urn:nbn:de:0030-drops-34385}, doi = {10.4230/LIPIcs.STACS.2012.477}, annote = {Keywords: communication complexity, streaming, matrix, singularity, determinant} }

Document

**Published in:** LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Transforming programs between two APIs or different versions of
the same API is a common software engineering task. However,
existing languages supporting for such transformation cannot
satisfactorily handle the cases when the relations between
elements in the old API and the new API are many-to-many
mappings: multiple invocations to the old API are supposed to be
replaced by multiple invocations to the new API. Since the
multiple invocations of the original APIs may not appear
consecutively and the variables in these calls may have different
names, writing a tool correctly to cover all such invocation
cases is not an easy task. In this paper we propose a novel
guided-normalization approach to address this problem. Our core
insight is that programs in different forms can be
semantics-equivalently normalized into a basic form guided by
transformation goals, and developers only need to write rules for
the basic form to address the transformation. Based on this
approach, we design a declarative program transformation
language, PATL, for adapting Java programs between different
APIs. PATL has simple syntax and basic semantics to handle
transformations only considering consecutive statements inside
basic blocks, while with guided-normalization, it can be extended
to handle complex forms of invocations. Furthermore, PATL ensures
that the user-written rules would not accidentally break def-use
relations in the program. We formalize the semantics of PATL on
Middleweight Java and prove the semantics-preserving property of
guided-normalization. We also evaluated our language with three
non-trivial case studies: i.e. updating Google Calendar API,
switching from JDom to Dom4j, and switching from Swing to
SWT. The result is encouraging; it shows that our language allows
successful transformations of real world programs with a small
number of rules and little manual resolution.

Chenglong Wang, Jiajun Jiang, Jun Li, Yingfei Xiong, Xiangyu Luo, Lu Zhang, and Zhenjiang Hu. Transforming Programs between APIs with Many-to-Many Mappings. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 25:1-25:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ECOOP.2016.25, author = {Wang, Chenglong and Jiang, Jiajun and Li, Jun and Xiong, Yingfei and Luo, Xiangyu and Zhang, Lu and Hu, Zhenjiang}, title = {{Transforming Programs between APIs with Many-to-Many Mappings}}, booktitle = {30th European Conference on Object-Oriented Programming (ECOOP 2016)}, pages = {25:1--25:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-014-9}, ISSN = {1868-8969}, year = {2016}, volume = {56}, editor = {Krishnamurthi, Shriram and Lerner, Benjamin S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.25}, URN = {urn:nbn:de:0030-drops-61195}, doi = {10.4230/LIPIcs.ECOOP.2016.25}, annote = {Keywords: Program transformation, API migration} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail