Увійти

Готові списки джерел за темами / Approximate counting / Статті в журналах

Статті в журналах з теми "Approximate counting"

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Approximate counting.

Автор: Grafiati

Опубліковано: 31 серпня 2024

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-50 статей у журналах для дослідження на тему "Approximate counting".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

BUSS, SAMUEL R., LESZEK ALEKSANDER KOŁODZIEJCZYK, and NEIL THAPEN. "FRAGMENTS OF APPROXIMATE COUNTING." Journal of Symbolic Logic 79, no. 2 (June 2014): 496–525. http://dx.doi.org/10.1017/jsl.2013.37.

Повний текст джерела

Анотація:

AbstractWe study the long-standing open problem of giving $\forall {\rm{\Sigma }}_1^b$ separations for fragments of bounded arithmetic in the relativized setting. Rather than considering the usual fragments defined by the amount of induction they allow, we study Jeřábek’s theories for approximate counting and their subtheories. We show that the $\forall {\rm{\Sigma }}_1^b$ Herbrandized ordering principle is unprovable in a fragment of bounded arithmetic that includes the injective weak pigeonhole principle for polynomial time functions, and also in a fragment that includes the surjective weak pigeonhole principle for FPNP functions. We further give new propositional translations, in terms of random resolution refutations, for the consequences of $T_2^1$ augmented with the surjective weak pigeonhole principle for polynomial time functions.

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Aronov, Boris, and Micha Sharir. "Approximate Halfspace Range Counting." SIAM Journal on Computing 39, no. 7 (January 2010): 2704–25. http://dx.doi.org/10.1137/080736600.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

3

Louchard, Guy, and Helmut Prodinger. "Generalized approximate counting revisited." Theoretical Computer Science 391, no. 1-2 (February 2008): 109–25. http://dx.doi.org/10.1016/j.tcs.2007.10.035.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Jeřábek, Emil. "Approximate counting in bounded arithmetic." Journal of Symbolic Logic 72, no. 3 (September 2007): 959–93. http://dx.doi.org/10.2178/jsl/1191333850.

Повний текст джерела

Анотація:

AbstractWe develop approximate counting of sets definable by Boolean circuits in bounded arithmetic using the dual weak pigeonhole principle (dWPHP(PV)), as a generalization of results from [15]. We discuss applications to formalization of randomized complexity classes (such as BPP, APP, MA, AM) in PV1 + dWPHP(PV).

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Cichoń, Jacek, and Karol Gotfryd. "Average Counting via Approximate Histograms." ACM Transactions on Sensor Networks 14, no. 2 (July 21, 2018): 1–32. http://dx.doi.org/10.1145/3177922.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Kirschenhofer, Peter, and Helmut Prodinger. "Approximate counting : an alternative approach." RAIRO - Theoretical Informatics and Applications 25, no. 1 (1991): 43–48. http://dx.doi.org/10.1051/ita/1991250100431.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

BORDEWICH, M., M. FREEDMAN, L. LOVÁSZ, and D. WELSH. "Approximate Counting and Quantum Computation." Combinatorics, Probability and Computing 14, no. 5-6 (October 11, 2005): 737. http://dx.doi.org/10.1017/s0963548305007005.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

8

Flajolet, Philippe. "Approximate counting: A detailed analysis." BIT 25, no. 1 (March 1985): 113–34. http://dx.doi.org/10.1007/bf01934993.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Erdős, Péter L., Sándor Z. Kiss, István Miklós, and Lajos Soukup. "Approximate Counting of Graphical Realizations." PLOS ONE 10, no. 7 (July 10, 2015): e0131300. http://dx.doi.org/10.1371/journal.pone.0131300.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Aldous, David. "Approximate Counting via Markov Chains." Statistical Science 8, no. 1 (February 1993): 16–19. http://dx.doi.org/10.1214/ss/1177011078.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Dudek, Andrzej, Alan Frieze, Andrzej Ruciński, and Matas Šileikis. "Approximate counting of regular hypergraphs." Information Processing Letters 113, no. 19-21 (September 2013): 785–88. http://dx.doi.org/10.1016/j.ipl.2013.07.018.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Barvinok, Alexander. "Approximate counting via random optimization." Random Structures and Algorithms 11, no. 2 (September 1997): 187–98. http://dx.doi.org/10.1002/(sici)1098-2418(199709)11:2<187::aid-rsa6>3.0.co;2-o.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Shaw, Arijit, Brendan Juba, and Kuldeep S. Meel. "An Approximate Skolem Function Counter." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (March 24, 2024): 8108–16. http://dx.doi.org/10.1609/aaai.v38i8.28650.

