-
Flip Dynamics for Sampling Colorings: Improving $(11/6-ε)$ Using a Simple Metric
Authors:
Charlie Carlson,
Eric Vigoda
Abstract:
We present improved bounds for randomly sampling $k$-colorings of graphs with maximum degree $Δ$; our results hold without any further assumptions on the graph. The Glauber dynamics is a simple single-site update Markov chain. Jerrum (1995) proved an optimal $O(n\log{n})$ mixing time bound for Glauber dynamics whenever $k>2Δ$ where $Δ$ is the maximum degree of the input graph. This bound was impro…
▽ More
We present improved bounds for randomly sampling $k$-colorings of graphs with maximum degree $Δ$; our results hold without any further assumptions on the graph. The Glauber dynamics is a simple single-site update Markov chain. Jerrum (1995) proved an optimal $O(n\log{n})$ mixing time bound for Glauber dynamics whenever $k>2Δ$ where $Δ$ is the maximum degree of the input graph. This bound was improved by Vigoda (1999) to $k > (11/6)Δ$ using a "flip" dynamics which recolors (small) maximal 2-colored components in each step. Vigoda's result was the best known for general graphs for 20 years until Chen et al. (2019) established optimal mixing of the flip dynamics for $k > (11/6 - ε) Δ$ where $ε\approx 10^{-5}$. We present the first substantial improvement over these results. We prove an optimal mixing time bound of $O(n\log{n})$ for the flip dynamics when $k \geq 1.809 Δ$. This yields, through recent spectral independence results, an optimal $O(n\log{n})$ mixing time for the Glauber dynamics for the same range of $k/Δ$ when $Δ=O(1)$. Our proof utilizes path coupling with a simple weighted Hamming distance for "unblocked" neighbors.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Authors:
Charlie Carlson,
Xiaoyu Chen,
Weiming Feng,
Eric Vigoda
Abstract:
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randomly chosen edge in each step. For a tree $T$ with $n$ vertices and maximum degree $Δ$, when the number of colors $q$ satisfies $q\geqΔ+2$ then we prove that the Glauber dynamics has an optimal relaxation time of $O(n)$, wh…
▽ More
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randomly chosen edge in each step. For a tree $T$ with $n$ vertices and maximum degree $Δ$, when the number of colors $q$ satisfies $q\geqΔ+2$ then we prove that the Glauber dynamics has an optimal relaxation time of $O(n)$, where the relaxation time is the inverse of the spectral gap. This is optimal in the range of $q$ in terms of $Δ$ as Dyer, Goldberg, and Jerrum (2006) showed that the relaxation time is $Ω(n^3)$ when $q=Δ+1$. For the case $q=Δ+1$, we show that an alternative Markov chain which updates a pair of neighboring edges has relaxation time $O(n)$. Moreover, for the $Δ$-regular complete tree we prove $O(n\log^2{n})$ mixing time bounds for the respective Markov chain. Our proofs establish approximate tensorization of variance via a novel inductive approach, where the base case is a tree of height $\ell=O(Δ^2\log^2Δ)$, which we analyze using a canonical paths argument.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Examining Ownership Models in Software Teams: A Systematic Literature Review and a Replication Study
Authors:
Umme Ayman Koana,
Quang Hy Le,
Shadikur Rahman,
Chris Carlson,
Francis Chew,
Maleknaz Nayebi
Abstract:
Effective ownership of software artifacts, particularly code, is crucial for accountability, knowledge sharing, and code quality enhancement. Researchers have proposed models linking ownership of software artifacts with developer performance and code quality. Our study aims to systematically examine various ownership models and provide a structured literature overview. Conducting a systematic lite…
▽ More
Effective ownership of software artifacts, particularly code, is crucial for accountability, knowledge sharing, and code quality enhancement. Researchers have proposed models linking ownership of software artifacts with developer performance and code quality. Our study aims to systematically examine various ownership models and provide a structured literature overview. Conducting a systematic literature review, we identified 79 relevant papers published between 2005 and 2022. We developed a taxonomy of ownership artifacts based on type, owners, and degree of ownership, along with compiling modeling variables and analytics types used in each study. Additionally, we assessed the replication status of each study. As a result, we identified nine distinct software artifacts whose ownership has been discussed in the literature, with "Code" being the most frequently analyzed artifact. We found that only three papers (3.79%) provided code and data, whereas nine papers (11.4%) provided only data. Using our systematic literature review results, we replicated experiments on nine priority projects at \texttt{Brightsquid}. The company aimed to compare its code quality against ownership factors in other teams, so we conducted a replication study using their data. Unlike prior studies, we found no strong correlation between minor contributors and bug numbers. Surprisingly, we found no strong link between the total number of developers modifying a file and bug counts, contrasting previous findings. However, we observed a significant correlation between major contributors and bug counts, diverging from earlier research.
△ Less
Submitted 24 May, 2024;
originally announced May 2024.
-
Improved Distributed Algorithms for Random Colorings
Authors:
Charlie Carlson,
Daniel Frishberg,
Eric Vigoda
Abstract:
Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step.…
▽ More
Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph $G$ of maximum degree $Δ$ and an integer $k\geqΔ+1$, the goal is to generate a random proper vertex $k$-coloring of $G$.
Jerrum (1995) proved that the Glauber dynamics has $O(n\log{n})$ mixing time when $k>2Δ$. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in $O(\log{n})$ rounds for $k>(2+\varepsilon)Δ$ for any $\varepsilon>0$. We improve this result to $k>(11/6-δ)Δ$ for a fixed $δ>0$. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step.
△ Less
Submitted 12 June, 2024; v1 submitted 14 September, 2023;
originally announced September 2023.
-
Ownership in the Hands of Accountability at Brightsquid -- A Case Study and a Developer Survey
Authors:
Umme Ayman Koana,
Francis Chew,
Chris Carlson,
Maleknaz Nayebi
Abstract:
The COVID-19 pandemic has accelerated the adoption of digital health solutions. This has presented significant challenges for software development teams to swiftly adjust to the market need and demand. To address these challenges, product management teams have had to adapt their approach to software development, reshaping their processes to meet the demands of the pandemic. Brighsquid implemented…
▽ More
The COVID-19 pandemic has accelerated the adoption of digital health solutions. This has presented significant challenges for software development teams to swiftly adjust to the market need and demand. To address these challenges, product management teams have had to adapt their approach to software development, reshaping their processes to meet the demands of the pandemic. Brighsquid implemented a new task assignment process aimed at enhancing developer accountability toward the customer. To assess the impact of this change on code ownership, we conducted a code change analysis. Additionally, we surveyed 67 developers to investigate the relationship between accountability and ownership more broadly. The findings of our case study indicate that the revised assignment model not only increased the perceived sense of accountability within the production team but also improved code resilience against ownership changes. Moreover, the survey results revealed that a majority of the participating developers (67.5%) associated perceived accountability with artifact ownership.
△ Less
Submitted 23 August, 2023;
originally announced August 2023.
-
Approximation Algorithms for Norm Multiway Cut
Authors:
Charlie Carlson,
Jafar Jafarov,
Konstantin Makarychev,
Yury Makarychev,
Liren Shan
Abstract:
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph $G$ into $k$ parts so as to separate $k$ given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced $\ell_p$-norm Multiway, a generalization of the problem, in which the goal is to minimize the $\ell_p$ norm of the edge boundaries of $k$ parts. We provide an…
▽ More
We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph $G$ into $k$ parts so as to separate $k$ given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced $\ell_p$-norm Multiway, a generalization of the problem, in which the goal is to minimize the $\ell_p$ norm of the edge boundaries of $k$ parts. We provide an $O(\log^{1/2} n\log^{1/2+1/p} k)$ approximation algorithm for this problem, improving upon the approximation guarantee of $O(\log^{3/2} n \log^{1/2} k)$ due to Chandrasekaran and Wang.
We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an $O(\log^{1/2} n \log^{7/2} k)$ approximation algorithm with a weaker oracle and an $O(\log^{1/2} n \log^{5/2} k)$ approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no $n^{1/4-\varepsilon}$ approximation algorithm for every $\varepsilon > 0$ assuming the Hypergraph Dense-vs-Random Conjecture.
△ Less
Submitted 16 August, 2023;
originally announced August 2023.
-
Approximately counting independent sets in dense bipartite graphs via subspace enumeration
Authors:
Charlie Carlson,
Ewan Davies,
Alexandra Kolla,
Aditya Potukuchi
Abstract:
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to ``high-temperature'' problems on bounded-degree graphs, and our contribution is a notable exception as it applies to…
▽ More
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph -- in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to ``high-temperature'' problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. The proof exploits the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e. bounded threshold rank), which via subspace enumeration lets us enumerate small cuts efficiently.
△ Less
Submitted 18 July, 2023;
originally announced July 2023.
-
GPT-4 Technical Report
Authors:
OpenAI,
Josh Achiam,
Steven Adler,
Sandhini Agarwal,
Lama Ahmad,
Ilge Akkaya,
Florencia Leoni Aleman,
Diogo Almeida,
Janko Altenschmidt,
Sam Altman,
Shyamal Anadkat,
Red Avila,
Igor Babuschkin,
Suchir Balaji,
Valerie Balcom,
Paul Baltescu,
Haiming Bao,
Mohammad Bavarian,
Jeff Belgum,
Irwan Bello,
Jake Berdine,
Gabriel Bernadett-Shapiro,
Christopher Berner,
Lenny Bogdonoff,
Oleg Boiko
, et al. (256 additional authors not shown)
Abstract:
We report the development of GPT-4, a large-scale, multimodal model which can accept image and text inputs and produce text outputs. While less capable than humans in many real-world scenarios, GPT-4 exhibits human-level performance on various professional and academic benchmarks, including passing a simulated bar exam with a score around the top 10% of test takers. GPT-4 is a Transformer-based mo…
▽ More
We report the development of GPT-4, a large-scale, multimodal model which can accept image and text inputs and produce text outputs. While less capable than humans in many real-world scenarios, GPT-4 exhibits human-level performance on various professional and academic benchmarks, including passing a simulated bar exam with a score around the top 10% of test takers. GPT-4 is a Transformer-based model pre-trained to predict the next token in a document. The post-training alignment process results in improved performance on measures of factuality and adherence to desired behavior. A core component of this project was developing infrastructure and optimization methods that behave predictably across a wide range of scales. This allowed us to accurately predict some aspects of GPT-4's performance based on models trained with no more than 1/1,000th the compute of GPT-4.
△ Less
Submitted 4 March, 2024; v1 submitted 15 March, 2023;
originally announced March 2023.
-
Algorithms for the ferromagnetic Potts model on expanders
Authors:
Charlie Carlson,
Ewan Davies,
Nicolas Fraiman,
Alexandra Kolla,
Aditya Potukuchi,
Corrine Yap
Abstract:
We give algorithms for approximating the partition function of the ferromagnetic Potts model on $d$-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger's alg…
▽ More
We give algorithms for approximating the partition function of the ferromagnetic Potts model on $d$-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger's algorithm to counting cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.
△ Less
Submitted 17 September, 2022; v1 submitted 4 April, 2022;
originally announced April 2022.
-
Computational thresholds for the fixed-magnetization Ising model
Authors:
Charlie Carlson,
Ewan Davies,
Alexandra Kolla,
Will Perkins
Abstract:
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here w…
▽ More
The ferromagnetic Ising model is a model of a magnetic material and a central topic in statistical physics. It also plays a starring role in the algorithmic study of approximate counting: approximating the partition function of the ferromagnetic Ising model with uniform external field is tractable at all temperatures and on all graphs, due to the randomized algorithm of Jerrum and Sinclair. Here we show that hidden inside the model are hard computational problems. For the class of bounded-degree graphs we find computational thresholds for the approximate counting and sampling problems for the ferromagnetic Ising model at fixed magnetization (that is, fixing the number of $+1$ and $-1$ spins). In particular, letting $β_c(Δ)$ denote the critical inverse temperature of the zero-field Ising model on the infinite $Δ$-regular tree, and $η_{Δ,β,1}^+$ denote the mean magnetization of the zero-field $+$ measure on the infinite $Δ$-regular tree at inverse temperature $β$, we prove, for the class of graphs of maximum degree $Δ$:
1. For $β< β_c(Δ)$ there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for all magnetizations $η$.
2. For $β> β_c(Δ)$, there is an FPRAS and efficient sampling scheme for the fixed-magnetization Ising model for magnetizations $η$ such that $|η| >η_{Δ,β,1}^+ $.
3. For $β> β_c(Δ)$, there is no FPRAS for the fixed-magnetization Ising model for magnetizations $η$ such that $|η| <η_{Δ,β,1}^+ $ unless NP=RP\@.
△ Less
Submitted 4 November, 2021;
originally announced November 2021.
-
Efficient algorithms for the Potts model on small-set expanders
Authors:
Charles Carlson,
Ewan Davies,
Alexandra Kolla
Abstract:
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorithmically, and since random regular graphs are good expanders with high probability the problem is typically tractable. Inspired by approaches used in…
▽ More
An emerging trend in approximate counting is to show that certain `low-temperature' problems are easy on typical instances, despite worst-case hardness results. For the class of regular graphs one usually shows that expansion can be exploited algorithmically, and since random regular graphs are good expanders with high probability the problem is typically tractable. Inspired by approaches used in subexponential-time algorithms for Unique Games, we develop an approximation algorithm for the partition function of the ferromagnetic Potts model on graphs with a small-set expansion condition. In such graphs it may not suffice to explore the state space of the model close to ground states, and a novel feature of our method is to efficiently find a larger set of `pseudo-ground states' such that it is enough to explore the model around each pseudo-ground state.
△ Less
Submitted 5 February, 2024; v1 submitted 2 March, 2020;
originally announced March 2020.
-
A Longitudinal Study of Identifying and Paying Down Architectural Debt
Authors:
Maleknaz Nayebi,
Yuanfang Cai,
Rick Kazman,
Guenther Ruhe,
Qiong Feng,
Chris Carlson,
Francis Chew
Abstract:
Architectural debt is a form of technical debt that derives from the gap between the architectural design of the system as it "should be" compared to "as it is". We measured architecture debt in two ways: 1) in terms of system-wide coupling measures, and 2) in terms of the number and severity of architectural flaws. In recent work it was shown that the amount of architectural debt has a huge impac…
▽ More
Architectural debt is a form of technical debt that derives from the gap between the architectural design of the system as it "should be" compared to "as it is". We measured architecture debt in two ways: 1) in terms of system-wide coupling measures, and 2) in terms of the number and severity of architectural flaws. In recent work it was shown that the amount of architectural debt has a huge impact on software maintainability and evolution. Consequently, detecting and reducing the debt is expected to make software more amenable to change. This paper reports on a longitudinal study of a healthcare communications product created by Brightsquid Secure Communications Corp. This start-up company is facing the typical trade-off problem of desiring responsiveness to change requests, but wanting to avoid the ever-increasing effort that the accumulation of quick-and-dirty changes eventually incurs. In the first stage of the study, we analyzed the status of the "before" system, which indicated the impacts of change requests. This initial study motivated a more in-depth analysis of architectural debt. The results of this analysis were used to motivate a comprehensive refactoring of the software system. The third phase of the study was a follow-on architectural debt analysis which quantified the improvements made. Using this quantitative evidence, augmented by qualitative evidence gathered from in-depth interviews with Brightsquid's architects, we present lessons learned about the costs and benefits of paying down architecture debt in practice.
△ Less
Submitted 30 November, 2018;
originally announced November 2018.
-
Lower bounds for Max-Cut in $H$-free graphs via semidefinite programming
Authors:
Charles Carlson,
Alexandra Kolla,
Ray Li,
Nitya Mani,
Benny Sudakov,
Luca Trevisan
Abstract:
For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with…
▽ More
For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The problem of estimating $f(G)$ as a function of the number of vertices and edges of $G$ has a long history and was extensively studied in the last fifty years. In this paper we propose an approach, based on semidefinite programming (SDP), to prove lower bounds on $f(G)$. We use this approach to find large cuts in graphs with few triangles and in $K_r$-free graphs.
△ Less
Submitted 22 April, 2020; v1 submitted 23 October, 2018;
originally announced October 2018.
-
ESSMArT Way to Manage User Requests
Authors:
Maleknaz Nayebi,
Liam Dicke,
Ron Ittyipe,
Chris Carlson,
Guenther Ruhe
Abstract:
Quality and market acceptance of software products is strongly influenced by responsiveness to user requests. Once a request is received from a customer, decisions need to be made if the request should be escalated to the development team. Once escalated, the ticket must be formulated as a development task and be assigned to a developer. To make the process more efficient and reduce the time betwe…
▽ More
Quality and market acceptance of software products is strongly influenced by responsiveness to user requests. Once a request is received from a customer, decisions need to be made if the request should be escalated to the development team. Once escalated, the ticket must be formulated as a development task and be assigned to a developer. To make the process more efficient and reduce the time between receiving and escalating the user request, we aim to automate of the complete user request management process. We propose a holistic method called ESSMArT. The methods performs text summarization, predicts ticket escalation, creates the title and content of the ticket used by developers, and assigns the ticket to an available developer. We internally evaluated the method by 4,114 user tickets from Brightsquid and their secure health care communication plat- form Secure-Mail. We also perform an external evaluation on the usefulness of the approach. We found that supervised learning based on context specific data performs best for extractive summarization. For predicting escalation of tickets, Random Forest trained on a combination of conversation and extractive summarization is best with highest precision (of 0.9) and recall (of 0.55). From external evaluation we found that ESSMArT provides suggestions that are 71% aligned with human ones. Applying the prototype implementation to 315 user requests resulted in an average time reduction of 9.2 minutes per request. ESSMArT helps to make ticket management faster and with reduced effort for human experts. ESSMArT can help Brightsquid to (i) minimize the impact of staff turnover and (ii) shorten the cycle from an issue being reported to an assignment to a developer to fix it.
△ Less
Submitted 11 August, 2018;
originally announced August 2018.
-
Improving the smoothed complexity of FLIP for max cut problems
Authors:
Ali Bibak,
Charles Carlson,
Karthekeyan Chandrasekaran
Abstract:
Finding locally optimal solutions for max-cut and max-$k$-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexi…
▽ More
Finding locally optimal solutions for max-cut and max-$k$-cut are well-known PLS-complete problems. An instinctive approach to finding such a locally optimum solution is the FLIP method. Even though FLIP requires exponential time in worst-case instances, it tends to terminate quickly in practical instances. To explain this discrepancy, the run-time of FLIP has been studied in the smoothed complexity framework. Etscheid and Röglin showed that the smoothed complexity of FLIP for max-cut in arbitrary graphs is quasi-polynomial. Angel, Bubeck, Peres, and Wei showed that the smoothed complexity of FLIP for max-cut in complete graphs is $O(φ^5n^{15.1})$, where $φ$ is an upper bound on the random edge-weight density and $n$ is the number of vertices in the input graph.
While Angel et al.'s result showed the first polynomial smoothed complexity, they also conjectured that their run-time bound is far from optimal. In this work, we make substantial progress towards improving the run-time bound. We prove that the smoothed complexity of FLIP in complete graphs is $O(φn^{7.83})$. Our results are based on a carefully chosen matrix whose rank captures the run-time of the method along with improved rank bounds for this matrix and an improved union bound based on this matrix. In addition, our techniques provide a general framework for analyzing FLIP in the smoothed framework. We illustrate this general framework by showing that the smoothed complexity of FLIP for max-$3$-cut in complete graphs is polynomial and for max-$k$-cut in arbitrary graphs is quasi-polynomial. We believe that our techniques should also be of interest towards addressing the smoothed complexity of FLIP for max-$k$-cut in complete graphs for larger constants $k$.
△ Less
Submitted 15 July, 2018;
originally announced July 2018.
-
Optimal Lower Bounds for Sketching Graph Cuts
Authors:
Charles Carlson,
Alexandra Kolla,
Nikhil Srivastava,
Luca Trevisan
Abstract:
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on $n$ vertices up to a $1+ε$ error must use $Ω(n\log n/ε^2)$ bits of space in the worst case, improving the $Ω(n/ε^2)$ bound of Andoni et al. and matching the best known upper bound achieved by spectral spa…
▽ More
We study the space complexity of sketching cuts and Laplacian quadratic forms of graphs. We show that any data structure which approximately stores the sizes of all cuts in an undirected graph on $n$ vertices up to a $1+ε$ error must use $Ω(n\log n/ε^2)$ bits of space in the worst case, improving the $Ω(n/ε^2)$ bound of Andoni et al. and matching the best known upper bound achieved by spectral sparsifiers. Our proof is based on a rigidity phenomenon for cut (and spectral) approximation which may be of independent interest: any two $d-$regular graphs which approximate each other's cuts significantly better than a random graph approximates the complete graph must overlap in a constant fraction of their edges.
△ Less
Submitted 29 December, 2017;
originally announced December 2017.
-
Invertibility and Largest Eigenvalue of Symmetric Matrix Signings
Authors:
Charles Carlson,
Karthekeyan Chandrasekaran,
Hsien-Chih Chang,
Alexandra Kolla
Abstract:
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of identifying symmetric signings of matrices with natural spectral properties. Our results are twofold:
1. We show NP-completeness for the following three problems: verifying whether a given matrix has a symmetric signing tha…
▽ More
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of identifying symmetric signings of matrices with natural spectral properties. Our results are twofold:
1. We show NP-completeness for the following three problems: verifying whether a given matrix has a symmetric signing that is positive semi-definite/singular/has bounded eigenvalues. However, we also illustrate that the complexity could substantially differ for input matrices that are adjacency matrices of graphs.
2. We exhibit a stark contrast between invertibility and the above-mentioned spectral properties: we show a combinatorial characterization of matrices with invertible symmetric signings and design an efficient algorithm using this characterization to verify whether a given matrix has an invertible symmetric signing. Next, we give an efficient algorithm to solve the search problem of finding an invertible symmetric signing for matrices whose support graph is bipartite. We also provide a lower bound on the number of invertible symmetric signed adjacency matrices. Finally, we give an efficient algorithm to find a minimum increase in support of a given symmetric matrix so that it has an invertible symmetric signing.
We use combinatorial and spectral techniques in addition to classic results from matching theory. Our combinatorial characterization of matrices with invertible symmetric signings might be of independent interest.
△ Less
Submitted 24 July, 2017; v1 submitted 11 November, 2016;
originally announced November 2016.
