📃Scientific paper: Faster parameterized algorithms for modification problems to minor-closed classes Abstract: Let G be a minor-closed graph class and let G be an n-vertex graph. We say that G is a k-apex of G if G contains a set S of at most k vertices such that G \ S belongs to G. Our first result is an algorithm that decides whether G is a k-apex of G in time 2 poly\(k\) • n 2. This algorithm improves the previous one, given by Sau, Stamoulis, and Thilikos \[ICALP 2020, TALG 2022\], whose running time was 2 poly\(k\) • n^3. The elimination distance of G to G, denoted by edG\(G\), is the minimum number of rounds required to reduce each connected component of G to a graph in G by removing one vertex from each connected component in each round. Bulian and Dawar \[Algorithmica 2017\] proved the existence of an FPT-algorithm, with parameter k, to decide whether edG\(G\) ≤ k. This algorithm is based on the computability of the minor-obstructions and its dependence on k is not explicit. We extend the techniques used in the first algorithm to decide whether edG\(G\) ≤ k in time 2^2^2^poly\(k\) • n^2. This is the first algorithm for this problem with an explicit parametric dependence in k. In the special case where G excludes some apex-graph as a minor, we give two alternative algorithms, one running in time 2^2^O\(k 2 log k\) • n 2 and one running in time 2 poly\(k\) • n^3. As a stepping stone for these algorithms, we provide an algorithm that decides whether edG\(G\) ≤ k in time 2 O\(tw•k+tw log tw\) • n, where tw is the treewidth of G. This algorithm combines the dynamic programming framework of Re... Continued on ES/IODE ➡️ https://etcse.fr/HZS ------- If you find this interesting, feel free to follow, comment and share. We need your help to enhance our visibility, so that our platform continues to serve you.
es/iode’s Post
More Relevant Posts
-
📃Scientific paper: A Reusable Machine-Calculus for Automated Resource Analyses;Une machine abstraite réutilisable pour les analyses de ressources Abstract: International audience; An automated resource analysis technique is introduced, targeting a Call-By-Push-Value abstract machine, with memory prediction as a practical goal. The machine has a polymorphic and linear type system enhanced with a first-order logical fragment, which encodes both low-level operational semantics of resource manipulations and high-level synthesis of algorithmic complexity. Resource analysis must involve a diversity of static analysis, for escape, aliasing, algorithmic invariants, and more. Knowing this, we implement the Automated Amortized Resource Analysis framework (AARA) from scratch in our generic system. In this setting, access to resources is a state-passing effect which produces a compile-time approximation of runtime resource usage. We implemented type inference constraint generation for our calculus, accompanied with an elaboration of bounds for iterators on algebraic datatypes, for minimal ML-style programming languages with Call-by-Value and Call-By-Push-Value semantics. The closed-formed bounds are derived as multivariate polynomials over the integers. This now serves as a base for the development of an experimental toolkit for automated memory analysis of functional languages. Continued on ES/IODE ➡️ https://etcse.fr/TVbM ------- If you find this interesting, feel free to follow, comment and share. We need your help to enhance our visibility, so that our platform continues to serve you.
A Reusable Machine-Calculus for Automated Resource Analyses;Une machine abstraite réutilisable pour les analyses de ressources
ethicseido.com
To view or add a comment, sign in
-
#Algorithms_Design_Techniques (Part-3) Classification by Design Approaches encompasses two main strategies for algorithm design: Top-Down Approach: This method involves breaking down a complex problem into smaller, more manageable sub-problems. The process continues recursively until each sub-problem is solvable, eventually leading to a solution for the original complex problem. Bottom-Up Approach: Conversely, the bottom-up approach, also known as the reverse of the top-down approach, involves solving individual components of a complex program using a programming language. These components are then combined to form the complete program. In the top-down approach, the system is designed starting from the highest level of abstraction and gradually refining it to lower levels, whereas the bottom-up approach builds the system by starting with individual components and integrating them into a larger system. Each approach has its own advantages and disadvantages, with the choice often dependent on the specific problem at hand. Additionally, algorithms can be classified into other categories, including: Randomized Algorithms: These algorithms utilize random choices to achieve faster solutions. An example is the Randomized Quicksort Algorithm. Classification by Complexity: Algorithms are categorized based on the time taken to solve a problem for a given input size, known as time complexity analysis. Some algorithms have linear time complexity (O(n)), while others have exponential time complexity. Classification by Research Area: Each field in computer science has its own set of problems that require efficient algorithms. Examples include Sorting Algorithms, Searching Algorithms, and Machine Learning algorithms. Branch and Bound Enumeration and Backtracking: These techniques are commonly used in Artificial Intelligence. In conclusion, the classification of algorithms plays a vital role in organizing, understanding, and comparing different algorithms. Whether categorized by design method, complexity, or research area, these classifications aid in problem-solving, performance comparison, and algorithm reuse. Moreover, they are essential for research and development in various fields of computer science, contributing to the efficiency and effectiveness of problem-solving processes.
To view or add a comment, sign in
-
Certified Scrum Master (CSM) , Founder- VibeHub India , MBA @ Woxsen Business School | Software Developer Ex-TCS, Ex-Accenture, Ex-RSKian| Computer Science Engineering-JIIT Noida
🌟 14 Essential Algorithms Every Programmer Should Know 🌟 As a programmer, understanding key algorithms is crucial for solving complex problems efficiently. Here are 14 algorithms that form the backbone of computational thinking: Sorting Algorithms: e.g., Bubble Sort, Quick Sort, Merge Sort. Searching Algorithms: e.g., Binary Search, Linear Search. Graph Algorithms: e.g., Breadth-First Search (BFS), Depth-First Search (DFS). Dynamic Programming: Optimal substructure and overlapping subproblems. Greedy Algorithms: e.g., Dijkstra's algorithm, Prim's algorithm. String Algorithms: e.g., Knuth-Morris-Pratt (KMP) algorithm, Rabin-Karp algorithm. Tree Algorithms: e.g., Binary Tree traversal (inorder, preorder, postorder). Divide and Conquer: e.g., Binary Search, Merge Sort. Backtracking: e.g., N-Queens problem, Sudoku solver. Mathematical Algorithms: e.g., Euclidean algorithm (GCD), Sieve of Eratosthenes. Bit Manipulation: e.g., Bitwise operations, XOR properties. Sorting Network: e.g., Bitonic sort, Batcher's odd-even merge. Parallel Algorithms: e.g., Parallel merge sort, Parallel prefix sum. Randomized Algorithms: e.g., QuickSelect, Monte Carlo algorithms. Mastering these algorithms not only enhances problem-solving skills but also lays a strong foundation for algorithmic thinking in software development. Which algorithms have been most impactful in your programming journey? #Algorithms #Programming #SoftwareDevelopment #ProblemSolving #ComputerScience #ContinuousLearning
To view or add a comment, sign in
-
Exciting news! Our paper titled "Synthesizing Libraries of Programs with Auxiliary Functions" has been published in the Transactions on Machine Learning Research (TMLR). Check it out: https://lnkd.in/gwBSwtF2 #ProgramSynthesis #MachineLearning #Research #Programming #AI
Synthesizing Libraries of Programs with Auxiliary Functions
openreview.net
To view or add a comment, sign in
-
VP, Data Scientist @ Truist | Physicist | MBA | MSc Physics | Data Science, ML and AI | Computer Vision | ex-IBM | IITB
Interesting paper: Programmable Variational Inference Paper link on Hugging Face: https://lnkd.in/gRnQ2WQC #paper #bookmark
MSc Student in Applied Mathematics | Probabilistic ML | RL | High-Performance Scientific Computing | Independent Researcher
Programmable Variational Inference Modern probabilistic models rely on variational inference and despite all advances so far, we have yet to unlock the full potential of this powerful inference framework. The most popular way of doing it which you can find in almost any tutorial on variational inference, is optimizing ELBO. However, this is just one way to perform VI while there might be more suitable objective functions depending on your problem. So Why is everyone using ELBO? because in VI, changing the objective function is not easy. Anything we use, at the end we will have to compute its gradient for solving the optimization problem. The difficulty is that in variational inference, computing the exact gradient is not an option and we usually use an estimation of gradient instead. you can read more about this gradient estimation problem here: 📔 Monte Carlo Gradient Estimation in Machine Learning ✏️ Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih https://lnkd.in/ekh4ppn2 Today I was reading an interesting research proposing a framework for automating gradient estimation: 📔 Probabilistic Programming with Programmable Variational Inference ✏️ McCoy R. Becker, Alexander K. Lew, Xiaoyan Wang, Matin Ghavami, Mathieu Huot, Martin C. Rinard, Vikash K. Mansinghka Arxiv : https://lnkd.in/d4DY4ywz 🔴 You can try their implementation in jax: https://lnkd.in/d57WjfTB Image is taken from the second paper.
To view or add a comment, sign in
-
-
🚀 Exploring #LoRA and Full Finetuning in Large Language Models 🧵👇 🔍 New Research from Columbia University & Databricks Mosaic AI! 1️⃣ Instruction Finetuning with 100K Prompt-Response Pairs - 🔹 Finding: Full finetuning outperforms LoRA in specialized tasks like programming and math. - 🔹 Insight: Full finetuning adapts better to specific tasks, while LoRA's regularization maintains broader task performance. 2️⃣ Continued Pretraining with 10B Unstructured Tokens - 🔹Finding: Full finetuning excels in target domains, LoRA retains base model capabilities in other tasks. - 🔹 Insight: Full finetuning’s adaptability leads to better target task performance, but LoRA preserves a wider skill set. 3️⃣ Regularization Effectiveness - 🔹 Finding: LoRA offers stronger regularization than weight decay and dropout. - 🔹 Insight: LoRA maintains performance across diverse tasks and generates more varied outputs. Great for general-purpose use! 4️⃣ Rank of Learned Perturbations - 🔹 Finding: Full finetuning learns perturbations with a rank 10-100x higher than typical LoRA configs. - 🔹 Insight: Higher rank explains full finetuning’s performance but comes with higher memory and computational costs. 5️⃣ Best Practices for Finetuning with LoRA - 🔹 Finding: Proposes strategies for balancing target task performance and broader model capabilities. - 🔹 Insight: Achieving a balance between specialization and generalization leverages LoRA’s regularization benefits. Conclusion - Full finetuning maximizes specific domain performance but at higher costs and risk of overfitting. - LoRA provides a balanced approach, maintaining broader capabilities with less computational power. Read the full paper here: 🔗 https://lnkd.in/dhMegFSZ
LoRA Learns Less and Forgets Less
arxiv.org
To view or add a comment, sign in
-
Some tech talk today! #technology 💪 The first phase of my coding project is stable - basic objects, user interface, and basic puzzle solving algorithm. I use a quite straightforward recursive algorithm https://lnkd.in/e-SDkt2B), which, I discovered later, is in a fact using backtracking https://lnkd.in/eymDuuAD. It works fine when there are about 10^4 options. It works horrible for the next problem, which is - my calculation may not be perfectly accurate, but I think the order of magnitude is OK - more in the 10^15 range! So I have to go into performance improvement, and this is another level of thrill... Here are a few tracks: - optimising the number or depth of branches to explore, with immediate exclusion tests ✔ - subdivision of the puzzle, when needed. Did not prove so effective.❌ - I read about backjumping, but have not yet managed to see how I could use the concept ❔ - Implementing more memory- and process-efficient code. Almost done, needs performance testing ➕ - I am thinking about implementing heuristic valuation methods to rank branches according to their probability of success. Still a concept. I wonder if neural networks could help. I think it will be the next sprint. Do you have suggestions? It is really interesting to see how rapidly you need to analyse a problem more in-depth once you have managed to set up the MVP! #computerprogramming #performance #trainyourbrain
Recursion (computer science) - Wikipedia
en.wikipedia.org
To view or add a comment, sign in
-
🤖 Turing-Complete Transformers: Two Transformers are more Powerful than One. In this paper https://lnkd.in/d2sppTVK, currently under review as a conference paper at ICLR2023, the researchers present Find+Replace, a family of multi-transformer architectures that are Turing-complete. They also show that this architecture outperforms GPT-4 on a set of classical Computer Science problems, like the Hanoi towers or dynamic programming. Firstly, the authors prove that Transformers are not Turing-complete, as they have fixed length and fixed vocabulary sizes. Computations that can be done through a Transformer are limited. Their proposal is the Find+Replace architecture, a multi-transformer system that operates on a sequence of arbitrary length called tape (as Turing himself would have called it). The Find Transformer identify parts of the input that pass to the Replace Transformer, which performs what essentially performs a mapping function. This find-and-replace approach is equivalent to three lambda calculus reductions, which in the real world means that it behaves like a programming language, being capable of solving any problem. This is the proof that this approach is Turing-complete. Having a Transformer architecture equivalent to a programming language also has its own perks, like initialising non-random weights or faster convergence. With this approach, they were able to solve the Tower of Hanoi problems of any input size. GPT-3 couldn't solve any, GPT-4 only had a problem with size 3. Isn't that impressive? It's too early to tell the implications of this work, but at least it is a really interesting read, and at most, world-changing. #nlproc #llms #python #opensource
To view or add a comment, sign in
-
-
Turing-complete Transformers might just be as big a leap for AI as transformers were for language models. The Find+Replace beating GPT-4? That's huge. We could be looking at the biggest AI breakthrough this year. Scoring perfect on tests is self-explanatory, but what's mind-blowing is their claim that this new setup is Turing-complete. If you know a bit about theoretical computer science, you'll realize this is a massive deal. Not in the short term, but probably this can become the new standard architecture for future models. #LLM #AI #TuringComplete
🤖 Turing-Complete Transformers: Two Transformers are more Powerful than One. In this paper https://lnkd.in/d2sppTVK, currently under review as a conference paper at ICLR2023, the researchers present Find+Replace, a family of multi-transformer architectures that are Turing-complete. They also show that this architecture outperforms GPT-4 on a set of classical Computer Science problems, like the Hanoi towers or dynamic programming. Firstly, the authors prove that Transformers are not Turing-complete, as they have fixed length and fixed vocabulary sizes. Computations that can be done through a Transformer are limited. Their proposal is the Find+Replace architecture, a multi-transformer system that operates on a sequence of arbitrary length called tape (as Turing himself would have called it). The Find Transformer identify parts of the input that pass to the Replace Transformer, which performs what essentially performs a mapping function. This find-and-replace approach is equivalent to three lambda calculus reductions, which in the real world means that it behaves like a programming language, being capable of solving any problem. This is the proof that this approach is Turing-complete. Having a Transformer architecture equivalent to a programming language also has its own perks, like initialising non-random weights or faster convergence. With this approach, they were able to solve the Tower of Hanoi problems of any input size. GPT-3 couldn't solve any, GPT-4 only had a problem with size 3. Isn't that impressive? It's too early to tell the implications of this work, but at least it is a really interesting read, and at most, world-changing. #nlproc #llms #python #opensource
To view or add a comment, sign in
-
-
🚀 Kadane's Algorithm: Your Key to Efficient Subarray Sum Calculation Ever wondered how to find the contiguous subarray within a list of numbers that gives the maximum sum? Meet Kadane's Algorithm, your solution for efficient computation! 📈 🔍 What does it do? Kadane's Algorithm is a clever technique that quickly pinpoints the subarray with the highest sum in a list of numbers. This problem-solving gem has wide applications, from finance to data analysis. 🛠️ How does it work? It's all about dynamic programming! This algorithm scans through the numbers, keeping tabs on the maximum sum seen so far and the maximum sum ending at each position in the list. ⚡ Why is it awesome? 1. Super Speedy:With a time complexity of O(n) for a list of 'n' numbers, it's lightning-fast compared to brute-force methods. 2. Space Saver: Plus, it does all this without gobbling up extra memory! 🌐 Where does it shine? Kadane's Algorithm pops up everywhere: - Crunching stock market data. - Analyzing images for contiguous areas. - Identifying sequences in genetics. - Powering up algorithms and machine learning for optimized calculations. 📚 Learning and Using It For anyone diving into algorithms or wanting to supercharge their problem-solving skills, Kadane's Algorithm is a must-know. Understanding it and putting it into practice can level up your computational game! 💡 Wrap Up Simple yet powerful, Kadane's Algorithm showcases the magic of elegant solutions in the world of computer science. Mastering it unlocks efficient ways to crack complex problems! #Algorithms #KadanesAlgorithm #Efficiency #Programming #ProblemSolving #ComputerScience
To view or add a comment, sign in
-