Повний текст джерела

Анотація:

One approach to probabilistic inference involves counting the number of models of a given Boolean formula. Here, we are interested in inferences involving higher-order objects, i.e., functions. We study the following task: Given a Boolean specification between a set of inputs and outputs, count the number of functions of inputs such that the specification is met. Such functions are called Skolem functions. We are motivated by the recent development of scalable approaches to Boolean function synthesis. This stands in relation to our problem analogously to the relationship between Boolean satisfiability and the model counting problem. Yet, counting Skolem functions poses considerable new challenges. From the complexity-theoretic standpoint, counting Skolem functions is not only #P-hard; it is quite unlikely to have an FPRAS (Fully Polynomial Randomized Approximation Scheme) as the problem of synthesizing a Skolem function remains challenging, even given access to an NP oracle. The primary contribution of this work is the first algorithm, SkolemFC, that computes the number of Skolem functions. SkolemFC relies on technical connections between counting functions and propositional model counting: our algorithm makes a linear number of calls to an approximate model counter and computes an estimate of the number of Skolem functions with theoretical guarantees. Our prototype displays impressive scalability, handling benchmarks comparably to state-of-the-art Skolem function synthesis engines, even though counting all such functions ostensibly poses a greater challenge than synthesizing a single function.

Стилі APA, Harvard, Vancouver, ISO та ін.

14

Gall, Francois Le, and Iu-Iong Ng. "Quantum approximate counting for Markov chains and collision counting." Quantum Information and Computation 22, no. 15&16 (November 2022): 1261. http://dx.doi.org/10.26421/qic22.15-16-1.

Повний текст джерела

Анотація:

In this paper we show how to generalize the quantum approximate counting technique developed by Brassard, H{\o}yer and Tapp [ICALP 1998] to a more general setting: estimating the number of marked states of a Markov chain (a Markov chain can be seen as a random walk over a graph with weighted edges). This makes it possible to construct quantum approximate counting algorithms from quantum search algorithms based on the powerful ``quantum walk based search'' framework established by Magniez, Nayak, Roland and Santha [SIAM Journal on Computing 2011]. As an application, we apply this approach to the quantum element distinctness algorithm by Ambainis [SIAM Journal on Computing 2007]: for two injective functions over a set of $N$ elements, we obtain a quantum algorithm that estimates the number $m$ of collisions of the two functions within relative error $\epsilon$ by making $\tilde{O}\left(\frac{1}{\epsilon^{25/24}}\big(\frac{N}{\sqrt{m}}\big)^{2/3}\right)$ queries, which gives an improvement over the $\Theta\big(\frac{1}{\epsilon}\frac{N}{\sqrt{m}}\big)$-query classical algorithm based on random sampling when $m\ll N$.

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Wang, Jinyan, Minghao Yin, and Jingli Wu. "Two approximate algorithms for model counting." Theoretical Computer Science 657 (January 2017): 28–37. http://dx.doi.org/10.1016/j.tcs.2016.04.047.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Shaltiel, Ronen, and Christopher Umans. "Pseudorandomness for Approximate Counting and Sampling." computational complexity 15, no. 4 (December 2006): 298–341. http://dx.doi.org/10.1007/s00037-007-0218-9.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Viola, Emanuele. "Randomness Buys Depth for Approximate Counting." computational complexity 23, no. 3 (January 8, 2014): 479–508. http://dx.doi.org/10.1007/s00037-013-0076-6.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

18

Chan, Timothy M., and Bryan T. Wilkinson. "Adaptive and Approximate Orthogonal Range Counting." ACM Transactions on Algorithms 12, no. 4 (September 2, 2016): 1–15. http://dx.doi.org/10.1145/2830567.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Afshani, Peyman, and Timothy M. Chan. "On Approximate Range Counting and Depth." Discrete & Computational Geometry 42, no. 1 (April 30, 2009): 3–21. http://dx.doi.org/10.1007/s00454-009-9177-z.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Miyata, Takahisa, and Tadashi Watanabe. "Approximate resolutions and box-counting dimension." Topology and its Applications 132, no. 1 (July 2003): 49–69. http://dx.doi.org/10.1016/s0166-8641(02)00362-0.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Meel, Kuldeep S., Supratik Chakraborty, and S. Akshay. "Auditable Algorithms for Approximate Model Counting." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 9 (March 24, 2024): 10654–61. http://dx.doi.org/10.1609/aaai.v38i9.28936.

Повний текст джерела

Анотація:

The problem of model counting, i.e., counting satisfying assignments of a Boolean formula, is a fundamental problem in computer science, with diverse applications. Given #P-hardness of the problem, many algorithms have been developed over the years to provide an approximate model count. Recently, building on the practical success of SAT-solvers used as NP oracles, the focus has shifted from theory to practical implementations of such algorithms. This has brought to focus new challenges. In this paper, we consider one such challenge – that of auditable deterministic approximate model counters wherein a counter should also generate a certificate, which allows a user (often with limited computational power) to independently audit whether the count returned by an invocation of the algorithm is indeed within the promised bounds. We start by examining a celebrated approximate model counting algorithm due to Stockmeyer that uses polynomially many calls to a \Sigma^2_P oracle, and show that it can be audited via a \Pi^2_P formula on (n^2 log^2 n) variables, where n is the number of variables in the original formula. Since n is often large (10’s to 100’s of thousands) for typical instances, we ask if the count of variables in the certificate formula can be reduced – a critical question towards potential implementation. We show that this improvement in certification can be achieved with a tradeoff in the counting algorithm’s complexity. Specifically, we develop new deterministic approximate model counting algorithms that invoke a \Sigma^3_P oracle, but can be certified using a \Pi^2_P formula on fewer variables: our final algorithm uses just (n log n) variables. Our study demonstrates that one can simplify certificate checking significantly if we allow the counting algorithm to access a slightly more powerful oracle. We believe this shows for the first time how the audit complexity can be traded for the complexity of approximate counting.

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Kabir, Mohimenul, Flavio O. Everardo, Ankit K. Shukla, Markus Hecher, Johannes Klaus Fichte, and Kuldeep S. Meel. "ApproxASP – a Scalable Approximate Answer Set Counter." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 5 (June 28, 2022): 5755–64. http://dx.doi.org/10.1609/aaai.v36i5.20518.

Повний текст джерела

Анотація:

Answer Set Programming (ASP) is a framework in artificial intelligence and knowledge representation for declarative modeling and problem solving. Modern ASP solvers focus on the computation or enumeration of answer sets. However, a variety of probabilistic applications in reasoning or logic programming require counting answer sets. While counting can be done by enumeration, simple enumeration becomes immediately infeasible if the number of solutions is high. On the other hand, approaches to exact counting are of high worst-case complexity. In fact, in propositional model counting, exact counting becomes impractical. In this work, we present a scalable approach to approximate counting for answer set programming. Our approach is based on systematically adding XOR constraints to ASP programs, which divide the search space. We prove that adding random XOR constraints partitions the answer sets of an ASP program. In practice, we use a Gaussian elimination-based approach by lifting ideas from SAT to ASP and integrating it into a state of the art ASP solver, which we call ApproxASP. Finally, our experimental evaluation shows the scalability of our approach over the existing ASP systems.

Стилі APA, Harvard, Vancouver, ISO та ін.

23

Jeřábek, Emil. "Approximate counting by hashing in bounded arithmetic." Journal of Symbolic Logic 74, no. 3 (September 2009): 829–60. http://dx.doi.org/10.2178/jsl/1245158087.

Повний текст джерела

Анотація:

AbstractWe show how to formalize approximate counting via hash functions in subsystems of bounded arithmetic, using variants of the weak pigeonhole principle. We discuss several applications, including a proof of the tournament principle, and an improvement on the known relationship of the collapse of the bounded arithmetic hierarchy to the collapse of the polynomial-time hierarchy.

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Andrés Montoya, J. "On the parameterized complexity of approximate counting." RAIRO - Theoretical Informatics and Applications 45, no. 2 (April 2011): 197–223. http://dx.doi.org/10.1051/ita/2011007.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Barvinok, A., and A. Samorodnitsky. "The distance approach to approximate combinatorial counting." Geometric And Functional Analysis 11, no. 5 (December 1, 2001): 871–99. http://dx.doi.org/10.1007/s00039-001-8219-3.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

26

Dyer, Martin, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. "The Relative Complexity of Approximate Counting Problems." Algorithmica 38, no. 3 (December 10, 2003): 471–500. http://dx.doi.org/10.1007/s00453-003-1073-y.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

27

Abboud, Ralph, Ismail Ceylan, and Thomas Lukasiewicz. "Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3097–104. http://dx.doi.org/10.1609/aaai.v34i04.5705.

Повний текст джерела

Анотація:

Weighted model counting (WMC) has emerged as a prevalent approach for probabilistic inference. In its most general form, WMC is #P-hard. Weighted DNF counting (weighted #DNF) is a special case, where approximations with probabilistic guarantees are obtained in O(nm), where n denotes the number of variables, and m the number of clauses of the input DNF, but this is not scalable in practice. In this paper, we propose a neural model counting approach for weighted #DNF that combines approximate model counting with deep learning, and accurately approximates model counts in linear time when width is bounded. We conduct experiments to validate our method, and show that our model learns and generalizes very well to large-scale #DNF instances.

Стилі APA, Harvard, Vancouver, ISO та ін.

28

Saha, Seemanta, Surendra Ghentiyala, Shihua Lu, Lucas Bang, and Tevfik Bultan. "Obtaining Information Leakage Bounds via Approximate Model Counting." Proceedings of the ACM on Programming Languages 7, PLDI (June 6, 2023): 1488–509. http://dx.doi.org/10.1145/3591281.

Повний текст джерела

Анотація:

Information leaks are a significant problem in modern software systems. In recent years, information theoretic concepts, such as Shannon entropy, have been applied to quantifying information leaks in programs. One recent approach is to use symbolic execution together with model counting constraints solvers in order to quantify information leakage. There are at least two reasons for unsoundness in quantifying information leakage using this approach: 1) Symbolic execution may not be able to explore all execution paths, 2) Model counting constraints solvers may not be able to provide an exact count. We present a sound symbolic quantitative information flow analysis that bounds the information leakage both for the cases where the program behavior is not fully explored and the model counting constraint solver is unable to provide a precise model count but provides an upper and a lower bound. We implemented our approach as an extension to KLEE for computing sound bounds for information leakage in C programs.

Стилі APA, Harvard, Vancouver, ISO та ін.

29

Dell, Holger, and John Lapinskas. "Fine-Grained Reductions from Approximate Counting to Decision." ACM Transactions on Computation Theory 13, no. 2 (June 2021): 1–24. http://dx.doi.org/10.1145/3442352.

Повний текст джерела

Анотація:

In this article, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus, we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the polynomial-time setting, and a similar result of Müller (IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). While all these problems have simple algorithms over which it is conjectured that no polynomial improvement is possible, our reductions would remain interesting even if these conjectures were proved; they have only polylogarithmic overhead and can therefore be applied to subpolynomial improvements such as the n 3 / exp(Θ (√ log n ))-time algorithm for the Negative-Weight Triangle problem due to Williams (STOC 2014). Our framework is also general enough to apply to versions of the problems for which more efficient algorithms are known. For example, the Orthogonal Vectors problem over GF( m ) d for constant m can be solved in time n · poly ( d ) by a result of Williams and Yu (SODA 2014); our result implies that we can approximately count the number of orthogonal pairs with essentially the same running time. We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some 1 < c < 2 and all k there is an O ( c n )-time algorithm for k -SAT. Then we prove that for all k , there is an O (( c + o (1)) n )-time algorithm for approximate # k -SAT. In particular, our result implies that the Exponential Time Hypothesis (ETH) is equivalent to the seemingly weaker statement that there is no algorithm to approximate #3-SAT to within a factor of 1+ɛ in time 2 o ( n )/ ɛ 2 (taking ɛ > 0 as part of the input).

Стилі APA, Harvard, Vancouver, ISO та ін.

30

Aspnes, James, and Keren Censor. "Approximate shared-memory counting despite a strong adversary." ACM Transactions on Algorithms 6, no. 2 (March 2010): 1–23. http://dx.doi.org/10.1145/1721837.1721841.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

31

Bulatov, Andrei A., and Stanislav Živný. "Approximate Counting CSP Seen from the Other Side." ACM Transactions on Computation Theory 12, no. 2 (May 14, 2020): 1–19. http://dx.doi.org/10.1145/3389390.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

32

Prodinger, Helmut. "Approximate counting with m counters: A detailed analysis." Theoretical Computer Science 439 (June 2012): 58–68. http://dx.doi.org/10.1016/j.tcs.2012.03.016.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

33

Sonntag, Dag, Jose M. Peña, and Manuel Gómez-Olmedo. "Approximate Counting of Graphical Models via MCMC Revisited." International Journal of Intelligent Systems 30, no. 3 (December 24, 2014): 384–420. http://dx.doi.org/10.1002/int.21704.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

34

Lai, Yong, Kuldeep S. Meel, and Roland H. C. Yap. "Fast Converging Anytime Model Counting." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4025–34. http://dx.doi.org/10.1609/aaai.v37i4.25517.

Повний текст джерела

Анотація:

Model counting is a fundamental problem which has been influential in many applications, from artificial intelligence to formal verification. Due to the intrinsic hardness of model counting, approximate techniques have been developed to solve real-world instances of model counting. This paper designs a new anytime approach called PartialKC for approximate model counting. The idea is a form of partial knowledge compilation to provide an unbiased estimate of the model count which can converge to the exact count. Our empirical analysis demonstrates that PartialKC achieves significant scalability and accuracy over prior state-of-the-art approximate counters, including satss and STS. Interestingly, the empirical results show that PartialKC reaches convergence for many instances and therefore provides exact model counting performance comparable to state-of-the-art exact counters.

Стилі APA, Harvard, Vancouver, ISO та ін.

35

Zhang, Fangyuan, Dechuang Chen, Sibo Wang, Yin Yang, and Junhao Gan. "Scalable Approximate Butterfly and Bi-triangle Counting for Large Bipartite Networks." Proceedings of the ACM on Management of Data 1, no. 4 (December 8, 2023): 1–26. http://dx.doi.org/10.1145/3626753.

Повний текст джерела

Анотація:

A bipartite graph is a graph that consists of two disjoint sets of vertices and only edges between vertices from different vertex sets. In this paper, we study the counting problems of two common types of em motifs in bipartite graphs: (i) butterflies (2x2 bicliques) and (ii) bi-triangles (length-6 cycles). Unlike most of the existing algorithms that aim to obtain exact counts, our goal is to obtain precise enough estimations of these counts in bipartite graphs, as such estimations are already sufficient and of great usefulness in various applications. While there exist approximate algorithms for butterfly counting, these algorithms are mainly based on the techniques designed for general graphs, and hence, they are less effective on bipartite graphs. Not to mention that there is still a lack of study on approximate bi-triangle counting. Motivated by this, we first propose a novel butterfly counting algorithm, called one-sided weighted sampling, which is tailored for bipartite graphs. The basic idea of this algorithm is to estimate the total butterfly count with the number of butterflies containing two randomly sampled vertices from the same side of the two vertex sets. We prove that our estimation is unbiased, and our technique can be further extended (non-trivially) for bi-triangle count estimation. Theoretical analyses under a power-law random bipartite graph model and extensive experiments on multiple large real datasets demonstrate that our proposed approximate counting algorithms can reach high accuracy, yet achieve up to three orders (resp. four orders) of magnitude speed-up over the state-of-the-art exact butterfly (resp. bi-triangle) counting algorithms. Additionally, we present an approximate clustering coefficient estimation framework for bipartite graphs, which shows a similar speed-up over the exact solutions with less than 1% relative error.

Стилі APA, Harvard, Vancouver, ISO та ін.

36

Ge, Cunjing. "Approximate Integer Solution Counts over Linear Arithmetic Constraints." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (March 24, 2024): 8022–29. http://dx.doi.org/10.1609/aaai.v38i8.28640.

Повний текст джерела

Анотація:

Counting integer solutions of linear constraints has found interesting applications in various fields. It is equivalent to the problem of counting lattice points inside a polytope. However, state-of-the-art algorithms for this problem become too slow for even a modest number of variables. In this paper, we propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. The counts computed by our approach has been proved approximately bounded by a (epsilon, delta)-bound. Experiments on extensive benchmarks show that our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.

Стилі APA, Harvard, Vancouver, ISO та ін.

37

Vartziotis, Dimitris, and Joachim Wipper. "The Fractal Nature of an Approximate Prime Counting Function." Fractal and Fractional 1, no. 1 (November 8, 2017): 10. http://dx.doi.org/10.3390/fractalfract1010010.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

38

Wojciechowski, J. "An approximate formula for counting trees in a graph." IEEE Transactions on Circuits and Systems 32, no. 4 (April 1985): 382–85. http://dx.doi.org/10.1109/tcs.1985.1085721.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

39

Wei, Zhewei, and Ke Yi. "Tight Space Bounds for Two-Dimensional Approximate Range Counting." ACM Transactions on Algorithms 14, no. 2 (June 4, 2018): 1–17. http://dx.doi.org/10.1145/3205454.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

40

Cvetkovski, Andrej. "An algorithm for approximate counting using limited memory resources." ACM SIGMETRICS Performance Evaluation Review 35, no. 1 (June 12, 2007): 181–90. http://dx.doi.org/10.1145/1269899.1254903.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

41

Jones, J. A., and M. Mosca. "Approximate Quantum Counting on an NMR Ensemble Quantum Computer." Physical Review Letters 83, no. 5 (August 2, 1999): 1050–53. http://dx.doi.org/10.1103/physrevlett.83.1050.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

42

G. Groer, P. "Exact and Approximate Bayesian Estimation of Net Counting Rates." Radiation Protection Dosimetry 102, no. 3 (November 1, 2002): 265–68. http://dx.doi.org/10.1093/oxfordjournals.rpd.a006095.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

43

Atserias, Albert, and Neil Thapen. "The Ordering Principle in a Fragment of Approximate Counting." ACM Transactions on Computational Logic 15, no. 4 (August 2014): 1–11. http://dx.doi.org/10.1145/2629555.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

44

Pandey, Prashant, Michael A. Bender, Rob Johnson, and Rob Patro. "Squeakr: an exact and approximate k-mer counting system." Bioinformatics 34, no. 4 (October 9, 2017): 568–75. http://dx.doi.org/10.1093/bioinformatics/btx636.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

45

Zhou, Jinhong, Chao Wang, Xi Li, and Xuehai Zhou. "Fast approximate hash table using extended counting Bloom filter." International Journal of Computational Science and Engineering 11, no. 4 (2015): 380. http://dx.doi.org/10.1504/ijcse.2015.073497.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

46

Yamakami, Tomoyuki. "Approximate counting for complex-weighted Boolean constraint satisfaction problems." Information and Computation 219 (October 2012): 17–38. http://dx.doi.org/10.1016/j.ic.2012.08.002.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

47

Sinclair, Alistair, and Mark Jerrum. "Approximate counting, uniform generation and rapidly mixing Markov chains." Information and Computation 82, no. 1 (July 1989): 93–133. http://dx.doi.org/10.1016/0890-5401(89)90067-9.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

48

Su, Na, Zhe Hui Wu, Ji Min Liu, Tai An Liu, Xin Jun An, and Chang Qing Yan. "Mining Approximate Frequent Itemsets over Data Streams." Applied Mechanics and Materials 685 (October 2014): 536–39. http://dx.doi.org/10.4028/www.scientific.net/amm.685.536.

Повний текст джерела

Анотація:

This paper proposes a method based on Lossy Counting to mine frequent itemsets. Logarithmic tilted time window is adopted to emphasize the importance of recent data. Multilayer count queue framework is used to avoid the counter overflowing and query top-Kitemsets quickly using a index table.

Стилі APA, Harvard, Vancouver, ISO та ін.

49

Obster, Dennis, and Naoki Sasakura. "Counting Tensor Rank Decompositions." Universe 7, no. 8 (August 15, 2021): 302. http://dx.doi.org/10.3390/universe7080302.

Повний текст джерела

Анотація:

Tensor rank decomposition is a useful tool for geometric interpretation of the tensors in the canonical tensor model (CTM) of quantum gravity. In order to understand the stability of this interpretation, it is important to be able to estimate how many tensor rank decompositions can approximate a given tensor. More precisely, finding an approximate symmetric tensor rank decomposition of a symmetric tensor Q with an error allowance Δ is to find vectors ϕi satisfying ∥Q−∑i=1Rϕi⊗ϕi⋯⊗ϕi∥2≤Δ. The volume of all such possible ϕi is an interesting quantity which measures the amount of possible decompositions for a tensor Q within an allowance. While it would be difficult to evaluate this quantity for each Q, we find an explicit formula for a similar quantity by integrating over all Q of unit norm. The expression as a function of Δ is given by the product of a hypergeometric function and a power function. By combining new numerical analysis and previous results, we conjecture a formula for the critical rank, yielding an estimate for the spacetime degrees of freedom of the CTM. We also extend the formula to generic decompositions of non-symmetric tensors in order to make our results more broadly applicable. Interestingly, the derivation depends on the existence (convergence) of the partition function of a matrix model which previously appeared in the context of the CTM.

Стилі APA, Harvard, Vancouver, ISO та ін.

50

Das, Mayukh, Devendra Singh Dhami, Gautam Kunapuli, Kristian Kersting, and Sriraam Natarajan. "Fast Relational Probabilistic Inference and Learning: Approximate Counting via Hypergraphs." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7816–24. http://dx.doi.org/10.1609/aaai.v33i01.33017816.

Повний текст джерела

Анотація:

Counting the number of true instances of a clause is arguably a major bottleneck in relational probabilistic inference and learning. We approximate counts in two steps: (1) transform the fully grounded relational model to a large hypergraph, and partially-instantiated clauses to hypergraph motifs; (2) since the expected counts of the motifs are provably the clause counts, approximate them using summary statistics (in/outdegrees, edge counts, etc). Our experimental results demonstrate the efficiency of these approximations, which can be applied to many complex statistical relational models, and can be significantly faster than state-of-the-art, both for inference and learning, without sacrificing effectiveness.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!